My Blogs
核心公式
\[\begin{aligned} \max_{i\in S}x_i=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}\min_{j\in T}x_j\\ \min_{i\in S}x_i=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}\max_{j\in T}x_j\\ \end{aligned}\]证明：转换成容斥原理的一般（集合）形式。构造映射 $f:x \mapsto {i\vert i\leq x}$，则 $f(\min(x,y))=f(x)\cap f(y)$，$f(\max(x,y))=f(x)\cup f(y)$。代入上式，得到：
\(\begin{aligned} \max_{i\in S}x_i&=\lvert\bigcup_{i\in S}f(x_i)\rvert\\ &=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}\lvert\bigcap_{j\in T}f(x_j)\rvert\\ &=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}\min_{j\in T}x_j \end{aligned}\) 对于第二个公式同理。
看似没有什么用，但是其在期望意义下也是成立的，即：
\[\begin{aligned} E(\max_{i\in S}x_i)=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}E(\min_{j\in T}x_j)\\ E(\min_{i\in S}x_i)=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}E(\max_{j\in T}x_j)\\ \end{aligned}\]扩展
\[\begin{aligned} \mathrm{kth}\!\max_{i\in T}x_i&=\sum_{S\in T}(-1)^{\lvert S\rvert-k}\binom{\lvert S\rvert-1}{k-1}\min_{i\in T}x_i\\ \mathrm{kth}\!\min_{i\in T}x_i&=\sum_{S\in T}(-1)^{\lvert S\rvert-k}\binom{\lvert S\rvert-1}{k-1}\max_{i\in T}x_i\\ E(\mathrm{kth}\!\max_{i\in T}x_i)&=\sum_{S\in T}(-1)^{\lvert S\rvert-k}\binom{\lvert S\rvert-1}{k-1}E(\min_{i\in T}x_i)\\ E(\mathrm{kth}\!\min_{i\in T}x_i)&=\sum_{S\in T}(-1)^{\lvert S\rvert-k}\binom{\lvert S\rvert-1}{k-1}E(\max_{i\in T}x_i)\\ \end{aligned}\]证明好复杂。。不会。。
例题
P3175 [HAOI2015] 按位或
看出了 $\mathrm{Min-Max}$ 容斥就是板子题了。可以设 $x_i$ 变量为第 $i$ 位变成 $1$ 的时间。求得就是：
\[E(\max_{i\in S}x_i)\]直接套板子：
\[E(\max_{i\in S}x_i)=\sum_{T\subseteq S}(-1)^{\lvert T\rvert-1}E(\min_{j\in T}x_j)\]转成了 $\min$，这样就是“集合内第一个数变成 $1$” 的期望时间。可以设 $x=\sum_{T\cap S\not=\emptyset}a_T$，这样第一个数出现的期望就是：
\[E=x\sum_{i=0}^{\infty}(i-x)^i(i+1)\]用等比数列求和的套路变形两次就可以得到：
\[E=\frac 1 x\]多次求可以先求 $1-x$，即 $\sum_{T\cap S=\emptyset}a_T$，暴力是 $\mathcal O(3^n)$，用 FWT 优化到 $\mathcal O(n2^n)$。
P5643 [PKUWC2018] 随机游走
$\max$ 转成 $\min$，设 $g_i$ 表示从 $i$ 出发第一次到达 $T$ 中的点的期望步数。可以归纳证明对于任意的 $i$，$g_i$ 都可以表示成 $A_i+B_ig_{fa}$。证明如下：
若 $i\in T$，则 $g_i=0$。
若 $i$ 是叶子，则 $f_i=1+fa_i$。
否则 $g_i=1+\frac 1 {deg_i}(g_{fa}+\sum_{j\in son_i}A_j+B_jg_i)$。移项变形： \(\begin{aligned} deg_ig_i&=deg_i+g_{fa}+\sum_{j\in son_i}A_j+B_jg_i\\ (deg_i-\sum_{j\in son_i}B_j)g_i&=deg_i+g_{fa}+\sum_{j\in son_i} A_j\\ g_i&=\frac{deg_i+\sum_{j\in son_i}A_j}{deg_i-\sum_{j\in son_i}B_j}+\frac {g_{fa}}{deg_i-\sum_{j\in son_i}B_j} \end{aligned}\)
这样就不用 $\mathcal O(n^3) $ 暴力高消了。所以对于枚举所有集合 $T$，每个集合 dfs 一遍求出 $f_T$ 表示从给定起点开始走到 $T$ 中点的期望步数。预处理 $f_T(-1)^{\lvert T\rvert-1}$ 的 FWT 数组，查询 $\mathcal O(1)$，总复杂度 $\mathcal O(n2^n\log P+q)$。稍微有点卡常，求逆元可以改成 $\mathrm{exgcd}$。
P4707 重返现世
比较神的题，但是难点不在第一步转化。
设 $x_i$ 表示第 $i$ 种原料出现期望，就是求第 $k$ 小的期望。但是这样只能转成最大，但是我们希望转成最小。所以看成是求第 $n-k+1$ 大的期望。下记 $k$ 表示题目中的 $n-k+1$，要求的就是：
\[\sum_{T}(-1)^{\lvert T\rvert -1}\binom{\lvert T\rvert -1}{k-1}E(\min_{i\in T}x_i)\]式中最后的期望就是 $\frac 1 {\sum_{i\in T}p_i}$。但是这里 $n$ 开到了 $1000$，肯定不能枚举子集。把上面的组合数拆开：
\[\sum_{T}(-1)^{\lvert T\rvert -1}\frac{(\lvert T\rvert -1)^{\underline{k-1}}}{(k-1)!}\frac 1 {\sum_{i\in T}p_i}\]所以可以设 $f_{i,j,k}$ 表示考虑了前 $i$ 个原料，$T$ 的大小为 $j$，$\sum_{i\in T} p_i$ 为 $k$，然后就发现爆了。
$k$ 非常的小。这里有一步很厉害的转化。有组合恒等式：
\[\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}\]这样如果 $\lvert T\rvert$ 增加了 $1$，可以从 $k-1$ 和 $k$ 转移。所以设 $f_{i,j,k}$ 表示考虑了 $i$ 个原料，$\sum_{x\in T}p_x=j$ 时 $(-1)^{\lvert T\rvert-k}\binom{\lvert T\rvert -1}{k-1}$ 之和。推一下转移方程：
\[\begin{aligned} f_{i,j+p_i,k}&=(-1)^{\lvert T\rvert-k+1}\binom{\lvert T\rvert}{k-1}\\ &= -(-1)^{\lvert T\rvert-k}\binom{\lvert T\rvert-1}{k-1}+(-1)^{\lvert T\rvert-k+1}\binom{\lvert T\rvert-1}{k-2}\\ &=-f_{i-1,j,k}+f_{i-1,j,k-1}\\ f_{i,j,k}&=f_{i-1,j,k} \end{aligned}\]边界是 $f_{0,0,0}=1$，总复杂度 $\mathcal O(nm(n-k))$。
总结
$\mathrm{Min-Max}$ 容斥的题感觉都比较套路，而且大部分都有非常明显的提示，比如 $\min$ 好求 $\max$ 不好求或者相反。