min-max 容斥 笔记

前言

min-max 容斥是一类特殊的容斥形式，其特殊性在于各种数值与计数的结合。

一般来说，在解题时，如果一些值的 \(\min\) 不好算，而这些值的 \(\max\) 相对好算（或者相反），

则这时我们可以使用 min-max 容斥，在两种不同的问题形式间进行转换。

一. 定义式

对一个数集 \(S\)，我们定义 \(\max(S)\) 为 \(S\) 中最大的元素值，\(\min(S)\) 为 \(S\) 中最小的元素值。

则对任意数集 \(S\)，我们都有以下恒等式成立：

\(\large\max(S)=\sum\limits_{T\subseteq S,T\ne\varnothing}(-1)^{|T|-1}\min(T)\)。

二. 证明

我们用类似待定系数法的思想证明以上恒等式。

设 \(\max(S)=\sum\limits_{T\subseteq S,T\ne\varnothing}f(|T|)\min(T)\)，其中 \(f\) 是我们需要解的容斥系数。

考虑将 \(\max(S)\) 拆解，即 \(\max(S)=\sum\limits_{u\in S}ux_{S,u}\)，其中 \(x_{S,u}=[u=\max(S)]\)。

我们也将 \(\min(S)\) 拆解，即 \(\min(S)=\sum\limits_{u\in S}uy_{S,u}\)，其中 \(y_{S,u}=[u=\min(S)]\)。

那么，对 \(\forall u\in S\)，我们必须有 \(x_{S,u}=\sum\limits_{T\subseteq S,T\ne\varnothing}f(|T|)y_{T,u}\)，

否则我们取 \(S\) 为一组基底（例如一组超越数组成的集合），就能让 \(f\) 不满足其定义。

我们设 \(u\) 是数集 \(M\) 中第 \(r(M,u)\) 大的数（默认 \(u\in M\)），那么由 \(x\) 和 \(y\) 的定义，我们不难证明：

\([r(S,u)=1]=\sum\limits_{T\subseteq S,T\ne\varnothing}f(|T|)[r(T,u)=|T|]\)。

考虑有多少个大小为 \(i\) 的数集 \(T\subseteq S,T\ne\varnothing\)，满足 \(r(T,u)=i\)，用排列组合得有 \(\dbinom{r(S,u)-1}{i-1}\) 个。

此时，上面的等式已经只与 \(|T|\) 有关，则等式可以重新写成枚举 \(i\) 作为 \(S\) 子集大小的形式：

\([r(S,u)=1]=\sum\limits_{i=1}^{r(S,u)}\dbinom{r(S,u)-1}{i-1}f(i)\)。

记 \(m=r(S,u)-1\)，我们可以写出一个简洁明了的形式：

\([m=0]=\sum\limits_{i=0}^{m}\dbinom{m}{i}f(i+1)\)。

记 \(g(i)=[i=0]\)，发现上式具有二项式反演的形式，即：

\(g(m)=\sum\limits_{i=0}^{m}\dbinom{m}{i}Ef(i)\)，

则由二项式反演，我们有：

\(Ef(m)=\sum\limits_{i=0}^m(-1)^{m-i}\dbinom{m}{i}g(i)\)。

整理一下，得：

\(f(m+1)=\sum\limits_{i=0}^m(-1)^{m-i}\dbinom{m}{i}[i=0]=(-1)^m\)，故 \(f(m)=(-1)^{m-1}\)。

将容斥系数 \(f\) 带回原式，我们也就得到了我们要证明的恒等式。

三. 应用

例题：ABC242H

做法：

定义 \(x(i)\) 为点 \(i\) 被覆盖的期望操作次数，

则对集合 \(S\)，令 \(\max(S)=\max\{x(u)|u\in S\}\)，\(\min(S)=\min\{x(u)|u\in S\}\)，

由期望的线性性，可得集合 \(S\) 也满足篇首的恒等式，那问题就转化为求以下式子的值：

\(max(U)=\sum\limits_{T\subseteq U,T\ne\varnothing}(-1)^{|T|-1}\min(T)\)，其中 \(U\) 代表全集。

又因为，设 \(c(S)\) 为所有不包含 \(S\) 中任何点的区间数，则我们不难得到 \(\min(S)=\frac{M}{M-c(S)}\)。

故我们发现，所求式右边只与 \(c(T)\) 的值，以及 \(|T|\) 的奇偶性有关，而这两个值的值域都有限，

故这时考虑用 DP 解决问题。

记 \(f(i,j,flg)\) 代表，考虑了 \(U\) 中前 \(i\) 个点，此时有多少个 \(T\) 满足：

\(i\in T,c(T)=j,|T|\equiv flg\) \(\mod2\)。

我们人为地加一个点 \(n+1\)，则答案就是 \(\sum\limits_{j,flg}(-1)^{flg}\frac{M}{M-j}f(n+1,j,flg)\)。

这样的时间复杂度是 \(O(N^3)\) 的，瓶颈在于转移时枚举上一个选取的点 \(k\)。

最后给出期望线性性的一种证明。

定义：

\(E(X+Y)=E(X)+E(Y)\)

证明：

\(E(aX)=\sum\limits_{i}ax_ip_i=a\sum\limits_{i}x_ip_i=aE(X)\)

取 \(a=\frac{X+Y}{X}\)，我们有：

\(E(X+Y)=E(X\cdot\frac{X+Y}{X})\)

\(=\frac{X+Y}{X}\cdot E(X)=E(X)+\frac{Y}{X}E(X)\)

\(=E(X)+E(X\cdot\frac{Y}{X})=E(X)+E(Y)\)。