Description
Jzzhu have n non-negative integers a1, a2, ..., an. We will call a sequence of indexes i1, i2, ..., ik(1 ≤ i1 < i2 < ... < ik ≤ n) a group of size k.
Jzzhu wonders, how many groups exists such that ai1 & ai2 & ... & aik = 0(1 ≤ k ≤ n)? Help him and print this number modulo1000000007(109 + 7). Operation x & y denotes bitwise AND operation of two numbers.
Input
The first line contains a single integer n(1 ≤ n ≤ 106). The second line contains n integers a1, a2, ..., an(0 ≤ ai ≤ 106).
Output
Output a single integer representing the number of required groups modulo 1000000007(109 + 7).
Sample Input
3
2 3 3
0
4
0 1 2 3
10
6
5 2 0 5 2 1
53
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 typedef __int64 LL; 7 const LL mod=1000000007; 8 const int maxn=1<<20; 9 int dp[20][1<<20]; 10 int a[1<<20]; 11 12 LL pow_mod(LL a,LL b) 13 { 14 LL ret=1;a%=mod; 15 while(b) 16 { 17 if(b&1) ret=ret*a%mod; 18 a=a*a%mod; 19 b>>=1; 20 } 21 return ret; 22 } 23 24 int main() 25 { 26 int n,i,j; 27 int ans,t,tt; 28 scanf("%d",&n); 29 for(i=1;i<=n;i++) scanf("%d",&a[i]); 30 memset(dp,0,sizeof(dp)); 31 for(i=1;i<=n;i++) 32 { 33 if(a[i]&1) 34 { 35 dp[0][ a[i] ]++;dp[0][ a[i]^1 ]++; 36 } 37 else dp[0][ a[i] ]++; 38 } 39 for(i=0;i<19;i++) 40 for(j=0;j<maxn;j++) 41 { 42 t=1<<(i+1); 43 if(j&t) 44 { 45 dp[i+1][j]+=dp[i][j];dp[i+1][ j-t ]+=dp[i][j]; 46 } 47 else dp[i+1][j]+=dp[i][j]; 48 } 49 ans=0; 50 for(j=0;j<maxn;j++) 51 { 52 t=1; 53 for(i=0;i<20;i++) 54 if((1<<i)&j) 55 t=-t; 56 tt=pow_mod(2,dp[19][j]); 57 tt--; 58 ans=((ans+t*tt)%mod+mod)%mod; 59 } 60 printf("%d\n",ans); 61 return 0; 62 }
codeforces 449D DP+容斥,布布扣,bubuko.com
原文：http://www.cnblogs.com/xiong-/p/3892681.html