【容斥原理】-训练总结

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;
}