LG4707 重返现世(扩展 min-max 容斥)

题目链接

洛谷

题意简述

有 $n$ 种颜色,每秒会出现一种颜色,第 $i$ 种颜色出现概率为 $\frac{p_i}m$,其中 $m=\sum_{i=1}^np_i$,求共出现 $k$ 种颜色的期望用时,对 $998244353$ 取模。

$1\le k\le n\le 1000$,$m\le10000$,$k\ge n-10$。

简要做法

扩展 min-max 容斥

$$
k\operatorname{-thmax}(S)=\sum\limits_{T\subseteq S}[T\ne\varnothing] (-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)
$$

其中 $k\operatorname{-thmax}(S)$ 表示 $S$ 这个集合的第 $k$ 大元素,$\min(T)$ 表示 $T$ 这个集合中最小的元素。

证明可以使用二项式反演,不会二项式反演也记不住式子的话,考场现推可以设 $k\operatorname{-thmax}(S)=\sum_{T\subseteq S}[T\ne\varnothing]f(|T|)\min(T)$ 然后算。

这个式子还可以推广到期望,“第 $k$ 大的期望”意思是 $\sum_xx\cdot p(x=k\operatorname{-thmax}(S))$。($p(event)$ 表示事件 $event$ 发生的概率。)

重返现世

下文中用 $K$ 代表 $n-k+1$。

答案就是颜色出现时间的第 $K$ 大的期望。
$$
ans = \sum\limits_{T\subseteq S}[T\ne\varnothing] (-1)^{|T|-K}\binom{|T|-1}{K-1}\frac m{sum(T)}
$$
其中 $sum(T)$ 表示 $\sum_{i\in T}p_i$,$\min(T)=\frac{m}{sum(T)}$ 可以这样理解:计算 $T$ 中元素最早出现时间的期望,可以将 $T$ 中所有颜色绑在一起,出现概率就是 $\frac{sum(T)}m$,期望出现时间就是其逆元。

接下来是一个神奇的 dp。

令 $f_{i,j,k}$ 表示 $\sum_{T\subseteq[1,i]}[sum(T)=j\ne0] (-1)^{|T|-k}\binom{|T|-1}{k-1}$。(这里的 $k$ 与题目输入中的 $k$ 不同。)

考虑转移,分两种情况:

  1. $T$ 不包含 $i$;
  2. $T$ 包含 $i$。

第一种情况显然是 $f_{i-1,j,k}$。

在 $j>p_i$ 时,将 $i$ 这个元素从 $T$ 中拿出来,剩下的部分依然不是空集,所以第二种情况的式子是 $\sum_{T\subseteq[1,i-1]}[sum(T)=j-p_i] (-1)^{|T|+1-k}\binom{|T|}{k-1}$。

尝试从之前的状态转移,写出两个式子:
$$
f_{i-1,j-p_i,k-1}=\sum\limits_{T\subseteq[1,i-1]}[sum(T)=j-p_i] (-1)^{|T|+1-k}\binom{|T|-1}{k-2}
$$

$$
f_{i-1,j-p_i,k}=\sum\limits_{T\subseteq[1,i-1]}[sum(T)=j-p_i] (-1)^{|T|-k}\binom{|T|-1}{k-1}
$$

发现最后的组合数部分就是杨辉三角中计算组合数的方法($\binom{x}{y}=\binom{x-1}{y-1}+\binom{x-1}{y}$),而前面只是正负号的变化。

也就是说,$j>p_i$ 时,第二部分的值为 $f_{i-1,j-p_i,k-1}-f_{i-1,j-p_i,k}$。

为什么要强调 $j>p_i$ 呢?因为枚举 $T\subseteq S$ 时是 不包含空集 的。所以,当 $j=p_i$ 时,第二种情况需要特殊计算,直接将 $T=\{i\}$ 代入定义式,得到第二部分的值为 $(-1)^{1-k}\binom{0}{k-1}$,也就是 $k=1$ 时为 $1$,否则为 $0$。

