InoueMoby's Blog

前言

班里有 30 个学生，18 个参加了数学社团，12 个参加了物理社团，5 个两个都参加了。那”至少参加了一个社团”的有多少人？

直觉告诉你： $18 + 12 = 30$ ？不对——那 5 个两边都参加的人被算了两次。所以 $18 + 12 - 5 = 25$ 。

这就是容斥原理。名字听起来高大上，但核心就是一句话：重叠的部分被多算了，要减回来；减多了又要加回来；加多了又要减回来……交替加减直到不重不漏。

00-03 累积和与差分里二维前缀和的”加了减、减了加”就是最简单的容斥。这篇推广到任意多个集合的情况。

问题的本质

两个集合

|A \cup B| = |A| + |B| - |A \cap B|

两个集合的并 = 各自大小之和 - 交集（被算了两次）。

三个集合

|A \cup B \cup C| = |A|+|B|+|C| - |A \cap B|-|A \cap C|-|B \cap C| + |A \cap B \cap C|

先加三个单独的，减去两两交被多加的，再加回三重交被多减的。符号交替： $+ - +$ 。

一般公式

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \ne S \subseteq \{1,\ldots,n\}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|

翻译成人话：枚举所有非空子集 $S$ ，如果 $|S|$ 是奇数就加、偶数就减。一共 $2^n - 1$ 项。

互补形式

容斥更常用的形式是求都不满足的个数：

\left|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\right| = N - |A_1 \cup \cdots \cup A_n|

即”全集 - 至少满足一个条件的个数”。

理论 + 代码

位掩码枚举所有子集

当集合个数 $n \le 20$ 时，可以用位掩码枚举所有 $2^n$ 个子集：

// 容斥公式：枚举所有非空子集
long long ans = 0;
for (int mask = 1; mask < (1 << n); mask++) {
    // ① mask 的每一位代表"选不选这个集合"
    int bits = __builtin_popcount(mask);  // ② 子集大小
    long long sz = count_intersection(mask);  // ③ 交集的大小
    if (bits % 2 == 1)
        ans += sz;    // ④ 奇数个集合：加
    else
        ans -= sz;    // ⑤ 偶数个集合：减
}

② __builtin_popcount(mask) 是 GCC 内置函数，返回 mask 中 1 的个数（即子集大小）。
③ count_intersection(mask) 需要根据具体问题实现——计算 mask 中所有集合的交集大小。
④⑤ 奇数加偶数减，对应公式中的 $(-1)^{|S|+1}$ 。

例题

例题 1：M&A 007 — Number of Multiples 1（★1）

题目： $N$ 以下有多少个正整数是 $X$ 或 $Y$ 的倍数？

数据范围： $1 \le N \le 10^6$ ， $1 \le X < Y \le 10^6$

—— AtCoder M&A 007

思路：容斥原理最基础的例子。 $X$ 的倍数有 $\lfloor N/X \rfloor$ 个， $Y$ 的倍数有 $\lfloor N/Y \rfloor$ 个，但两者公有的（ $LCM(X,Y)$ 的倍数）被算了两次，要减去。

答案 = $\lfloor N/X \rfloor + \lfloor N/Y \rfloor - \lfloor N/\text{lcm}(X,Y) \rfloor$ 。

代码：

#include <cstdio>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

int main() {
    long long N, X, Y;
    scanf("%lld%lld%lld", &N, &X, &Y);

    long long cntX = N / X;                       // ① X 的倍数个数
    long long cntY = N / Y;                       // ② Y 的倍数个数
    long long lcm = X / gcd(X, Y) * Y;            // ③ LCM(X,Y)，先除后乘防溢出
    long long cntXY = N / lcm;                    // ④ 同时是 X 和 Y 的倍数的个数

    printf("%lld\n", cntX + cntY - cntXY);        // ⑤ 容斥：|A∪B| = |A|+|B|-|A∩B|
}

逐行解析：

⑤ 这就是容斥原理的两集合版本： $|A \cup B| = |A| + |B| - |A \cap B|$ 。

例题 2：M&A 068 — Number of Multiples 2（★2）

题目： $1$ 到 $N$ 中，有多少个整数是 $V_1, V_2, \ldots, V_K$ 中至少一个的倍数？

数据范围： $1 \le N \le 10^{12}$ ， $1 \le K \le 10$ ， $1 \le V_i \le 50$

