容斥问题

一、基本思想

二、公式表达

1. 两个集合

2. 三个集合

3. n个集合的一般形式

• \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. 错位排列问题

• 设 ( A_i ) 为第 ( i ) 个人拿到自己帽子的事件。
• 总排列数 ( n! )。
• 利用容斥原理： [ D_n = n! - \sum_{i=1}^n |A_i| + \sum_{i<j} |A_i \cap A_j| - \cdots + (-1)^n |A_1 \cap \cdots \cap A_n| ] 其中，( |A_{i_1} \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 = 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}{p_i} \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. 区间内与某数互质的整数个数

• 对 ( n ) 质因数分解，设质因子为 ( p_1, \dots, p_k )。
• 令 ( A_i ) 为能被 ( p_i ) 整除的数的集合。
• 利用容斥原理： [ \text{Ans} = m - \sum_{i=1}^k \left\lfloor \frac{m}{p_i} \right\rfloor + \sum_{i<j} \left\lfloor \frac{m}{p_i p_j} \right\rfloor - \cdots ]

四、使用技巧与注意事项

1. 问题转化：将复杂条件转化为集合的并集，再用容斥原理。
2. 交集计算：关键是如何快速计算多个集合的交集大小（例如利用质因子的倍数）。
3. 时间复杂度：若集合数量 ( n ) 很大，但交集计算简单（如质因子倍数），可枚举子集（( 2^k ) 复杂度，( k ) 为质因子数）。

五、总结