上海市计算机学会竞赛平台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;
}
全部评论 (0)
还没有任何评论哟~