一、题目
1、原题链接
4496. 吃水果
2、题目描述
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
输出样例1：
3
1
输入样例2：
3 2 1
1
输出样例2：
4
1
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）第一个小朋友（最左边）拿到水果的情况共有m种。
（2）因为题目中的k个小朋友不包括最左边的小朋友，所以先在n-1个小朋友中选择k个小朋友，这k个小朋友和其左边相邻的小朋友的水果不同，总共C n − 1 k C_{n-1}^{k}C
n−1
k
种情况。而这k个小朋友由于要和其左边的小朋友拿的水果不同，所以这k个人拿到的水果种类的情况总共(m-1)k种情况。所以总的情况数就有C n − 1 k C_{n-1}^{k}C
n−1
k
(m-1)k种。
（3）剩下的n-k-1个小朋友，拿到的水果和其左边小朋友的水果一样，所有他们拿到的水果是唯一确定的，只要确定了（1）（2）的情况总数，总的情况数也就确定了。
（4）所以答案即为C n − 1 k C_{n-1}^{k}C
n−1
k
m(m-1)k。
2、时间复杂度
时间复杂度为O(n2)
3、代码详解
#include <iostream>
using namespace std;
typedef long long LL;
const int N=2010,mod=998244353;
int c[N][N];
int n,m,k;
int main(){
cin>>n>>m>>k;
//求组合数
for(int i=0;i<=n-1;i++){
for(int j=0;j<=i&&j<=k;j++){
if(!j) c[i][j]=1;
else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
//求答案注意类似下面第二行不要写成ans*=m%mod 等形式，因为%的优先级高于*=，就会造成先取模再乘，而我们是要先乘再取模
LL ans=c[n-1][k]%mod;
ans=ans*m%mod;
for(int i=0;i<k;i++){
ans=ans*(m-1)%mod;
}
cout<<ans;
return 0;
}
三、知识风暴
求组合数
基本思想：利用公式C n m C_{n}^{m}C
n
m
=C n − 1 m C_{n-1}^{m}C
n−1
m
+C n − 1 m − 1 C_{n-1}^{m-1}C
n−1
m−1
递推，每个状态可以由其前面的转态推导出来，类似dp。
