【学习笔记】min-max 容斥

前言

这东西看起来我早就会了，只是一直没有理解其原理。/kk

对于一个集合 $S$，设 $\max(S)$ 为集合中的最大元素，$\min(S)$ 为集合中的最小元素。则有：

$$ \max(S)=\sum_{T\subseteq S} (-1)^{|T|+1}\min(T) $$

反过来也成立。

考虑证明。设 $x=\max(S)$，则 $\text{min-max}$ 容斥的原理在于：

$$ \max(\{x\})=\min(\{x\})=x $$

也就是只有一个元素，集合的 $\min=\max$。因此我们现在希望配一个系数，使得只有集合中的最大值对答案的贡献为 $1$，其他贡献都为 $0$。设集合大小为 $s$ 的集合对答案的贡献系数是 $f(s)$，则对于一个数字，他在集合中是第 $k+1$ 大，则其系数和为：

$$ \sum_{i=0}^{k} \binom{k}{i} f(i+1)=[k=0] $$

也就是只能选那些比他大的元素，才能使集合 $\min$ 恰好是自己。

二项式反演：

$$ f(k+1)=\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}[i=0]=(-1)^k $$

也就是 $f(k)=(-1)^{k+1}$。上式得证。

考虑求第 $k$ 大，先给出公式：

$$ \text{kthmax}(S)=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T) $$

带入 $k=1$ 验证一下，感觉没啥问题（

还是一样，考虑配个系数：

$$ \text{kthmax}(S)=\sum_{T\subseteq S}f(|T|)\min(T) $$

有：

$$ \sum_{i=0}^{x} \binom{x}{i} f(i+1)=[x=k-1] $$

二项式反演：

$$ f(x+1)=\sum_{i=0}^{x}(-1)^{x-i}\binom{x}{i}[i=k-1]=(-1)^{x-k+1}\binom{x}{k-1} $$

所以：$f(x)=(-1)^{x-k}\binom{x-1}{k-1}$。证毕。

~~是的例题鸽了~~