0901-T2 笼中鸟
题意
给出正整数 \(n,k\)。
求长度为 \(k\)，每个数都是 \([1,n]\) 中的随机正整数的序列的众数的出现次数的期望值乘以 \(n^k\) 后的结果。
35pts 思路
定义 \(dp_{i,j,p}\) 表示考虑前 \(i\) 种数，长度为 \(j\)，众数出现次数为 \(p\) 的序列个数。
转移方程：
\[dp_{i,j,p}=\sum_{m=0}^{p-1}dp_{i-1,l-m,p}\times C_{j}^{m}+\sum_{m=0}^{p}dp_{i-1,l-p,m}\times C_{j}^{p} \]左侧的求和式子表示新来的数不是众数，枚举 \(m\) 表示新来的数的出现次数，\(C_{j}^m\) 表示在当前 \(j\) 个位置中选出 \(m\) 个放新来的数。
右侧的求和式子表示新来的数是众数，则出现次数为 \(p\)，枚举 \(m\) 表示上一个众数的出现次数，\(C_{j}^{p}\) 表示再当前 \(j\) 个位置中选出 \(p\) 个放新来的数。
注意左右两个求和式子在 \(m=p\) 时值相等，所以只有一边能取到 \(p\)，另一边只能取到 \(p-1\)，不然会算重复。
35pts 代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 205;
const int mod = 998244353;
int n, k, C[N][N];
int dp[N][N][N], ans;
signed main() {
cin >> n >> k;
C[0][0] = 1;
for (int i = 1; i <= 200; i ++) {
C[i][0] = 1;
for (int j = 1; j <= 200; j ++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
for (int i = 0; i <= n; i ++) dp[i][0][0] = 1;
for (int i = 1; i <= n; i ++) {
for (int l = 1; l <= k; l ++) {
for (int j = 1; j <= min(k, l); j ++) {
for (int m = 0; m < j; m ++)
dp[i][l][j] += dp[i - 1][l - m][j] * C[l][m] % mod, dp[i][l][j] %= mod;
for (int m = 0; m <= j; m ++)
dp[i][l][j] += dp[i - 1][l - j][m] * C[l][j] % mod, dp[i][l][j] %= mod;
}
}
}
for (int i = 1; i <= k; i ++) ans = (ans + dp[n][k][i] * i % mod) % mod;
cout << ans << "\n";
return 0;
}