上海市计算机学会竞赛平台2023年1月月赛丙组积木染色（二）

题目描述

𝑛n 块积木排成一排，需要给每块积木染色，颜色有 𝑚m 种。请问有多少种方法，从第二块积木开始统计，恰有 𝑝p 块积木与前一块积木颜色不同？

输入格式

三个整数分别表示 𝑛,𝑚,𝑝n,m,p

输出格式

输出满足条件的方案数模109+7109+7的结果

数据范围

• 对于 30%30% 的数据，1≤𝑛,𝑚≤101≤n,m≤10
• 对于 60%60% 的数据，1≤𝑛,𝑚≤5001≤n,m≤500
• 对于 100%100% 的数据，1≤𝑛,𝑚≤50001≤n,m≤5000,1≤𝑝<𝑛1≤p<n

样例数据

输入:

4 2 2

输出:

6

说明:

设两种颜色分别为1,2
则有：1121,1211,1221,2122,2112,2212共计6种

详见代码:

#include<bits/stdc++.h>
using namespace std;
long long dp[5005][5005];
long long n,m,p,ans;
long long init(int x,int y)
{
    if (x==0||y==0) return 1;
    for (int i=1;i<=x;i++)
    {
        for (int j=1;j<=y;j++)
        {
            if (i==1)
            {
                dp[i][j]=j;
            }
            else if (j==1)
            {
                dp[i][j]=1;
            }
            else
            {
                dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;
            }
        }
    }
    return dp[x][y];
}
 
long long f(long long k,long long p)
{
	if(p==1)
	{
		return k;
	}
	if(p%2==0)
	{
		return (f(k,p/2))*(f(k,p/2))%1000000007;
	}
	else
	{
		return (((f(k,p/2))*(f(k,p/2))%1000000007)*k)%1000000007;
	}
 
}
int main()
{
	cin>>n>>m>>p;
 
	ans=m*f(m-1,p)%1000000007;
	ans=(ans*init(n-p-1,p+1))%1000000007;
	cout<<ans<<endl;
	return 0;
}