【蓝桥杯集训·每日一题】AcWing 4496. 吃水果

一、题目

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：

3

输入样例2：

3 2 1

输出样例2：

4

二、解题报告

1、思路分析

思路来源：y总讲解视频
y总yyds

（1）第一个小朋友（最左边）拿到水果的情况共有m种。
（2）因为题目中的k个小朋友不包括最左边的小朋友，所以先在n-1个小朋友中选择k个小朋友，这k个小朋友和其左边相邻的小朋友的水果不同，总共$C_{n-1}^k$种情况。而这k个小朋友由于要和其左边的小朋友拿的水果不同，所以这k个人拿到的水果种类的情况总共(m-1)^k种情况。所以总的情况数就有$C_{n-1}^k$(m-1)^k种。
（3）剩下的n-k-1个小朋友，拿到的水果和其左边小朋友的水果一样，所有他们拿到的水果是唯一确定的，只要确定了（1）（2）的情况总数，总的情况数也就确定了。
（4）所以答案即为$C_{n-1}^k$m(m-1)^k。

2、时间复杂度

时间复杂度为O(n²)

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-1}^m$+$C_{n-1}^{m-1}$递推，每个状态可以由其前面的转态推导出来，类似dp。