快速入门

首先，需要学习最值反演和二项式反演，式子如下：

\[ \max(S) = \sum_{T \subset S} (-1)^{|T| – 1} \min(T) \\ f_i = \sum_{j = 0}^i {i \choose j} g_j \Leftrightarrow g_i = \sum_{j = 0}^i (-1)^{i – j} {i \choose j} f_j \]

然后，你需要对反演和容斥有一定的理解，能理解容斥系数的意义。

引入与推理

扩展最值反演其实就是通过容斥最小值的方式来求第\(k\)大值，式子如下：

\[ \text{kthmax}(S) = \sum_{T \subset S} (-1)^{|T| – 1} {|T| – 1 \choose k – 1} \min(T) \]

那么我们是如何得到\((-1)^{|T| – 1} {|T| – 1 \choose k – 1}\)这样的容斥系数的呢？我们不妨来推导一下。设置容斥系数为\(c_i\)，原式变为：

\[ \text{kthmax}(S) = \sum_{T \subset S} c_{|T|} \min(T) \]

那么我们现在来思考\(c_i\)所要满足的条件。当\(\min(T)\)为第\(i\)大数，则我们要让\(c_i\)：

\[ \sum_{j = 0}^{i – 1} {i – 1 \choose j} c_{j + 1} = [i = k] \]

可以想象成是在固定第\(i\)大之后在\(i – 1\)中枚举\(|T|\)的大小\(j\)中并选\(j\)个元素并乘上\(c_j\)等于我们期望的计数次数。我们把下标换一下，然后进行二项式反演：

\[ \begin{aligned} c’_i &= c_{i + 1}, \sum_{j = 0}^{i} {i \choose j} c’_j = [i = k – 1] \\ c’_i &= \sum_{j = 0}^i (-1)^{i – j} {i \choose j} [j = k – 1] = (-1)^{i – k + 1} {i \choose k – 1} \\ c_i &= (-1)^{i – k} {i – 1 \choose k – 1} \end{aligned} \\  \]

推完了。

例题：P4707 重返现世

毒瘤现世。首先，其实这道题就是让你求第\(n – k + 1\)大元素的期望值。