题目描述
n
个小朋友站成一排,等着吃水果。
一共有 m
种水果,每种水果的数量都足够多。
现在,要给每个小朋友都发一个水果,要求:在所有小朋友都拿到水果后,恰好有 k
个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同(最左边的小朋友当然不算数,即最左边的小朋友不包含在 k
个小朋友内)。
请你计算,一共有多少种不同的分发水果的方案。
输入格式
一行,三个整数 n,m,k
。
输出格式
一个整数,表示合理的分发水果的方案总数量对 998244353
取模后的结果。
数据范围
前 5
个测试点满足 1≤n,m≤5
。
所有测试点满足 1≤n,m≤2000
, 0≤k≤n−1
。
样例
输入样例1:
3 3 0
输出样例1:
3
输入样例2:
3 2 1
输出样例2:
4
算法1
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=2010,MOD=998244353;
int n,m,k;
int f[N][N];//dp思想,表示前i个小朋友中恰好由k个小朋友与左边的不一样
int main()
{
scanf("%d%d%d",&n,&m,&k);
f[1][0]=m;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=k&&j<i;j++)
{
f[i][j]=f[i-1][j];//第i个小朋友与i-1相同
if(j)f[i][j]=(f[i][j]+f[i-1][j-1]*(m-1ll))%MOD;//如果存在i与左边不同,两种情况相加
}
}
cout<<f[n][k];
return 0;
}