容斥问题
OIer_ACMer · · 个人记录
容斥原理是组合数学中的一种重要计数方法，用于计算多个集合的并集元素个数。其核心思想是“先加后减，避免重复”，通过交替加减交集的方式逐步修正计数结果。下面详细解释其原理、公式和应用。
一、基本思想
当多个集合存在重叠时，直接求和会导致交集部分被重复计算。容斥原理通过交替加减交集项来消除重复，确保每个元素只被计算一次。
二、公式表达
1. 两个集合
[ |A \cup B| = |A| + |B| - |A \cap B| ]
2. 三个集合
[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| ]
3. n个集合的一般形式
对于集合 ( A_1, A_2, \dots, An )： [ \left| \bigcup{i=1}^n Ai \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|
- \cdots
- (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n| ] 规律：
- 奇数个集合的交集：加；
- 偶数个集合的交集：减；
- 符号交替出现。
三、经典应用示例
1. 错位排列问题
问题：( n ) 个人和 ( n ) 顶帽子，每个人都不拿自己帽子的方案数（错位排列数 ( D_n )）。
解：
- 设 ( A_i ) 为第 ( i ) 个人拿到自己帽子的事件。
- 总排列数 ( n! )。
- 利用容斥原理： [ Dn = n! - \sum{i=1}^n |Ai| + \sum{i<j} |A_i \cap A_j| - \cdots + (-1)^n |A_1 \cap \cdots \cap An| ] 其中，( |A{i1} \cap \cdots \cap A{i_k}| = (n-k)! )（固定 ( k ) 个人拿自己帽子，其余任意）。 [ D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!} \right) ]
2. 欧拉函数（Euler's Totient Function）
问题：计算小于 ( n ) 且与 ( n ) 互质的正整数个数 ( \varphi(n) )。
解：
- 设 ( n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} )。
- 令 ( A_i ) 为能被 ( p_i ) 整除的数的集合。
- 利用容斥原理： [ \varphi(n) = n - \sum_{i=1}^k \left\lfloor \frac{n}{pi} \right\rfloor + \sum{i<j} \left\lfloor \frac{n}{p_i p_j} \right\rfloor - \cdots + (-1)^k \left\lfloor \frac{n}{p_1 p_2 \cdots p_k} \right\rfloor ] 化简后得： [ \varphi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_k} \right) ]
3. 区间内与某数互质的整数个数
问题：求 ([1, m]) 中与 ( n ) 互质的整数个数。
解：
- 对 ( n ) 质因数分解，设质因子为 ( p_1, \dots, p_k )。
- 令 ( A_i ) 为能被 ( p_i ) 整除的数的集合。
- 利用容斥原理： [ \text{Ans} = m - \sum_{i=1}^k \left\lfloor \frac{m}{pi} \right\rfloor + \sum{i<j} \left\lfloor \frac{m}{p_i p_j} \right\rfloor - \cdots ]
四、使用技巧与注意事项
- 问题转化：将复杂条件转化为集合的并集，再用容斥原理。
- 交集计算：关键是如何快速计算多个集合的交集大小（例如利用质因子的倍数）。
- 时间复杂度：若集合数量 ( n ) 很大，但交集计算简单（如质因子倍数），可枚举子集（( 2^k ) 复杂度，( k ) 为质因子数）。
五、总结
容斥原理是处理重叠计数问题的利器，其核心在于通过交替符号的求和来修正重复计算。熟练掌握容斥原理，能够解决许多组合数学、数论和概率问题。