min-max容斥
经常与 FWT 等知识搭配食用。
min-max 容斥证明的思想是贡献打包计算。
\[\max(S) = \sum\limits_{T \subseteq S, T \neq \emptyset} (-1)^{|T| + 1} \min(T) \\ \min(S) = \sum\limits_{T \subseteq S, T \neq \emptyset} (-1)^{|T| + 1} \max(T) \\ \]
证明（以 \(\max(S) = \sum\limits_{T \subseteq S, T \neq \emptyset} (-1)^{|T| + 1} \min(T)\) 为例）：
记全集 \(U = \{ A_1, A_2, \dots, A_n \}\)，其中 \(A\) 降序排列。
记 \(S \subseteq U, S \neq \emptyset\)，\(S = \{ A_{a_1}, A_{a_2}, \cdots, A_{a_m} \}\)，同样降序排列。
记 \(a_m = k\)，即 \(\min(S) = A_k\)。记 \(\max(S) = A_{a_1}\)。
-
当 \(k = 1\)时， 易知 \(S = \{ A_1 \}\)，则 \(T\) 只能为 \(\{ A_1 \}\)，\(\max(S) = A_1 = (-1)^{2}A_1 = (-1)^{2}\min(T)\)。
-
当 \(k > 1\) 时：枚举 \(T \subseteq S, T \neq \emptyset\)。
-
当 \(T = \{ A_{a_1} \}\) 时，有 \(\min(T) = \max(T) = \max(S)\)。
-
否则，对于其他的 \(T \neq \{ A_{a_1} \}\)，
当 \(\min(T) = A_{a_x}\) 时，仅考虑 \(T\) 取 \(S\) 中前 \(x\) 个元素（特殊考虑存在元素相等时的情况），
有 \(2^{x - 2}\) 个 \(T\) 的大小为偶数，有 \(2^{x - 2}\) 个 \(T\) 的大小为奇数，故能抵消。
即此类 \(T\) 对 \(\max(S)\) 无贡献。
于是原式的求和转为 \((-1)^{2}\min(\{ A_{a_1} \}) = A_{a_1} = \max(S)\)。
-
综上可知 \(\max(S) = \sum\limits_{T \subseteq S, T \neq \emptyset} (-1)^{|T| + 1} \min(T)\)。
同理可得 \(\min(S) = \sum\limits_{T \subseteq S, T \neq \emptyset} (-1)^{|T| + 1} \max(T)\)。
当 \(U\) 中存在多个元素的值相等时，结论仍然适用。
\[\operatorname{Kthmax}(S) = \sum\limits_{T \subseteq S, T \neq \emptyset}(-1)^{|T| + K}\binom{|T| - 1}{K - 1}\min(T) \\ \operatorname{Kthmin}(S) = \sum\limits_{T \subseteq S, T \neq \emptyset}(-1)^{|T| + K}\binom{|T| - 1}{K - 1}\max(T) \\ \]
不妨先来看一下其在特殊情况下的正确性：
\[\operatorname{1thmax(S)} = \max(S) = \sum\limits_{T \subseteq S, T \neq \emptyset}(-1)^{|T| + 1}\binom{|T| - 1}{1 - 1}\min(T) = \sum\limits_{T \subseteq S, T \neq \emptyset}(-1)^{|T| + 1}\min(T) \\ \]证明（同样以求 \(\operatorname{kthmax}(S)\) 为例）：
前面的定义直接照搬：
记全集 \(U = \{ A_1, A_2, \dots, A_n \}\)，其中 \(A\) 降序排列。
记 \(S \subseteq U, S \neq \emptyset\)，\(S = \{ A_{a_1}, A_{a_2}, \cdots, A_{a_m} \}\)，同样降序排列。
记 \(a_m = k\)，即 \(\min(S) = A_k\)。记 \(\max(S) = A_{a_1}\)。
构造 \(\operatorname{Kthmax}(S) = \sum\limits_{T \subseteq S, T \neq \emptyset}F(|T|)\min(T) \\\)，欲求 \(F(|T|)\)。
\(k = 1\) 略，这里只考虑 \(k > 1\)。
类似地考虑令 \(\min(T) = A_{a_x}\)，并只考虑 \(T\) 取 \(S\) 中前 \(x\) 个元素（特殊考虑存在元素相等时的情况）。
考虑 \(A_{a_x}\) 必选，则这样的 \(T\) 有 \(2^{x - 1}\) 种可能，对 \(\operatorname{Kthmax}(S)\) 的贡献为 \(\sum\limits_{i = 0}^{x - 1}\binom{x - 1}{i}F(i + 1)\)。
根据我们的目的，需使 \(\sum\limits_{i = 0}^{x - 1}\binom{x - 1}{i}F(i + 1) = [x = K]\)，即最终只有 \(\min(T) = A_{a_K}\) 的贡献和为 \(1\)，其他为 \(0\)。
换元，得 \(\sum\limits_{i = 0}^{x}\binom{x}{i}F(i + 1) = [x + 1 = K]\)。
比较标准的二项式反演形式。令 \(G(x) = [x = K - 1] = \sum\limits_{i = 0}^{x}\binom{x}{i}F(i + 1)\)：
\[\begin{aligned} F(x + 1) &= \sum\limits_{i = 0}^{x}\binom{x}{i}(-1)^{x - i}[i = K - 1] \\ &= \binom{x}{K - 1}(-1)^{x - (K - 1)} \\ F(x) &= \binom{x - 1}{K - 1}(-1)^{x - K} \end{aligned} \]原式得证。对于求 \(\operatorname{Kthmin}(S)\) 同理。
\[E[\max(S)] = \sum\limits_{T \subseteq S, T \neq \emptyset} (-1)^{|T| + 1} E[\min(T)] \\ E[\min(S)] = \sum\limits_{T \subseteq S, T \neq \emptyset} (-1)^{|T| + 1} E[\max(T)] \\ E[\operatorname{Kthmax}(S)] = \sum\limits_{T \subseteq S, T \neq \emptyset}(-1)^{|T| + K}\binom{|T| - 1}{K - 1}E[\min(T)] \\ E[\operatorname{Kthmin}(S)] = \sum\limits_{T \subseteq S, T \neq \emptyset}(-1)^{|T| + K}\binom{|T| - 1}{K - 1}E[\max(T)] \\ \]
期望的线性性。
标签：limits,min,max,sum,容斥,subseteq,neq From： https://www.cnblogs.com/Schucking-Sattin/p/17416865.html