容斥原理 - NOI提高级教程

📖 离散组合数学：容斥原理（斥与容的艺术）

在计数时，为了求几个集合并集的大小，我们先将所有集合大小相加，然后减去多加的交集，再补回多扣的交集，以此类推。这种奇数个集合的交集相加，偶数个集合的交集相减的算法即为容斥原理。

📐 容斥原理代数通式

设 $A_1, A_2, \ldots, A_n$ 为有限集合，它们的并集大小公式为：

$\left| \bigcup_{i=1}^n A_i \right| = \sum_i |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$

二进制掩码实现：如果有 $n$ 个集合，我们可以用一个从 $1 \to 2^n-1$ 的二进制数掩码表示选择哪些集合求交集。若选择集合的个数为奇数，符号为正；若为偶数，符号为负。

演示控制：

点击“容斥步骤逐步演示”按钮，可逐步观察维恩图中单个集合累加（容）、两个集合交集剔除（斥）、三个集合重叠补回（容）的代数过程。

单集合和 |A|+|B|+|C| 15 + 10 + 6 = 31

双重交集和 ∑|Ai∩Aj| 5 + 3 + 2 = 10

三重交集 |A∩B∩C| 1

最终并集大小 |A∪B∪C| 22

📊 3 集合容斥维恩图 (Venn Diagram Area)

并集大小 = |A| + |B| + |C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C| = ?

// 容斥原理：求 [1, N] 内能被素数集合 primes 整除的数的个数
long long countDivisible(long long n, vector<long long> primes) {
    long long ans = 0;
    int k = primes.size();
    // 二进制掩码：枚举所有 2^k - 1 个非空子集
    for (int i = 1; i < (1 << k); i++) {
        long long lcmVal = 1;
        int cnt = 0; // 子集大小
        for (int j = 0; j < k; j++) {
            if ((i >> j) & 1) {
                lcmVal = lcm(lcmVal, primes[j]);
                cnt++;
            }
        }
        // 容斥定理：奇数个集合加，偶数个集合减
        if (cnt % 2 == 1) ans += n / lcmVal;
        else ans -= n / lcmVal;
    }
    return ans;
}

📋 容斥递退步骤日志