有n个整数，问从他们中取出若干个数字相与之后结果是0的有多少组。
答案比较大，输出对于 1,000,000,007 (1e9+7)取模后的结果。
Input
第一行输入一个整数n。(1<=n<=1,000,000).
第二行有n个整数a[0],a[1],a[2],...a[n-1]，以空格分开.(0<=a[i]<=1,000,000)
Output
对于每一组数据，输出一个整数。
又是没见过的姿势...
如果对于每个数x都可以算出a[i]&x==x的数的个数的话就可以算了。
f[i][j]表示 有多少个数 与j 得到的结果和j二进制表示下第i位到第20位相同（最低位为第0位），第0到i-1位都和j完全一样。
初始化f[20][i]=读入的数组中等于i的数的个数。
f[i][j]=
f[i+1][j]，j的第i位上是1
f[i+1][j]+f[i+1][j+2^i]，j的第i位上是0
最后再容斥统计一波，ans=sum{ -1^num1 *f[0][i] }。i=0..2^20-1,num1是i二进制下1的个数
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 const int maxn=1052333,modd=1000000007; 5 int f[maxn],a[maxn],two[maxn],n1[maxn]; 6 int i,j,k,n,m; 7 8 int ra,fh;char rx; 9 inline int read(){ 10 rx=getchar(),ra=0,fh=1; 11 while((rx<'0'||rx>'9')&&rx!='-')rx=getchar(); 12 if(rx=='-')fh=-1,rx=getchar(); 13 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh; 14 } 15 inline void MOD(int &x){ 16 if(x>=modd)x-=modd;else if(x<0)x+=modd; 17 } 18 int main(){ 19 n=read();int mx=(1<<20)-1;register int i,j; 20 for(i=1;i<=n;i++)f[a[i]=read()]++; 21 for(i=two[0]=1;i<=n;i++)MOD(two[i]=two[i-1]<<1); 22 for(i=19;i>=0;i--) 23 for(j=0;j<=mx;j++) 24 if(!((j>>i)&1))f[j]+=f[j|(1<<i)]; 25 int ans=0; 26 for(i=0;i<=mx;i++){//printf("i:%d f:%d ",i,f[i]); 27 n1[i]=n1[i>>1]+(i&1); 28 if(n1[i]&1)MOD(ans-=two[f[i]]);else MOD(ans+=two[f[i]]); 29 } 30 printf("%d ",ans); 31 }