min-max容斥-最值反演及其推广

设 $S$ 是一个集合， $max (S)$ 和 $min (S)$ 分别表示集合中的最大值与最小值。

那么有如下式子成立：

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

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

因为证明很简单就写一下吧，以第一个式子为例，设 $max (S) = x$ ，那么只有 $T = {x}$ 时的 $min (T)$ 为 $x$ （可能有多个相同的最大值，这时候随便钦点一个就可以了），对于除此之外的所有 $T$ ，肯定至少存在一个集合中的数 $y$ 使得 $min (T \cup {y}) = min (T)$ ，假设有 $k$ 个这样的 $y$ ，那么从中选奇数个和选偶数个的方案数是一样的，于是 $min (T)$ 就被抵消了。

这个式子在期望下也是成立的，即：

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

用期望的线性性证明即可。

于是就可以用来做题了，一般的套路是每个位置有概率从 $0$ 变成 $1$ ，问都变成 $1$ 的期望步数，这就是 $max (S)$ ，然后就反演成 $min (T)$ ，至少一个数变成 $1$ 的期望就好做很多了。

$u p d$ ：来填坑了...现在来介绍一下最值反演的推广：通过求 $min$ 来求第 $k$ 大（ $k t h max$ ）。前置知识是二项式反演，如果不知道请戳这里 (opens new window)。

我们来尝试构造一个函数 $f$ ，使得：

k t h max (S) = \sum_{T \subseteq S} f_{| T |} min (T)

然后来考虑一下对于集合中第 $i$ 大的元素，如果 $min (T)$ 等于这个元素，那么只有比它大的 $i - 1$ 个元素是可能存在的，那么它的贡献就是：

\sum_{j = 0}^{i - 1} (\binom{i - 1}{j}) f_{j + 1}

也就是说 $f$ 需要满足：

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

等价于：

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

为了方便我们用 ${\hat{f}}_{i} = f_{i + 1}$ 替换 $f$ ，然后用 $g_{i}$ 表示 $[i = k - 1]$ ，那么就得到：

\sum_{j = 0}^{i} (\binom{i}{j}) {\hat{f}}_{j} = g_{i}

看这个是不是一个经典的二项式反演的形式呀，所以二项式反演一下：

{\hat{f}}_{i} = \sum_{j = 0}^{i} (- 1)^{i - j} (\binom{i}{j}) g_{j}

然后因为 $g_{i} = [i = k - 1]$ ，所以上面的式子只有 $j = k - 1$ 这一项是有贡献的，我们再把 $f$ 替换回去，得：

f_{i + 1} = (- 1)^{i - k + 1} (\binom{i}{k - 1})

再把 $f_{i + 1}$ 替换成 $f_{i}$ ，最终得到：

f_{i} = (- 1)^{i - k} (\binom{i - 1}{k - 1})

终于结束啦！

k t h max (S) = \sum_{T \subseteq S} (- 1)^{| T | - k} (\binom{| T | - 1}{k - 1}) min (T)

同时我们可以发现如果要求第 $k$ 大，那么只需要计算元素个数 $\geq k$ 的子集就可以了。