脚本宝典收集整理的这篇文章主要介绍了容斥定理，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

其实容斥很早就学过了，原理很简单，公式也是，但是运用起来却发现异常困难。 在网上查阅了很多资料，感觉容斥还是偏运用吧，这里就整理一些题目。

具有性质(A)或者(B)的元素个数，等于具有性质(A)或者(B)的元素个数的和，减去具有性质(A)和(B)的元素的个数，是的计算的结果无重无漏。 先把公式写在这： (|A_1 cup A_2cup...A_m| = suMLimITs_{1leq i leq m}|A_i|-sumlimits_{1leq i <jleq m}|A_icap A_j|+sumlimits_{1leq i <j<kleq m}|A_icap A_jcap A_k|-...+(-1)^{m-1}|A_1cap A_2cap ... cap A_m|)

错位排序

错位排序的(DP)推理方式在我之前的博客已经提到过，现在尝试用容斥的思路进行推导。

假设集合(S)为(1，2，...，n)的所有全排列，(|S|=n!)。定义(S_i)为数字(i)排在(i)位置上的全排列，因为数字(i)不动，所以 (|S_i| = (n-1)!【i = 1，2，....，n】) 依次类推可以得到固定(k)个位置时的全排列个数，((n-k)!)。

现在我们定义(D_n)为每个元素都不在自己位置上的排列数。

由容斥定理： (D_n = |S|-sumlimits_{1leq i leq n}|S_i|+sumlimits_{1leq i <jleq n}|S_icap S_j|+...+(-1)^{n-1}|S_1cap S_2cap...cap S_n|\=n!(1-frac{1}{1!}+frac{1}{2!}-...pmfrac{1}{n!}))

欧拉函数

(VARphi(n))表示为([1,n])中与(n)互质的数。 特别的：(p)为素数时(varphi(p) = p-1) 并且(gcd(a,b)== 1)时，(varphi(ab)=varphi(a)varphi(b)) 下面用容斥求一下欧拉函数： 将(N)分解为素数的乘积，(N = p_1^{r_1}p_2^{r_2}...p_k^{r_k}) 设(A_i)表示(1)到(N)中(p_i)倍数的集合 ，有(|A_i| = lfloor{frac{N}{p_i}}rfloor) 对于(p_i neq p_j), (|A_i cap A_j| = lfloor frac{N}{p_ip_j}rfloor) 依次类推，可以得到若干个数相乘的集合， 最后用容斥得到公式（这个公式好像挺难推的） (varphi(N) = N(1-frac{1}{p_1})(1-frac{1}{p_2})...(1-frac{1}{p_k}))

给两个求欧拉函数的板子：

//基于素因数分解求欧拉函数的算法
ll get_phi(ll x){
    ll res = x;
    for(ll i = 2;i*i <= x;i++){
        if(x%i == 0){
            res = res/i*(i-1);
            while(x%i == 0) x/=i;
        }
    }
    if(x!=1) res = res/x*(x-1);
    return res;
}
//利用埃式筛，实现预处理
ll phi[N];
void init(){
    for(ll i = 0;i < N;i++) phi[i] = i;
    for(ll i = 2;i < N;i++){
        if(phi[i] == i){
            for(ll j = i;j < N;j+=i){
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
}

脚本宝典总结

以上是脚本宝典为你收集整理的容斥定理全部内容，希望文章能够帮你解决容斥定理所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。