【学习笔记】min-max 容斥

前言

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

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

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

反过来也成立。

考虑证明。设 $x = max (S)$ ，则 $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$ 大，先给出公式：

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

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

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

$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})$ 。证毕。

~~是的例题鸽了~~