关于容斥原理
Captain_Paul · · 个人记录
对容斥的理解一直不是很透彻，略写一点，稍作整理
注：本文有部分引自没想好叫什么名字大佬的博客
最简单的容斥
求几个集合的并集，如：
用维恩图也可以轻松得出
由三个集合的并集大小可以推广到
即：各集合之和-两个集合的交集+三个集合的交集……
同理，也可以用这种方法求解概率的问题
如：事件集合
关于证明：
贴个链接
实际问题中的应用
-
简单排列问题：用
0 到9 的数字组成不重复的排列，要求第一个数大于1 ，最后一个数小于8 ，有多少种排列方式正难则反，我们可以求出第一个数小于等于
1 ，最后一个数大于等于8 的排列数设第一个数小于等于
1 时的集合为X ，最后一个数大于等于8 的集合为Y 根据容斥原理得，所求为
|X|+|Y|-|X∩Y| 用简单的排列组合可以得到答案为
S=2\times9!+2\times9!-2\times2\times8! 那么原题答案
Ans=10!-S
-
0,1,2 序列问题：长度为n 的由0,1,2 组成的序列，要求每个数字至少出现1 次，有多少种排列方式还是逆向思维，考虑不出现某些数字的情况
设
A_i 表示不出现数字i 的序列数，根据容斥原理，得到逆问题的结果为：|A_0|+|A_1|+|A_2|-|A_0∩A_1|-|A_0∩A_2|-|A_1∩A_2|+|A_0∩A_1∩A_2| 可以发现每个
A_i 的值都是2^n （因为只有两个数）所以原题答案为$3^n-3\times2^n+3\times1-0
-
方程整数解问题：给出一个方程：
x_1+x_2+...+x_n=t ，其中0<=x_i<=m ，求方程整数解的数量先忽略
x_i 的限制，考虑方程非负整数解的数量问题等价于求方程
(x_1+1)+(x_2+1)+...(x_n+1)=t+n 的正整数解相当于有
t+n 个1 ，要在其中放(n-1) 块隔板，因此有C_{t+n-1}^{n-1} 中放法所以原方程的非负整数解有
C_{t+n-1}^{n-1} 组用容斥原理来讨论它的逆问题，即当
x>m 时的解定义
A_k 为x_k>m 且其他x_i>=0 时的集合沿用隔板的思想，有
m+1 个位置已经被占用了，所以|A_k|=C_{t+n-m-2}^{n-1} 计算这样两个集合
A_k 和A_p 的交集|A_k∩A_p|=C_{t+n-2m-3}^{n-1} 考虑到总和为
t ，这样的集合个数是有限制的，设最多有k 个逆问题答案
Res=C_{n}^{1}*C_{t+n-m-2}^{n-1}-C_{n}^{2}*C_{t+n-2m-3}^{n-1}+...C_{n}^{k}*C_{t+n-km-k-1}^{n-1} 原问题答案即为
Ans=C_{t+n-1}^{n-1}-Res 这道题里有用到
-
求区间
[1,r] 内与n 互质的数的个数先计算不与
n 互质的数的个数考虑
n 的所有质因子p_i(i∈[1,k]) 在
[1,r] 内能被p_i 整除的数的个数为：\lfloor{r/p_i}\rfloor 但是如果直接相加，就会出现重复计算的情况（一个数可能被多个质因子整除）
可以用
2^k 的算法求出所有的质因子组合，计算每种组合的p_i 乘积，通过容斥原理处理结果题在这
具体实现代码