欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【容斥原理】-训练总结

程序员文章站 2022-05-08 19:06:14
...

1. HDU - 2841 在n*m(n<=1e5,m<1e5)的矩阵中,每一个格子都有一棵树,小明站在(0,0),问他可以看到多少棵不被遮住的树?分析:当两棵树与小明在三点直线上,则小明只能看见一棵树,可以得出所有y/x==y0/x0这样的点(x,y)只能看见最简的(x,y),即x与y互质,那么小明看见不同树的个数就等于n,m中互质的数的对数。容斥原理可以求出一个集合内的数与一个数互质的个数。答案就可以通过容斥求出来。

2.HDU - 3929 设F(x) = (1+x)^a1 + (1+x)^a2 + ... + (1+x)^am,(m<=15,ai<=2^45)化简后求有多少项的系数是奇数?分析:(1+x)^n的第i项的系数是C(n,i-1)。由二项式定理当n&k==k时 C(n,k)为奇数。可知(1+x)^n的系数为奇数的项由2^t(其中t是n二进制表示中1的个数)。然后就可以用容斥定理求出答案,注意两个奇数项合并会变成偶数项,所以要减掉。

3.HDU - 4059 求所有与n互质的数的四次方和?分析:求一个集合与一个数互质的个数的变种,先推出四次方求和公式,然后i可以在容斥的过程中求出答案。

4.HDU - 4336 小明要收集n种卡片,一包干脆面只可能出现一张卡片,每种卡片出现概率为pi,求收集所有卡片的期望。分析:很明显的容斥,答案为收集一张的总期望-收集两张的总期望+·········奇加偶减。

5.HDU - 4390 对于等式a1∗a2∗...∗an=b1∗b2∗…∗bn(ai>1).,已知b数组,求有多少种可能的a数组,a数组中每个数都大于1。
分析:题目可以转化成把一个整数拆分成n个整数相乘,这个整数可以分解成m个质因子,每个因子出现次数为xi ,如果ai 可以为1,则直接可以转化为一种放球问题,把x个相同的球放到n个盒子里。有m种球。答案就为 【容斥原理】-训练总结C(n+xi−1,n−1) 但是题目要求ai>1 所以要用容斥定理排除不符合要求的方案。

6.HDU - 4790小明和小红每个人在给定区间(小明(a,b)小红(c,d))内猜一个数,问他们的和膜p等于m的概率。可以先求(1,n)(1,m)的期望点的个数,然后容斥。(1,n)(1,m)可以分为三段等差数列来求。

7.HDU - 5072给n个数,求能找到多少种三个数两两互质,和三个数两两不互质的个数。满足条件的不太好求,我们可以求不满足条件的,即求两个数中两个数互质两个数不互质的个数,可以用容斥求出一个数与一个集合互质的个数,然后求出所有的不满足条件的个数。

8.HDU - 5155在一个n*m的矩阵中每一行每一列都有一个小球,问小球有多少种摆放方法? 分析:可以先在每一行放置一个小球,然后在列的层次用容斥求解。

9.HDU - 5468 给一棵n个点n-1条边的树,1为根,求每个子树中与子树的根互质的树的个数。分析:可以用dfs序把树变成一条链,就可以变成在求集合内的数与一个数互质的数的个数。

//一般用以下算法求集合内与一个数互质的个数


//求集合内与n不互质的数的个数
//cnt[i]存的是集合内含约束i的数的个数
int nu,pri[100],cnt[N];
int solve(int n)
{
    nu=0;
    int ret=0;
    for(int j=2;j*j<=n;j++)
    {
        if(n%j==0)
        {
            pri[nu++]=j;
            while(n%j==0)n/=j;
        }
    }
    if(n!=1)pri[nu++]=n;
    int tim=1<<nu,tem,num;
    for(int k=1;k<tim;k++)
    {
        num=0;
        tem=1;
        for(j=0;j<nu;j++)
            if(k&(1<<j))
                tem*=pri[j],num++;
        if(num&1)
            ret+=cnt[tem];
        else
            ret-=cnt[tem];
    }
    return ret;
}