\(\text{1.}\) min-max 容斥引入
给定一个集合 \(S\) ，告诉其中每个元素单位时间出现概率，问每个元素至少出现一次的期望时间。
\(\text{2.}\) min-max 容斥相关
[1] 最初形式
\[\begin{align} \max(S)=\sum_{T \subseteq S} (-1)^{|T| - 1} \min(T) \tag{1} \end{align} \] \[\begin{align} \min(S)=\sum_{T \subseteq S} (-1)^{|T| - 1} \max(T) \tag{2} \end{align} \]上述式子的 \(S\) 和 \(T\) 都是两个集合，自然可以是由二进制数表示的集合。
当 \(\max\) 和 \(\min\) 中一个不好求，可以通过对对立的做子集容斥得到最终结果。
(1) 证明
首先将元素都从大到小进行排列。
对于排第 \(k\) 的元素，要其拥有贡献，那么，它必须是 \(T\) 中最小的一个。
所以剩下的数只能在 \(1 \sim k-1\) 中进行选择。
那么选取方案为就为 \(\dbinom{k-1}{|T|-1}\)
设集合大小为 \(1 \sim k\) ，则排第 \(k\) 的元素的总贡献为：
\[\sum_{i=1}^k \dbinom{k-1}{i-1} * g(i) = [k = 1] \]这样只有最大值对 \(\max\) 有贡献，于是就显然很对。
然后考虑二项式反演就能得到: \(g(k)=\sum_{i=1}^k (-1)^{k-i} \dbinom{k-1}{i-1} [i=1]\)
所以 \(g(k)=(-1)^{k-1}\) , 然后证完了。
(2) 证明
本质一样，改成将元素从小到大排序，然后证明同上。
[2] 扩展形式
这个还可以扩展到 \(\text{kth min-max}\) 。
\[\max_{k}(S) = \sum_{T \subseteq S , |T| > k} (-1)^{|T| - k} \dbinom{|T| - 1}{k - 1} \min(T) \]证明类似，先略去。
[3] 概率和期望层面的运用
\[E(max(S))=\sum_{T\subset S}(-1)^{|T|-1}E(min(T))\\ E(max_k(S))=\sum_{T\subset S}(-1)^{|T|-k}C(|T|-1,k-1)E(min(T))\]证明同样先略去，这个期望具有线性性质，于是很对。
\(\text{3.}\) min-max 的实际运用
题目一
一个数字从 \(0\) 开始,每次按位或上一个数 \(