写在前面
本人CSDN博客主页:这里
一、题目
1、原题链接
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:
3
输入样例2:
3 2 1
输出样例2:
4
二、解题报告
1、思路分析
思路来源:y总讲解视频 y总yyds
(1)第一个小朋友(最左边)拿到水果的情况共有m种。
(2)因为题目中的k个小朋友不包括最左边的小朋友,所以先在n-1个小朋友中选择k个小朋友,这k个小朋友和其左边相邻的小朋友的水果不同,总共种情况。而这k个小朋友由于要和其左边的小朋友拿的水果不同,所以这k个人拿到的水果种类的情况总共(m-1)k种情况。所以总的情况数就有
(m-1)k种。
(3)剩下的n-k-1个小朋友,拿到的水果和其左边小朋友的水果一样,所有他们拿到的水果是唯一确定的,只要确定了(1)(2)的情况总数,总的情况数也就确定了。
(4)所以答案即为
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;
}
三、知识风暴
标签:水果,int,左边,样例,拿到,蓝桥,4496,小朋友,AcWing From: https://blog.51cto.com/u_15720469/6374087求组合数
- 基本思想:利用公式
=
+
递推,每个状态可以由其前面的转态推导出来,类似dp。