总结一下:$f_{i,j,k}=\begin{cases}f_{i-1,j,k}&(j<p_i)\\f_{i-1,j,k}+[k=1]&(j=p_i)\\f_{i-1,j,k}+f_{i-1,j-p_i,k-1}-f_{i-1,j-p_i,k}&(j>p_i)\end{cases}$

dp 的边界情况是什么?其实除了 $i\ge 1,1\le j\le m,1\le k\le i$(当然这些情况里也有很多 $0$),其它情况都可以由定义计算得到是 $0$。

最后的答案就是 $\sum_{i=1}^mf_{n,i,K}\frac{m}{i}$。

需要用滚动数组优化空间。

参考代码

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
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 1010;
const int M = 10010;
const int K = 15;
const int mod = 998244353;

int n, m, k, p[N], f[M][K], ans;

int qpow(int x, int y)
{
int out = 1;
while (y)
{
if (y & 1) out = (ll) out * x % mod;
x = (ll) x * x % mod;
y >>= 1;
}
return out;
}

int main()
{
scanf("%d%d%d", &n, &k, &m);

for (int i = 1; i <= n; ++i)
{
scanf("%d", p + i);
}

k = n - k + 1;

for (int i = 1; i <= n; ++i)
{
for (int j = k; j >= 1; --j)
{
for (int s = m; s > p[i]; --s)
{
f[s][j] = (0ll + f[s][j] + f[s - p[i]][j - 1] - f[s - p[i]][j] + mod) % mod;
}
}
f[p[i]][1] = (f[p[i]][1] + 1) % mod;
}

for (int i = 1; i <= m; ++i) ans = (ans + (ll) f[i][k] * m % mod * qpow(i, mod - 2)) % mod;

cout << ans;

return 0;
}

如果枚举包含空集

如果我们将 dp 状态定义成枚举包含空集,也是可以算的。

令 $f_{i,j,k}$ 表示 $\sum_{T\subseteq[1,i]}[sum(T)=j] (-1)^{|T|-k}\binom{|T|-1}{k-1}$。

还是分成不包含 $i$ 和包含 $i$ 两部分。

第一部分依然是 $f_{i-1,j,k}$。

第二部分不需要分 $j$ 与 $p_i$ 的关系讨论,直接 $f_{i-1,j,k}+f_{i-1,j-p_i,k-1}-f_{i-1,j-p_i,k}$。

但是边界情况需要注意:

$$
f_{i,0,k}
=(-1)^{-k}\binom{-1}{k-1}=
\begin{cases}
0&k=0\\
-1&otherwise
\end{cases}
$$

(注:$\binom{-1}{k-1}$ 可以由广义组合数 $\binom{x}{y}=\frac{x(x-1)\cdots(x-y+1)}{y!}$得到。)

代码:

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
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 1010;
const int M = 10010;
const int K = 15;
const int mod = 998244353;

int n, m, k, p[N], f[M][K], ans;

int qpow(int x, int y)
{
int out = 1;
while (y)
{
if (y & 1) out = (ll) out * x % mod;
x = (ll) x * x % mod;
y >>= 1;
}
return out;
}

int main()
{
scanf("%d%d%d", &n, &k, &m);

for (int i = 1; i <= n; ++i)
{
scanf("%d", p + i);
}

k = n - k + 1;

for (int i = 1; i <= k; ++i) f[0][i] = mod - 1;

for (int i = 1; i <= n; ++i)
{
for (int j = k; j >= 1; --j)
{
for (int s = m; s >= p[i]; --s)
{
f[s][j] = (0ll + f[s][j] + f[s - p[i]][j - 1] - f[s - p[i]][j] + mod) % mod;
}
}
}

for (int i = 1; i <= m; ++i) ans = (ans + (ll) f[i][k] * m % mod * qpow(i, mod - 2)) % mod;

cout << ans;

return 0;
}