前言

这东西看起来我早就会了,只是一直没有理解其原理。/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}$。证毕。

是的例题鸽了

标签: Min-Max 容斥

添加新评论