首页 > 代码库 > codeforces 449D DP+容斥

codeforces 449D DP+容斥

2024-07-15 22:33:01   211人阅读

Jzzhu and Numbers
Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u
Submit Status
Appoint description: 

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

Input
3
2 3 3
Output
0
Input
4
0 1 2 3
Output
10
Input
6
5 2 0 5 2 1
Output
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 }

 


联系
我们