LG4707 重返现世（扩展 min-max 容斥）

题目链接

洛谷

题意简述

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

$1\le k\le n\le 1000$，$m\le 10000$，$k\ge n-10$。

简要做法

扩展 min-max 容斥

$$k\text{-}thmax\left(S\right)=\sum _{T\subseteq S,T\ne \varnothing }(-1{)}^{|T|-k}(\frac{|T|-1}{k-1})min(T)$$

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

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

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

重返现世

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

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

接下来是一个神奇的 dp。

令 $f_{i,j,k}$ 表示 $\sum _{T\subseteq [1,i],sum\left(T\right)=j\ne 0}(-1{)}^{|T|-k}(\frac{|T|-1}{k-1})$。（这里的 $k$ 与题目输入中的 $k$ 不同。）（$j=0$ 时依然是良定义的，其值为 $0$。）

考虑转移，分两种情况：

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

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

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

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

$$f_{i-1,j-p_i,k}=\sum _{T\subseteq [1,i-1],sum\left(T\right)=j-p_i}(-1{)}^{|T|-k}(\frac{|T|-1}{k-1})$$

发现最后的组合数部分就是杨辉三角中计算组合数的方法（$(\frac{x}{y})=(\frac{x-1}{y-1})+(\frac{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=\left\{i\right\}$ 代入定义式，得到第二部分的值为 $(-1{)}^{1-k}(\frac{0}{k-1})$，也就是 $k=1$ 时为 $1$，否则为 $0$。

总结一下：$f_{i,j,k}=\{\begin{array}{cc}{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{array}$

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

最后的答案就是 $\sum _{i=1}^m{f}_{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\left(T\right)=j}(-1{)}^{|T|-k}(\frac{|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}(\frac{-1}{k-1})=\{\begin{array}{cc}0& k=0\\ -1& otherwise\end{array}$$

（注：$(\frac{-1}{k-1})$ 可以由广义组合数 $(\frac{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; }