「P4707」重返现世 - ex Min-Max容斥 + DP

题目

简要题意

n 个物品, 第 i 个时刻出现第 j 个物品的概率为 p_j , 其中 \sum_{i = 1}^n p_i = 1 , 求出现了 k 种物品的期望时间

题目描述

为了打开返回现世的大门,Yopilla 需要制作开启大门的钥匙。Yopilla 所在的迷失大陆有 n 种原料,只需要集齐任意 k 种,就可以开始制作。

Yopilla 来到了迷失大陆的核心地域。每个单位时间,这片地域就会随机生成一种原料。每种原料被生成的概率是不同的,第 i 种原料被生成的概率是 \frac{p_i}{m} 。如果 Yopilla 没有这种原料,那么就可以进行收集。

Yopilla 急于知道,他收集到任意 k 种原料的期望时间,答案对 998244353 取模。

输入格式

第一行三个数 n, k, m

第二行 n 个数 p_1, p_2, ..., p_n

输出格式

输出一行

输入输出样例

输入 #1

1
2
3 3 3
1 1 1

输出 #1

1
499122182

说明 / 提示

对于 10 \% 的数据, p_1 = p_2 = ... = p_m

对于另外 10 \% 的数据, k = n

对于 70 \% 的数据, n \le 100

对于 100 \% 的数据, 1 \le n \le 1000 1 \le k \le n, \lvert n - k \rvert \le 10 0 \le p_i \le m, \sum p = m, 1 \le m \le 10000

题解

ex Min-Max容斥:

K\text {-th max} (S) = \sum _ {\varnothing \neq T\subseteq S}{|T|-1\choose k-1} (-1)^{|T|-k} \min(T)

考虑 dp 表示集合的系数, 也就是设 dp_{i,j,k} 表示前 i 个物品构成的集合中概率为 j 的集合的系数. 考虑如何进行递推

根据组合数递推, 我们得到

{|T| - 1 \choose k - 1} = {|T| - 2 \choose k - 1} + {|T - 2| \choose k - 2}

在 dp 中, 前一项的系数为正的, 而后一项的系数为负, 故我们有 dp _ {i , j , k} = dp_{i − 1, j − p_i, k − 1} − dp_{i − 1, j − p _ i, k}

Code

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
#define int long long

const int mod = 998244353;

const int N = 1000 + 10;
const int M = 10010;

int n, m, k;

int v[N];
int inv[M];

// int dp[2][M][20];
int dp[M][20];
int ans;

void pre () {
inv[1] = 1;
up(i, 2, m) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

int pow (int base, int p) {
int ret = 1;
while (p) {
if (p & 1) ret = ret * base % mod;
base = base % base % mod; p = p >> 1;
}
return ret;
}

signed main() {
n = read(); k = n - read() + 1; m = read();
pre();
up (i, 1, n) v[i] = read();
up (i, 1, n) {
down (j, k, 1)
down (s, m, v[i] + 1) dp[s][j] = (dp[s][j] + dp[s - v[i]][j - 1] - dp[s - v[i]][j] + mod) % mod;
dp[v[i]][1] = (dp[v[i]][1] + 1) % mod;
}
up (i, 1, m) ans = (ans + (dp[i][k] * m) % mod * inv[i] % mod) % mod;
print((ans % mod + mod) % mod);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!