【Luogu】重返现世

发表于
https://www.luogu.org/problemnew/show/P4707

题目链接：

【Luogu】重返现世

题目描述：

为了打开返回现世的大门，Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 $ n $ 种原料，只需要集齐任意 $ k $ 种，就可以开始制作。
Yopilla 来到了迷失大陆的核心地域。每个单位时间，这片地域就会随机生成一种原料。每种原料被生成的概率是不同的，第 $ i $ 种原料被生成的概率是 $ \frac{P_i}{m} $ 。如果 Yopilla 没有这种原料，那么就可以进行收集。
Yopilla 急于知道，他收集到任意 $ k $ 种原料的期望时间，答案对 $ 998244353 $ 取模。

做法：

根据 $ Kth-MinMax $ 容斥：
$$ Kth-MinMax(S) = \sum_{T \in S} C(|T| - 1, k - 1) (-1)^{|T| - k} min(T) $$
令 $ f[i][j][k] = (前i个元素中 \sum P_{a_i} = j)\sum_{T} C(|T| - 1, k - 1)(-1)^{|T| - k} $ 。考虑加入一个新元素：
不加：$ f[i][j][k] = f[i - 1][j][k] $ 。
加：
$$ f[i][j][k] = \sum_{T \in S} C(|T| - 1, k - 1) (-1)^{|T| - k} $$
$$ = \sum_{T}C(|T|, k - 1)(-1)^{|T| - k + 1} $$
$$ = \sum_{T}(C(|T| - 1, k - 1) + C(|T - 1|, k - 2))(-1)^{|T| - k + 1} $$
$$ = \sum_{T}C(|T| - 1, k - 1)(-1)^{|T| - k}(-1) + \sum_{T}C(|T| - 1, k - 2)(-1)^{|T| - k + 1} $$
$$ = -f[i - 1][j - P_i][k - 1] + f[i - 1][j - P_i][k] $$
$ f[i][0][0] = 1 $ 。
$ dp $ 转移即可（需要滚动数组），最后的 $ f[i][j][k] $ 期望为 $ \frac{m}{j} $ 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1010;
int n, m, k, p[N], ans = 0;
int fac[N], ifac[N];
int f[2][N * 10][N], Now = 0;

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) {
	return (int)((ll)x * y % mod);
}
int ksm(int x, int y = mod - 2) {
	int ss = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ss = mul(ss, x);
	return ss;
}
int C(int x, int y) {
	if(x < 0 || y < 0 || x < y) return 0;
	return mul(fac[x], mul(ifac[y], ifac[x - y]));
}
int main() {
	scanf("%d%d%d", &n, &k, &m), k = n - k + 1;
	for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
	fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
	for(int i = 2; i <= n; i++) fac[i] = mul(fac[i - 1], i);
	for(int i = 2; i <= n; i++) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
	for(int i = 2; i <= n; i++) ifac[i] = mul(ifac[i - 1], ifac[i]);
	f[Now][0][0] = 1;
	for(int i = 1; i <= n; i++) {
		Now ^= 1;
		for(int j = 0; j <= m; j++)
			for(int h = 0; h <= k; h++) f[Now][j][h] = f[Now ^ 1][j][h];
		for(int j = p[i]; j <= m; j++)
			for(int h = 1; h <= k; h++) {
				f[Now][j][h] = add(f[Now][j][h], f[Now ^ 1][j - p[i]][h - 1]);
				f[Now][j][h] = sub(f[Now][j][h], f[Now ^ 1][j - p[i]][h]);
			}
	}
	for(int i = 1; i <= m; i++) ans = add(ans, mul(f[Now][i][k], ksm(i)));
	printf("%d\n", mul(ans, m));
	return 0;
}