链接：https://ac.nowcoder.com/acm/contest/33785/F
来源：牛客网
在旅途的终点，你终于看到了大魔王小 X。
小 X 准备玩一个游戏，这个游戏规则如下：
对于一个含有 n 个数的数组 a。小 X 必须执行如下操作 t 次：
选择数组中的某一个数，给它加上 1。
经过这样 t 次操作后得到的数组 b。小 X 的得分是数组 b 中所有数的乘积。
显然，在不同的操作过程后，最终可能获得不同的数组 b。我们称两个数组是不同的，当且仅当这两个数组中至少有一个数不同，即两个数组 p, q 不同当且仅当存在 i 使得 pi≠qi 。
如果小 X 在所有不同的数组 b 中随机取一个作为最终结果，那么他的期望得分是多少？
- 题目要求的是期望得分，等于对 n n n个数进行 t t t次操作，能带来的得分总和除以操作的种类数。操作的种类我们可以看做球盒模型（ t t t相同的球放进 n n n个不同的盒子，可空）答案为 C n + t − 1 n − 1 C_{n + t - 1}^{n - 1} Cn+t−1n−1，于是只需要求得得分总和即可。
- 考虑令
f
i
,
j
f_{i,j}
fi,j表示对前
i
i
i个数进行
j
j
j次操作能获得的不同的得分之和，状态转移的时候我们枚举在第
i
i
i个数进行次
k
k
k次操作，即
f i , j = ∑ k = 0 j − 1 ( f i − 1 , j − k × ( a i + k ) ) f_{i,j} = sum_{k = 0}^{j - 1}(f_{i-1,j - k}times (a_i + k)) fi,j=k=0∑j−1(fi−1,j−k×(ai+k))
很明显这个转移时朴素的 n 3 n^3 n3，对于这个枚举当前操作几次的 d p dp dp，我们考虑把它的形式拆开并且这样写观察一下
f i , j = f i − 1 , j × a i + f i − 1 , j − 1 × ( a i + 1 ) + f i − 1 , j − 2 × ( a i + 2 ) + ⋯ + f i − 1 , 0 × ( a i + j ) f i , j − 1 = f i − 1 , j − 1 × a i + f i − 1 , j − 2 × ( a i + 1 ) ⋯ + f i − 1 , 0 × ( a i + j − 1 ) f_{i,j} = f_{i-1,j}times a_i +f_{i-1,j - 1}times (a_i + 1) + f_{i-1,j - 2}times (a_i + 2) + cdots +f_{i-1,0}times (a_i + j) \ f_{i,j - 1} = f_{i-1,j - 1}times a_i + f_{i-1,j-2}times (a_i + 1)cdots +f_{i-1,0}times (a_i + j - 1) fi,j=fi−1,j×ai+fi−1,j−1×(ai+1)+fi−1,j−2×(ai+2)+⋯+fi−1,0×(ai+j)fi,j−1=fi−1,j−1×ai+fi−1,j−2×(ai+1)⋯+fi−1,0×(ai+j−1)
可得
f i , j = f i − 1 , j × a i + f i , j − 1 + ∑ k = 0 j − 1 f i − 1 , k f_{i,j} = f_{i-1,j}times a_i + f_{i,j - 1} + sum_{k = 0}^{j - 1}f_{i-1,k} fi,j=fi−1,j×ai+fi,j−1+k=0∑j−1fi−1,k
这样维护一个前缀和就可以 O ( n 2 ) O(n^2) O(n2)转移了。
注意一下初始化的问题，仅让 f 0 , 0 = 1 f_{0,0} = 1 f0,0=1即可，他来更新最开始的答案，其它的直接转移即可。
#includeusing namespace std; const long long mod = 998244353; long long f[3010][3010],a[3010],s[3010][3010],fac[10010]; long long fiv[10010],inv[10010]; void init() { fac[0] = fac[1] = fiv[0] = fiv[1] = inv[1] = 1; for(int i = 2;i <= 10000;i ++) { fac[i] = fac[i - 1] * i % mod; inv[i] = (mod - mod / i) * inv[mod % i] % mod; fiv[i] = inv[i] * fiv[i - 1] % mod; } } long long ksm(long long a,long long b) { long long res = 1; while(b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } long long invv(int x) { return ksm(1ll * x,mod - 2); } long long C(int n,int m) { return fac[n] * fiv[m] % mod * fiv[n - m] % mod; } int main() { init(); // fac[0] = 1; // for(int i = 1;i <= 10000;i ++) fac[i] = fac[i - 1] * i % mod; int n,t; cin >> n >> t; for(int i = 1;i <= n;i ++) { cin >> a[i]; } s[0][0] = f[0][0] = 1; for(int i = 1;i <= n;i ++) { f[i][0] = f[i - 1][0] * a[i] % mod; s[i][0] = f[i][0]; } for(int i = 1;i <= t;i ++) { s[0][i] = (s[0][i - 1] + f[0][i]) % mod; } for(int i = 1;i <= n;i ++) { for(int j = 1;j <= t;j ++) { f[i][j] = f[i - 1][j] * a[i] % mod; f[i][j] = (f[i][j] + f[i][j - 1]) % mod; f[i][j] = (f[i][j] + s[i - 1][j - 1]) % mod; } for(int j = 1;j <= t;j ++) { s[i][j] = (s[i][j - 1] + f[i][j]) % mod; } } long long ans = f[n][t] * invv(C(n + t - 1,n - 1)) % mod; cout << ans << 'n'; return 0; }
