深入理解容斥原理及其在算法中的应用

核心逻辑与数学原理

容斥原理（Inclusion-Exclusion Principle）是组合数学中处理非互斥集合并集大小的核心工具。其核心思想在于：在计算多个重叠集合的并集大小时，先将所有集合的大小相加，随后通过交替加减重叠部分的交集大小，来精确修正被重复计算的元素贡献。

数学公式推导

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

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

用符号表达可紧凑表述为：

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{S \subseteq \{1, 2, \dots, n\}, S \neq \emptyset} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right|$$

证明逻辑（贡献度分析）：假设某个元素 $x$ 恰好属于 $k$ 个集合（$1 \le k \le n$），该元素在左侧并集中的真实贡献度计数应当精确为 $1$。检查右侧公式对该元素的计算次数：

• 包含 $x$ 的单个集合有 $C_k^1$ 个。
• 包含 $x$ 的每两个集合的交集有 $C_k^2$ 个。
• 以此类推，包含 $x$ 的 $m$ 个集合的交集有 $C_k^m$ 个。

右侧对 $x$ 的总计贡献次数为：

$$\sum_{m=1}^k (-1)^{m-1} C_k^m$$

根据二项式定理，我们知道：

$$(1 - 1)^k = \sum_{m=0}^k (-1)^m C_k^m = C_k^0 + \sum_{m=1}^k (-1)^m C_k^m = 1 - \sum_{m=1}^k (-1)^{m-1} C_k^m$$

由于 $(1 - 1)^k = 0$（当 $k \ge 1$），移项变形得：

$$\sum_{m=1}^k (-1)^{m-1} C_k^m = 1$$

任何被包含在至少一个集合中的元素，其在右侧代数和中的净贡献权值恒为 $1$。数理逻辑严丝合缝。

状态设计与算法推导

在集合数量 $n$ 较小（通常 $n \le 20$）的情况下，我们可以利用状态压缩（State Compression）思想，将集合的选取状态压缩进一个二进制整数 mask 中。

二进制状态设计

• 一个非负整数 mask 的第 $i$ 位（从 $0$ 开始编号）为 1，代表选择集合 $A_{i+1}$ 参与求交集；为 0 代表不选择。
• mask 的取值范围为 $[1, 2^n - 1]$，完美映射了 $n$ 个元素集合的所有非空子集 $S$。
• 对于给定的状态 mask：
  1. 利用内置位运算计数函数或循环，统计 mask 中二进制 1 的个数，记为 $k$（即集合大小 $|S|$）。
  2. 确定当前状态的符号权值：若 $k$ 为奇数，对应公式中的加项，权值为 $+1$；若 $k$ 为偶数，对应公式中的减项，权值为 $-1$。
  3. 计算当前子集状态下所有被选中集合的交集大小 $\left| \bigcap_{i \in S} A_i \right|$。

总并集大小即为所有 mask 状态贡献的代数和。

C++ 标准源码

#include <iostream>
#include <vector>

// 计算最大公约数，为求最小公倍数服务
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算最小公倍数，严防中间乘法爆 long long
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    long long g = gcd(a, b);
    // 先除后乘，最大化利用 long long 的空间承载力
    return (a / g) * b; 
}

// 容斥原理计数：求 1~N 中能被 primes 数组中至少一个数整除的个数
long long count_multiples(long long N, const std::vector<long long> &primes) {
    int n = primes.size();
    long long total_union = 0;
    int max_states = 1 << n; // 2^n 个可能的状态组合

    // 从 1 开始循环，直接跳过 0000... 的空集状态
    for (int mask = 1; mask < max_states; ++mask) {
        int bits_count = 0;
        long long current_lcm = 1;
        bool overflow = false;

        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) { // 捕捉状态位
                bits_count++;
                current_lcm = lcm(current_lcm, primes[i]);
                // 防御性拦截：如果当前最小公倍数已经大于 N，则 1~N 范围内其倍数必然为 0
                if (current_lcm > N || current_lcm <= 0) { 
                    overflow = true;
                    break;
                }
            }
        }

        if (overflow) continue; // 超出上限的交集大小直接归零，不予统计

        long long count = N / current_lcm; // 计算当前交集集合的大小

        // 奇加偶减内核逻辑
        if (bits_count & 1) {
            total_union += count;
        } else {
            total_union -= count;
        }
    }

    return total_union;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long N;
    int n;
    if (std::cin >> N >> n) {
        std::vector<long long> primes(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> primes[i];
        }
        std::cout << count_multiples(N, primes) << "\n";
    }
    return 0;
}

NOIP 实战避坑指南

1. 求交集时乘法爆发引发死循环或负数截断 在求多个数的最小公倍数时（如上述源码中的 lcm 累乘），多个数的乘积会以几何级数爆炸。即使使用了 long long，也极易在四五个非质数累乘后爆出符号位变成负数。如果不做 current_lcm > N 的防御拦截，N / current_lcm 会算出一个错误的巨大数据，彻底摧毁容斥的加减平衡。
2. 位运算优先级低级失误 在判断二进制位时，很多选手会顺手写成 if (mask >> i & 1 == 1)。注意：C++中位移运算符 >> 和按位与 & 的优先级低于相等运算符 ==。这段代码在编译器的视角里等价于 mask >> (i & (1 == 1))，逻辑当场畸变。必须严格加括号：if ((mask >> i) & 1)。

经典 NOIP/洛谷 真题

1. 洛谷 P1450 [HAOI2008] 硬币购物

• 题意描述：共有 $4$ 种面值的硬币，面值分别为 $c_1, c_2, c_3, c_4$。某人去购物，每种硬币分别有 $d_1, d_2, d_3, d_4$ 枚。求支付面值总和为 $s$ 的方案数。多组询问（高达 $10^5$ 次），硬币面值固定。
• 问题本质：多重背包可行方案数转化为完全背包加容斥原理抽离。
• 核心解题思路：由于询问次数极高，不可能每组询问都跑一次多重背包。因为硬币面值固定，可以先不限制每种硬币的个数，跑一次普通的完全背包预处理出数组 $f[s]$。对于每次询问，不合法的情况是“至少有一种硬币被超过了限制个数”。由于硬币种类仅为 $4$，直接使用状态数只有 $2^4 = 16$ 种的状压容斥。若限制第 $i$ 种硬币超额，意味着强行先放入 $c_i \times (d_i + 1)$ 的面值，剩下的容量随便放，即方案数为 $f[s - c_i \times (d_i + 1)]$。通过奇加偶减修正完全背包产生的多余贡献。

2. 洛谷 P2567 [SCOI2010] 幸运数字

• 题意描述：仅由 4 和 7 组成的数字被称为幸运数字（如 4, 7, 44, 47）。如果一个正整数能被任意一个幸运数字整除，它就被称为神奇数字。求区间 $[A, B]$ 内神奇数字的个数。$1 \le A \le B \le 10^{10}$。
• 问题本质：大范围内的非互质集合并集计数。
• 核心解题思路：首先通过 DFS 搜索出 $[1, B]$ 范围内的所有基础幸运数字，去掉彼此之间存在倍数关系的冗余数字（例如有了 4 就不需要 44）。筛选后剩下的数字个数约在几百个级别。由于几百个数字无法直接套用 $2^n$ 的状压容斥，必须进行带剪枝的 DFS 搜索容斥。在搜寻组合时，一旦当前的最小公倍数 $lcm > B$，直接进行可行性剪枝。利用搜索树的深度天然充当 bits_count，完成大范围的容斥原理落地。