Hdu 3929 Big Coefficients (容斥原理二项式性质)

港控/mmm° 2022-08-26 04:55 18阅读 0赞

二项式定理有两个性质，这题只用到第一个。

性质1：若k表示把n转为二进制后所有位中1的个数，则(1 + x) ^ n中系数为奇数的个数为2 ^ k。

性质2：(1 + x) ^ n中的系数中 所有奇系数之和等于偶系数之和等于 2^(n-1)

以下内容参考了：http://hi.baidu.com/yy17yy/item/f703320adb5cafeb34990256

有三个集合ABC,则num(A∪B∪C)=num(A)+num(B)+num(C) -num(A∩B)-num(A∩C)-num(B∩C) +num(A∩B∩C)

容斥原理有一般有简单的递归式

dfs (int beg,set S,int sym)
    {
    	ans+=num(S)*sym;
    	for (int i=beg;i<=n;i++)
    		dfs(i,S∩A[i],sym*-1);
    }
    for (int i=1;i<=n;i++)
    	dfs(i,A[i],1);

题意：给出a1,a2,\`\`\`am，F(x) = (1+x)^a1 + (1+x)^a2 + \`\`\` + (1+x)^am，F(x)的展开式中系数为奇数的个数。

思路：每个(1 + x) ^ n都是一个集合，它的奇数次项的个数就是集合中元素的个数，算法是2^(系数的二进制里1的个数)，

两个集合的交: 比如系数w1,w2,集合的交的个数是2^(w1&w2的二进制里1的个数),

由于奇数次幂相交不一定是奇数次幂,所以所以要把偶数个集合的交的个数减掉,写一下式子,发现问题没有变复杂,只需把上面的递归式的sym由-1变为-2既可。

以三个集合ABC为例：num(A∪B∪C)-num(A∩B)-num(A∩C)-num(B∩C)+3\*num(A∩B∩C) 即为所求

也就是 num(A)+num(B)+num(C) -2\*num(A∩B)-2\*num(A∩C)-2\*num(B∩C) +4\*num(A∩B∩C)

#include <cstdio>
    
    __int64 ans,data[20];
    int n;
    
    int get (__int64 x)
    {//计算x的二级制位有多少个1
    	return x==0?0:get(x-(x&-x))+1;  //(x&-x)是取出最低位的1
    }
    
    void DFS (int begin,__int64 num,__int64 sym)
    {
    	ans+=((__int64)1<<get(num))*sym;
    	for (int i=begin+1;i<=n;i++)
    		DFS (i,num&data[i],-2*sym);
    }
    
    int main ()
    {
    	int T,i;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d",&n);
    		for (i=1;i<=n;i++)
                scanf("%I64d",&data[i]);
    		ans=0;
    		for (i=1;i<=n;i++)
    			DFS(i,data[i],1);
    		printf("Case #%d: %I64d\n",Cas,ans);
    	}
    	return 0;
    }