min-max容斥
经常与 FWT
等知识搭配食用。
min-max
容斥证明的思想是贡献打包计算。
证明(以 \(\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)\) 为例):
前面的定义直接照搬:
记全集 \(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)\):
原式得证。对于求 \(\operatorname{Kthmin}(S)\) 同理。
期望的线性性。