[51nod1407]与与与与

　　有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的个数

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 const int maxn=,modd=;

 int f[maxn],a[maxn],two[maxn],n1[maxn];

 int i,j,k,n,m;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while((rx<''||rx>'')&&rx!='-')rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;

 }

 inline void MOD(int &x){

     if(x>=modd)x-=modd;else if(x<)x+=modd;

 }

 int main(){

     n=read();int mx=(<<)-;register int i,j;

     for(i=;i<=n;i++)f[a[i]=read()]++;

     for(i=two[]=;i<=n;i++)MOD(two[i]=two[i-]<<);

     for(i=;i>=;i--)

         for(j=;j<=mx;j++)

             if(!((j>>i)&))f[j]+=f[j|(<<i)];

     int ans=;

     for(i=;i<=mx;i++){//printf("i:%d  f:%d\n",i,f[i]);

         n1[i]=n1[i>>]+(i&);

         if(n1[i]&)MOD(ans-=two[f[i]]);else MOD(ans+=two[f[i]]);

     }

     printf("%d\n",ans);

 }

巴特西

[51nod1407]与与与与

最新文章

热门文章