[数据结构与算法]第20届上海大学程序设计联赛春季赛 F - 到底是多少分啊

链接：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$个数进行$t$次操作，能带来的得分总和除以操作的种类数。操作的种类我们可以看做球盒模型（$t$相同的球放进$n$个不同的盒子，可空）答案为$C_{n+t?1}^{n?1}$，于是只需要求得得分总和即可。
• 考虑令$f_{i,j}$表示对前$i$个数进行$j$次操作能获得的不同的得分之和，状态转移的时候我们枚举在第$i$个数进行次$k$次操作，即
  $$f_{i,j}=\sum _{k=0}^{j?1}(f_{i?1,j?k}\times (a_i+k))$$
  很明显这个转移时朴素的$n^3$，对于这个枚举当前操作几次的$dp$，我们考虑把它的形式拆开并且这样写观察一下
  $$\begin{gathered} 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)+?+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)?+f_{i?1,0}\times (a_i+j?1) \end{gathered}$$
  可得
  $$f_{i,j}=f_{i?1,j}\times a_i+f_{i,j?1}+\sum _{k=0}^{j?1}{f}_{i?1,k}$$
  这样维护一个前缀和就可以$O(n^2)$转移了。
  注意一下初始化的问题，仅让$f_{0,0}=1$即可，他来更新最开始的答案，其它的直接转移即可。

#include <bits/stdc++.h>

using 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;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