—— AtCoder M&A 068

思路： $K \le 10$ ，可以枚举所有 $V_i$ 的子集（共 $2^K - 1 = 1023$ 个），对每个子集求 LCM，然后用容斥原理：

$\text{答案} = \sum_{\emptyset \ne S \subseteq \{1,\ldots,K\}} (-1)^{|S|+1} \lfloor N / \text{lcm}(S) \rfloor$

子集大小为奇数时加，偶数时减。

代码：

#include <cstdio>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

int main() {
    long long N;
    int K;
    scanf("%lld%d", &N, &K);
    long long V[15];
    for (int i = 0; i < K; i++)
        scanf("%lld", &V[i]);

    long long ans = 0;
    for (int mask = 1; mask < (1 << K); mask++) {  // ① 枚举所有非空子集
        long long l = 1;
        int bits = 0;
        for (int i = 0; i < K; i++) {
            if (mask >> i & 1) {
                bits++;
                l = l / gcd(l, V[i]) * V[i];  // ② 子集的 LCM
                if (l > N) { l = N + 1; break; }  // ③ LCM 超过 N 时直接跳出
            }
        }
        if (bits % 2 == 1)
            ans += N / l;    // ④ 奇数子集：加
        else
            ans -= N / l;    // ⑤ 偶数子集：减
    }
    printf("%lld\n", ans);
}

逐行解析：

① mask 从 1 到 $2^K - 1$ ，每个 mask 代表一个非空子集。
② 对子集中的元素求 LCM。先除 GCD 再乘，防溢出。
③ 如果 LCM 已经超过 $N$ ，则 $\lfloor N/LCM \rfloor = 0$ ，不影响结果，可以剪枝。
④⑤ 容斥符号：奇数大小加、偶数大小减。

例题 3：M&A 066 — Three Cards（★2）

题目：有黑、白、灰三张卡片，各写一个 $1$ 到 $N$ 的整数。求满足以下至少一个条件的写法数：黑白差 $\ge K$ 、黑灰差 $\ge K$ 、灰白差 $\ge K$ 。

数据范围： $1 \le N \le 100000$ ， $1 \le K \le \min(5, N-1)$

—— AtCoder M&A 066

思路：用容斥求”至少一个条件满足”。总数 $N^3$ ，减去”三个条件都不满足”就是答案。

“三个条件都不满足”= 黑白差 $< K$ 且黑灰差 $< K$ 且灰白差 $< K$ 。即所有相邻对的差都 $< K$ 。

直接统计”都不满足”的数量：枚举黑色的值 $b$ （ $1$ 到 $N$ ），白色 $w$ 必须在 $[\max(1, b-K+1), \min(N, b+K-1)]$ 范围内，灰色 $g$ 必须同时满足和黑色差 $< K$ 及和白色差 $< K$ 。

由于 $K \le 5$ ，范围很小，可以暴力枚举。

代码：

#include <cstdio>
#include <cstdlib>
using namespace std;

int main() {
    long long N;
    int K;
    scanf("%lld%d", &N, &K);

    long long total = N * N % 1000000007 * N % 1000000007;  // 总写法 N^3
    long long bad = 0;

    // 统计"三个条件都不满足"的写法
    for (int b = 1; b <= N; b++) {
        for (int d_bw = -(K-1); d_bw <= K-1; d_bw++) {  // ① 黑白差 < K
            int w = b + d_bw;
            if (w < 1 || w > N) continue;
            for (int d_bg = -(K-1); d_bg <= K-1; d_bg++) {  // ② 黑灰差 < K
                int g = b + d_bg;
                if (g < 1 || g > N) continue;
                if (abs(w - g) >= K) continue;  // ③ 灰白差也要 < K
                bad++;
            }
        }
    }
    bad %= 1000000007;
    long long ans = (total - bad % 1000000007 + 1000000007) % 1000000007;
    printf("%lld\n", ans);
}

参考文献

教材讲解 — 競技プログラミングの鉄則第 5 章

5.6 B31 Divisors Hard（容斥原理解说，3 集合の包除原理）

配套教材

「アルゴリズムと数学」書籍 2.5 節「包除原理」

基础练习 — アルゴリズムと数学演習問題集

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

竞技编程 02-06 容斥原理

加了减、减了加——不重复不遗漏地计数

前言