min-max 容斥小记
\(\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\) 开始,每次按位或上一个数 \(?? \in [0, 2^n-1]\) , 其中 \(??\) 出现的概率是 \(??_??\) 。
求期望多少次后该数变为 \(2^?? ? 1\) 。
\(\text{Data range:} n \le 20, 0 \le p_i \le 1, \sum p_i = 1\)
设 \(\min(S)\) 表示二进制数 \(S\) 中第一个元素变为 \(1\) 所需时间, \(\max(S)\) 表示最后一个元素变为 \(1\) 所需时间。
题目即求 \(E(\max(U)), U=2^n-1\) 。
根据结论有，期望也满足 min-max 容斥形式，直接套式子，求 \(E(\min(S))\) 。
设 \(f(S)\) 表示 \(S\) 中至少出现一位时的期望步数，也就是 \(E( \min(S) )\) 。
\[f(S) = 1 + \sum_{T \cap S = \emptyset} p(t)f(S) \]考虑操作一步，代价就是 \(1\)， 如果选到与 \(S\) 无交集的 \(T\) 就仍然需要花费 \(f(S)\) 的代价，选到有交集的就结束，因为这个没有贡献。
然后这个东西其实就是考虑一个成功的概率为 \(p\) ，那么步数就是 \(\dfrac{1}{p}\) ，如下：
\[E(x)=1+(1-p)E(x) \]\[\Rightarrow E(x)=\frac{1}{p} \]所以得到 \(f(S) = \dfrac{1}{\sum_{T \cap S \neq \emptyset p(T) }}\) 。
然后下面那一坨直接 \(FWT\) 预处理子集和，然后用全集 \(1\) 减去就是了，然后剩下的就是套式子。然后直接做就是了。
题目二
\(n\) 种原料，第 \(i\) 种原料被生成的概率是 \(\dfrac{p_i}{m}\) 。
求收集到任意 \(k\) 种原料的期望时间，答案对 \(998244353\) 取模。
\(\text{Data Range:} 1 \leq k \leq n \leq 1000, |n-k|\leq 10, 0 \leq p_i \leq m, \sum p_i = m, 1 \le m \le 10000\) 。
这题其实就一个 \(\text{kth min-max}\) ，关键在于后面的那个 dp 确实挺神仙的。不过至少这题思路还是很显然的/hanx 。
直接考虑列期望式子，和 \(\text{min-max}\) 容斥。
\[E(max_k(S))=\sum_{T\subset S}(-1)^{|T|-k}C(|T|-1,k-1)E(min(T)) \]我擦，nmd 好多式子，我不想列了，反正这题也不是我自己推出来的，去看 sooke 哥哥的题解吧！！
https://www.luogu.com.cn/blog/Sooke/solution-p4707#
题目三
给定一棵 \(n\) 个结点的树，你从点 \(x\) 出发，每次等概率随机选择一条与所在点相邻的边走过去。
有 \(Q\) 次询问，每次询问给定一个集合 \(S\)，求如果从 \(x\) 出发一直随机游走，直到点集 \(S\) 中所有点都至少经过一次的话，期望游走几步。
特别地，点 \(x\)（即起点）视为一开始就被经过了一次。
答案对 \(998244353\) 取模。
显然考虑 \(\text{min-max}\) 容斥，直接设 \(\min\) 表示点集中第一个被经过的期望步数， \(\max\) 表示点集中点都被经过的期望步数。
直接容斥。考虑设立 \(\text{dp}\) , \(f_{s,i}\) 表示从 \(i\) 出发，经过 \(s\) 中至少一个点的期望步数。
可以高斯消元，但是会超时，由于形态特殊，这是个树，利用树的性质，待定系数法之后可以变成一个树形 dp 。 最后 FWT 卷一下就好了。
因为事情很多这个题解就写的不详细，但是网上有写的比蒟蒻详细的多的说 qwq ，可以去看 Marser 哥哥的题解。
https://www.luogu.com.cn/blog/Marser/solution-p5643