关于容斥原理

对容斥的理解一直不是很透彻，略写一点，稍作整理 注：本文有部分引自[没想好叫什么名字大佬的博客](https://blog.csdn.net/m0_37286282/article/details/78869512) ------------ ### **最简单的容斥** 求几个集合的并集，如： $|A∩B∩C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|$ 用维恩图也可以轻松得出 由三个集合的并集大小可以推广到$n$个集合的并集大小 即：各集合之和-两个集合的交集+三个集合的交集…… 同理，也可以用这种方法求解概率的问题 如：事件集合$A_i(i∈[1,n])$，求发生其中某些事件（至少发生一个事件）的概率 ------------ ### **关于证明**： [贴个链接](https://blog.csdn.net/m0_37286282/article/details/78869512) ------------ ### **实际问题中的应用** - **简单排列问题**：用$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$（因为只有两个数） $A_i$两两相交的值都是$1$（只有一个数） 所以原题答案为$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$ [这道题里有用到](https://loj.ac/problem/6077) ------------ - **求区间$[1,r]$内与$n$互质的数的个数** 先计算不与$n$互质的数的个数 考虑$n$的所有质因子$p_i(i∈[1,k])$ 在$[1,r]$内能被$p_i$整除的数的个数为：$\lfloor{r/p_i}\rfloor$ 但是如果直接相加，就会出现重复计算的情况（一个数可能被多个质因子整除） 可以用$2^k$的算法求出所有的质因子组合，计算每种组合的$p_i$乘积，通过容斥原理处理结果 [题在这](http://acm.hdu.edu.cn/showproblem.php?pid=4135) [具体实现代码](https://www.luogu.org/paste/m2s90fs6) ------------