容斥原理

前言

班里有 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$ 个子集： ```cpp // 容斥公式：枚举所有非空子集 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](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_g) **思路**：容斥原理最基础的例子。$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$。 **代码**： ```cpp #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](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_be) **思路**：$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$$ 子集大小为奇数时加，偶数时减。 **代码**： ```cpp #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](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bd) **思路**：用容斥求"至少一个条件满足"。总数 $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$，范围很小，可以暴力枚举。 **代码**： ```cpp #include <cstdio> 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 集合の包除原理）](https://github.com/E869120/kyopro-tessoku/blob/main/editorial/chap05/chap05.pdf) **配套教材** - 「アルゴリズムと数学」書籍 2.5 節「包除原理」 **基础练习** — アルゴリズムと数学 演習問題集 - [007 Number of Multiples 1（倍数计数入门）【例题】](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_g) - [068 Number of Multiples 2（多集合容斥）【例题】](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_be) - [066 Three Cards（有界计数+容斥）【例题】](https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bd) --- ## 系列索引 **第零章 基础工具** - [00-01 复杂度与暴力枚举](https://blog.inouemoby.com/posts/0faccf60/) - [00-02 排序](https://blog.inouemoby.com/posts/b51e93fd/) - [00-03 累积和与差分](https://blog.inouemoby.com/posts/74762bb5/) **第一章 搜索技术** - [01-01 二分搜索](https://blog.inouemoby.com/posts/a74c9f0a/) - [01-02 双指针与尺取法](https://blog.inouemoby.com/posts/015181cf/) **第二章 数学基础** - [02-01 整数与整除](https://blog.inouemoby.com/posts/4bee4857/) - [02-02 素数与筛法](https://blog.inouemoby.com/posts/1c879235/) - [02-03 同余与模运算](https://blog.inouemoby.com/posts/3adf87b4/) - [02-04 快速幂与逆元](https://blog.inouemoby.com/posts/38f06f22/) - [02-05 组合计数](https://blog.inouemoby.com/posts/12196d40/) - [02-06 容斥原理](https://blog.inouemoby.com/posts/69c8300a/) - [02-07 欧拉函数](https://blog.inouemoby.com/posts/77c20ec5/) - [02-08 博弈论基础](https://blog.inouemoby.com/posts/9cd8e63e/) **第三章 数据结构** - [03-01 栈、队列与单调栈](https://blog.inouemoby.com/posts/c21e9dca/) - [03-02 堆与优先队列](https://blog.inouemoby.com/posts/fe75f985/) - [03-03 并查集](https://blog.inouemoby.com/posts/884bc6cf/) - [03-04 树状数组](https://blog.inouemoby.com/posts/e0ef2960/) - [03-05 线段树](https://blog.inouemoby.com/posts/67b6bfeb/) - [03-06 懒标记线段树](https://blog.inouemoby.com/posts/3787855c/) - [03-07 Sparse Table 与倍增](https://blog.inouemoby.com/posts/29de7e74/) - [03-08 字符串哈希](https://blog.inouemoby.com/posts/0e5edad3/) **第四章 图论** - [04-01 图的遍历](https://blog.inouemoby.com/posts/ad6b1d3a/) - [04-02 最短路—Dijkstra 与 01-BFS](https://blog.inouemoby.com/posts/efa03f8e/) - [04-03 最短路—Bellman-Ford 与 Floyd](https://blog.inouemoby.com/posts/d97aeafa/) - [04-04 拓扑排序](https://blog.inouemoby.com/posts/ba521cfa/) - [04-05 最小生成树](https://blog.inouemoby.com/posts/94e28d45/) - [04-06 强连通分量与 2-SAT](https://blog.inouemoby.com/posts/bc7f9b2b/) - [04-07 二分图与网络流](https://blog.inouemoby.com/posts/cb9e655e/) - [04-08 树上问题](https://blog.inouemoby.com/posts/c7f6985a/) **第五章 动态规划** - [05-01 DP入门—状态与转移](https://blog.inouemoby.com/posts/0c11b87e/) - [05-02 背包问题族](https://blog.inouemoby.com/posts/5eea935e/) - [05-03 LIS、LCS与编辑距离](https://blog.inouemoby.com/posts/e151a6e9/) - [05-04 区间DP](https://blog.inouemoby.com/posts/deb9c248/) - [05-05 状态压缩DP](https://blog.inouemoby.com/posts/c82ca83b/) - [05-06 树形DP与数位DP](https://blog.inouemoby.com/posts/c2bdeed6/) - [05-07 矩阵快速幂与线性递推](https://blog.inouemoby.com/posts/064ae7c6/) **第六章 贪心** - [06-01 贪心策略与交换论证](https://blog.inouemoby.com/posts/07e884de/) - [06-02 区间调度与优化](https://blog.inouemoby.com/posts/79b6914d/) **第七章 字符串** - [07-01 字符串哈希详述](https://blog.inouemoby.com/posts/536f7894/) - [07-02 后缀数组](https://blog.inouemoby.com/posts/f8ceca24/) **第八章 进阶** - [08-01 卷积与FFT](https://blog.inouemoby.com/posts/f35cf6db/) - [08-02 期望与概率](https://blog.inouemoby.com/posts/9ae9b9e6/) - [08-03 Zeta / Möbius 变换](https://blog.inouemoby.com/posts/fb00bac3/) - [08-04 计算几何基础](https://blog.inouemoby.com/posts/35ec0205/) - [08-05 采样与随机化](https://blog.inouemoby.com/posts/088aa6c3/)