小米网站建设案例,商城网站制作网站,wordpress类,WordPress网站生成小程序文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴求组合数一、题目
1、原题链接 4496. 吃水果 2、题目描述 n 个小朋友站成一排#xff0c;等着吃水果。 一共有 m 种水果#xff0c;每种水果的数量都足够多。 现在…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴求组合数一、题目
1、原题链接 4496. 吃水果 2、题目描述 n 个小朋友站成一排等着吃水果。 一共有 m 种水果每种水果的数量都足够多。 现在要给每个小朋友都发一个水果要求在所有小朋友都拿到水果后恰好有 k 个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同最左边的小朋友当然不算数即最左边的小朋友不包含在 k 个小朋友内。 请你计算一共有多少种不同的分发水果的方案。 输入格式 一行三个整数 n,m,k。 输出格式 一个整数表示合理的分发水果的方案总数量对 998244353 取模后的结果。 数据范围 前 5 个测试点满足 1≤n,m≤5。 所有测试点满足 1≤n,m≤20000≤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个小朋友和其左边相邻的小朋友的水果不同总共Cn−1kC_{n-1}^{k}Cn−1k种情况。而这k个小朋友由于要和其左边的小朋友拿的水果不同所以这k个人拿到的水果种类的情况总共(m-1)k种情况。所以总的情况数就有Cn−1kC_{n-1}^{k}Cn−1k(m-1)k种。 3剩下的n-k-1个小朋友拿到的水果和其左边小朋友的水果一样所有他们拿到的水果是唯一确定的只要确定了12的情况总数总的情况数也就确定了。 4所以答案即为Cn−1kC_{n-1}^{k}Cn−1km(m-1)k。
2、时间复杂度
时间复杂度为O(n2)
3、代码详解
#include iostream
using namespace std;
typedef long long LL;
const int N2010,mod998244353;
int c[N][N];
int n,m,k;
int main(){cinnmk;//求组合数for(int i0;in-1;i){for(int j0;jijk;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 ansc[n-1][k]%mod;ansans*m%mod;for(int i0;ik;i){ansans*(m-1)%mod;}coutans;return 0;
}三、知识风暴 求组合数 基本思想利用公式CnmC_{n}^{m}CnmCn−1mC_{n-1}^{m}Cn−1mCn−1m−1C_{n-1}^{m-1}Cn−1m−1递推每个状态可以由其前面的转态推导出来类似dp。
