题目描述
$n$ 个小朋友站成一排,等着吃水果。
一共有 $m$ 种水果,每种水果的数量都足够多。
现在,要给每个小朋友都发一个水果,要求:在所有小朋友都拿到水果后,恰好有 $k$ 个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同(最左边的小朋友当然不算数,即最左边的小朋友不包含在 $k$ 个小朋友内)。
请你计算,一共有多少种不同的分发水果的方案。
输入格式
一行,三个整数 $n,m,k$。
输出格式
一个整数,表示合理的分发水果的方案总数量对 $998244353$ 取模后的结果。
数据范围
前 $5$ 个测试点满足 $1 \\le n,m \\le 5$。
所有测试点满足 $1 \\le n,m \\le 2000$,$0 \\le k \\le n-1$。
输入样例1:
3 3 0
输出样例1:
3
输入样例2:
3 2 1
输出样例2:
4
算法
(动态规划) $O(n^2)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010, MOD = 998244353;
int n, m, k;
// f[i][j]表示只考虑前i个小朋友
// 恰好有j个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同 的方案数
int f[N][N];
int main()
{
// 输入
cin >> n >> m >> k;
// 初始化
// 只考虑前i个小朋友
// 恰好有0个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同
// 也就是前i个小朋友拿到的水果都是相同的
// 所以总共有m种方法(m种水果随便选一种水果)
for(int i = 1; i <= n; i ++) f[i][0] = m;
for(int i = 2; i <= n; i ++)
{
for(int j = 0; j <= k && j < i; j ++)
{
// 如何计算f[i][j]
// f[i][j]由两种情况组成
// 1、第i个小朋友与其左边相邻的小朋友水果相同
// 所以根据f数组的含义可知这种情况的结果就是f[i - 1][j]
// f[i - 1][j]表示的就是
// 先考虑前i-1个小朋友
// 恰好有j个小朋友和其左边相邻小朋友拿到的水果不同的方案数
// 再考虑第i个小朋友
// 因为第i个小朋友与其左边相邻的小朋友水果相同所以只有1种选择
// 2、第i个小朋友与其左边相邻的小朋友水果不相同
// 所以根据f数组的含义可知这种情况的结果就是f[i - 1][j - 1] * (m - 1)
// f[i - 1][j - 1]表示的就是
// 先考虑前i-1个小朋友
// 恰好有j-1个小朋友和其左边相邻小朋友拿到的水果不同的方案数
// 再考虑第i个小朋友
// 因为第i个小朋友与其左边相邻的小朋友水果不相同所以有(m - 1)种选择
f[i][j] = (f[i - 1][j - 1] * 1ll * (m - 1) + f[i - 1][j]) % MOD;
}
}
// 答案就是考虑前n个小朋友
// 恰好有k个小朋友拿到的水果和其左边相邻小朋友拿到的水果不同 的方案数
// f[n][k]即为所求答案
cout << f[n][k] << endl;
return 0;
}