Min-Max 容斥小记
Min-Max 容斥
对于集合 \(S\)，定义 \(\max(S)=\max_{x\in S} x\)，同理可以定义 \(\min(S)\)。Min-Max 容斥给出了以下结论：
\[\max(S)=\sum _{T\subseteq S} (-1)^{|T|-1}\min(T)
\]
对 \(\min\) 也同理。
证明：考虑对 \(x\in S\)，若其为第 \(k\) 小元素，那么定义一个从 \(x\) 到 \(\{1,2,\dots,k\}\) 的映射 \(f(x)\)，显然这是一个双摄。发现 \(f(\min(x,y))=f(x)\cap f(y)\)，\(f(\max(x,y))=f(x)\cup f(y)\)，利用容斥原理得到：
\[\begin{aligned}
|f(\max(S))|=\sum _{T\sube S} (-1)^{|T|-1}|f(\min(T))|
\end{aligned}
\]
再把 \(|f(\max(S))|\) 映射回 \(\max(S)\) 即可，\(\min\) 也是类似的。
Min-Max 容斥在期望下也成立
这是很重要的。记 \(E(\max(S))\) 表示集合 \(S\) 内元素的最大值的期望。则
\[E(\max(S))=\sum_{T\sube S} (-1)^{|T|-1}E(\min(T))
\]
这个式子很有用，因为期望下的 \(\max\) 并不好求，有时 \(E(\max(a,b))\ne \max(E(a),E(b))\)。例如抛硬币游戏中，\(E(a)=E(b)=\frac12\)，\(E(\max(a,b))=0.75\ne \max(E(a),E(b))\)。
例子：P5643 [PKUWC2018] 随机游走
记 \(S\) 为包含所有关键点到达时间的集合，我们要求经过所有关键点至少一次的期望时间，即 \(E(\max(S))\)。
根据 Min-Max 容斥得到：
\[E(\max(S))=\sum_{T\sube S} (-1)^{|T|-1}E(\min(T))
\]
那么 \(E(\min(T))\) 的实际意义就是达到 \(T\) 中任意一个点的期望时间。