$\min$-$\max$容斥
因为讲了这个... 并且把 PPT 和 PDF 也一起发上来了.
前置知识
二项式反演.
例题
$\min$-$\max$ 容斥
$$ \max\{S\}=\sum_{S\supseteq T}(-1)^{|T|-1}\min\{S\}\\ \min\{S\}=\sum_{S\supseteq T}(-1)^{|T|-1}\max\{S\} $$
也有将 $|T|-1$ 写成 $|T|+1$ 的, 不过显然对结果没有影响.
理解一下这个式子, 其中 $S$ 和 $T$ 显然应该是两个集合 (当然也可以是二进制数表示的集合). 有了这个式子, 对于很难求 $\max$ 的集合也可以通过求子集 $\min$ 来容斥出最终的结果.
证明
设存在容斥系数 $f(x)$ 满足
$$ \max\{S\}=\sum_{S\supseteq T}(f|T|)\min\{T\} $$
则第 $i+1$ 大 (即有 $i$ 个元素比它大) 的元素的贡献是
$$ [i=0]=\sum_{j=0}^i\binom ijf(j+1) $$
理解一下这个式子.
- 对于右边: 首先钦定 $i+1$ 大的元素是 $\min$, 然后枚举集合剩下的元素个数, 再从比 $i+1$ 大的 $i$ 个元素中选出对应的个数, 最后乘上容斥系数 $f(j+1)$,$j+1$ 是集合大小.
- 对于左边: 窝们希望这个式子在最大 (即第 $0+1$ 大) 的元素处才有贡献, 其它比较小的都应该被消掉.
然后进行二项式反演
$$ f(i+1){=\sum_{j=0}^i(-1)^{i-j}\binom ij[j=0]\\ =(-1)^i } $$
化简得到
$$ f(x)=(-1)^{x-1} $$
类似地, 第二个式子也成立.
一个比较取巧的想法: 将大小顺序反过来. 当然要是想像之前那样写一堆式子来证也能证出来.
期望下的 $\min$-$\max$ 容斥
$$ \mathrm E(\max\{S\})=\sum_{S\supseteq T}(-1)^{|T|-1}\mathrm E(\min\{S\})\\ \mathrm E(\min\{S\})=\sum_{S\supseteq T}(-1)^{|T|-1}\mathrm E(\max\{S\}) $$
$\min$-$\max$ 容斥在期望下也成立, 这里需要用到期望的线性性:
$$ \mathrm E(\alpha X+\beta Y)=\alpha\mathrm E(X)+\beta\mathrm E(Y) $$
这个式子的证明要用到定积分的知识, 因为期望本质上是积分, 期望的线性性即是积分的线性性, 但是这个式子窝是真的不会证 (笑).
这个式子的意义在于期望是不能放到 $\min$ 和 $\max$ 里面去的, 比如有两个无关变量 $X$ 和 $Y$,$\mathrm E(\max\{X,Y\})\not=\max\{\mathrm E(X),\mathrm E(Y)\}$.
举例: 抛两枚硬币 $X$ 和 $Y$,$1$ 表示正面朝上, 则 $\mathrm E(X)=\mathrm E(Y)=\max\{\mathrm E(X),\mathrm E(Y)\}=0.5$, 而 $\mathrm E(\max\{X,Y\})=0.75$.
所以对于期望下的 $\min$ 和 $\max$ 不能直接暴力地拆开去求, 但是现在我们有了 $\min$-$\max$ 容斥, 就可以比较方便地求出期望下的 $\min$ 和 $\max$ 了.
推广 $k^\text{th}\min\min$-$\max$ 容斥
$$ \max_k\{S\}=\sum_{S\supseteq T}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min\{S\}\\ \min_k\{S\}=\sum_{S\supseteq T}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max\{S\} $$
$\max_k$($\min_k$)分别表示第 $k$ 大 (小) 元素.
证明
用同样的思路, 设容斥系数 $f(x)$ 满足
$$ \max_k\{S\}=\sum_{S\supseteq T}f(|T|)\min\{S\} $$
考虑第 $i+1$ 大元素的贡献
$$ [i=k-1]=\sum_{j=0}^i\binom ijf(j+1) $$
窝们这次希望这个式子只在第 $i+1=k$ 大的元素处有贡献, 所以用类似的方法枚举剩下的集合大小.
二项式反演
$$ f(i+1){=\sum_{j=0}^i(-1)^{i-j}\binom ij[j=k-1]\\ =(-1)^{i-k+1}\binom i{k-1} }\\ f(x)=(-1)^{x-k}\binom{x-1}{k-1} $$
同样就懒得证第二个式子了.
推广 期望下的 $k^\text{th}\min$-$\max$ 容斥
$$ \mathrm E(\max\{S\})=\sum_{S\supseteq T}(-1)^{|T|-1}\mathrm E(\min\{S\})\\ \mathrm E(\min\{S\})=\sum_{S\supseteq T}(-1)^{|T|-1}\mathrm E(\max\{S\}) $$
是的 $k^\text{th}\min$-$\max$ 容斥在期望下也成立.