【组合数学】min-max 容斥

min-max 容斥

对于一个长度为 \(n\) 数列 \(\left \{ a_i \right \}\)，有如下式子：

\[\max_{i=1}^{n} \left \{ a_i \right \}=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} \min_{j \in T} \left \{ a_{j} \right \}\]

\[\min_{i=1}^{n} \left \{ a_i \right \}=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \} }(-1)^{\left | T \right | -1} \max_{j \in T} \left \{ a_{j} \right \}\]
以上计算过程称作 min-max 容斥，也叫最值反演，证明过程参考的 OI Wiki，把该计算过程用一般的容斥原理表示出来即可证明，考虑构造双射 \(f(x)=\left \{ 1,2,\cdots ,x \right \}\)，显然 \(x=\left | f(x)\right |\)，\(\min \left \{ x,y\right \}=\left | f(x) \cap f(y) \right |\)，\(\max \left \{ x,y\right \}=\left | f(x) \cup f(y) \right |\)。于是得到如下式子：

\[\max_{i=1}^{n} \left \{ a_i \right \}=\left | \bigcup_{i=1}^{n} f(a_i) \right |\]

\[=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} \left | \bigcap_{j \in T}f(a_j) \right |\]

\[=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} \min_{j \in T} \left \{ a_{j} \right \}\]
证毕，min 的计算过程的证明与 max 的一样。
min-max 容斥求解数学期望

前置知识：数学期望具有线性性质

对于两个变量 \(x\) 和 \(y\)，以及两个常数 \(a\) 和 \(b\)，有如下线性性质：

\[E(ax+by)=aE(x)+bE(y)\]
因此，min-max 容斥可带入到期望的计算当中：

\[E(\max_{i=1}^{n} \left \{ a_i \right \})=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | T \right | -1} E(\min_{j \in T} \left \{ a_{j} \right \})\]
前置知识：离散随机变量的几何分布

假设一个变量 \(x\) 表示实验第一次成功的实验次数，实验成功的概率为 \(p\)，显然：

\[P(x=k)=p(1-p)^{k-1},k \in \mathbb{N}^{+}\]
则变量 \(x\) 的数学期望为：

\[E(x)=\sum_{i=1}^{\infty}i\cdot p(1-p)^{i-1}=p\sum_{i=1}^{\infty}i(1-p)^{i-1}\]
考虑如何化简此式，我们知道几何级数：

\[\sum_{n=0}^{\infty}x^n=\frac{1}{1-x}\]
这个可以由等比数列求和直接求得，该式只在 \(x \in [0,1)\) 成立，因为该式只在 \(x \in [0,1)\) 时收敛，对等式两边同时求导，得到如下式子：

\[\sum_{n=1}^{\infty} nx^{n-1}=\frac{1}{(1-x)^2}\]
代入 \(E(x)\) 得：

\[E(x)=p\cdot \frac{1}{p^2}=\frac{1}{p}\]
问题一

描述：
有 \(n\) 张卡牌，每张卡牌的数字都不一样，背面都一样，将所有卡牌背面朝上放在桌子上，从中随机抽取一张记下其数字，然后放回，需要抽 \(k\) 次卡牌才可以看到所有的数字，求 \(E(k)\)，时间复杂度要求 \(O(n)\)。
思路：
设 \(T_i\) 表示第一次看到第 \(i\) 张卡牌的次数，则有如下：

\[E(k)=E(\max_{i=1}^{n} \left \{ T_i \right \})\]

\[=\sum_{S \subseteq \left \{ 1,2,\cdots,n\right \}}(-1)^{\left | S \right | -1} E(\min_{j \in S} \left \{ T_{j} \right \})\]
考虑如何求 \(E(\min_{j \in S} \left \{ T_{j} \right \})\)，\(\min_{j \in S} \left \{ T_{j} \right \}\) 表示第一次抽取到集合 \(S\) 的卡牌的抽取次数，考虑几何分布，其期望值即为抽到集合 \(S\) 中任意一张卡牌的概率的倒数，如下：

\[E(\min_{j \in S} \left \{ T_{j} \right \})=\frac{n}{\left | S \right |}\]
带入原式，改变枚举方式，枚举子集大小，得到如下式子：

\[E(k)=n\sum_{i=1}^{n}\binom{n}{i}(-1)^{i-1}\frac{1}{i}\]
化简到这里已经足够了，如果你有一定的高等数学基础，这个式子还可以继续化简，就得到了如下式子（不再说明计算过程）：

\[E(k)=n\sum_{i=1}^{n}\frac{1}{i}\]
问题二（[HAOI2015] 按位或）

描述：
有一个变量 \(x\) ，最初 \(x=0\)，接下来每次操作从区间 \([0,2^n-1]\) 当中选择一个整数，然后 \(x \gets x \operatorname{or} i\)，\(\operatorname{or}\) 表示按位或操作，选择整数 \(i\) 的概率为 \(p_i\)，需要 \(k\) 次才能使 \(x=2^n-1\)，求 \(E(k)\)，\(n \le 20\)。
思路：
当 \(x=2^n-1\) 时，其二进制形式下的有 \(n\) 位且都是 \(1\)，设 \(T_i\) 表示 \(x\) 在二进制形式下第 \(i\) 位是 \(1\) 的操作次数，\(E(k)\) 表示为如下：

\[E(k)=E(\max_{i=0}^{n-1} \left \{ T_i \right \})\]

\[=\sum_{S \subseteq \left \{ 0,1,\cdots,n-1 \right \}}(-1)^{\left | S \right | -1} E(\min_{j \in S} \left \{ T_{j} \right \})\]
其中 \(E(\min_{j \in S} \left \{ T_{j} \right \})\) 同样可以由几何分布得出，如下：

\[E(\min_{j \in S} \left \{ T_{j} \right \})=\frac{1}{\sum_{G \subseteq{S}} p_{f(G)}}\]
其中 \(f(G)=\sum2^{G_i}\)，即 \(G\) 所表示的原数，这里需要提前预处理出所有集合的子集和，可以考虑 SOS DP，也可以考虑 FMT，最后直接枚举就行了，时间复杂度为 \(O(n2^n)\)。

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除