Min-Max容斥 学习笔记

· · 算法·理论

Min-Max 容斥学习笔记

前置知识

全序

设集合 X 上有一个全序关系，记作 \le，则下列叙述对于 \forall a, b, c \in X 都成立：

  1. 反对称性：若 a \le b 且 b \le a，则 a = b。
  2. 传递性：若 a \le b 且 b \le c，则 a \le c。
  3. 完全性：a \le b 或 b \le a。

关系的完全性可以理解为：对于集合中的任意一对元素，在该关系下都是相互可比较的。同时，完全性条件蕴含了自反性，即 a \le a。因此，全序也是偏序（自反、反对称、传递的二元关系），而全序可定义为满足“完全性”条件的偏序。

容斥原理

容斥原理用于计数问题，避免重复计数或遗漏计数，常见于集合交并计数、概率问题等。

Min-Max 容斥原理

定理及公式

Min-Max容斥，又称最值反演，是一种针对特定集合，在已知集合的最小值或最大值情况下，求另一者的算法。

对于集合 S，有如下等式：

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

证明思路

设 U = \{u_1, u_2, \ldots, u_n\}，且 u_i \neq u_j (i \neq j)。令 A_k 为 U 中元素降序排列后第 k 大的元素。

考虑 \min(S) = A_k 的情况：

  1. 若 k = 1，即 \min(S) = A_1，那么显然 S = \{A_1\}，此时答案为 (-1)^2 A_1 = A_1，成立。
  2. 若 k > 1，集合的良序性要求 S 中不应存在比 A_k 更小的元素，剩下的 k-1 个位置有 2^{k-1} 种选取方式。
    • 其中一半即 2^{k-2} 种方案使 |S| 为奇数，另一半为偶数。
    • 两部分分别相加后互相抵消，因此最终结果为 0。

另一种情况同理，详细证明可参考Min-max Inclusion and Exclusion。

扩展公式

第 k 大/小

记 \max_k(S) 表示 S 中第 k 大的元素，\min_k(S) 同理，则：

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

期望推广

若 E(\max(S)) 表示最大值的期望，有：

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

应用场景与例题

应用场景

Min-Max容斥与其推广常用于解决“所有元素都出现的期望时间”问题。

记 t_i 表示第 i 个元素的出现时间：

根据 Min-Max 容斥，有：

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

对公式两边取期望，由于期望的线性性质，可以直接放到求和符号内，即：

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

实际应用时，E(\min(T)) 的计算较为简单：若单位时间出现 T 中至少一个元素的概率为 p，则其期望时间为 \frac{1}{p}。

实现方式

由于此方法与集合状态有关，通常使用状态压缩进行实现。以下为伪代码示例：

for i = 0 to 2^n - 1:
    for j = 0 to 2^n - 1:
        if (j & i):
            dp[j] = dp[i] - dp[j]

例题

该题为经典的“卡片收集期望时间”问题，可以直接使用 Min-Max 容斥求解。

参考文献