[Codeforces 449D]D. Jzzhu and Numbers

這題可以用排容原理來做

如果序列全部都是0，那答案就是$2^{N}$了
可是在其他的情況我們會多算，那要怎麼扣掉呢？
假如對於每個$s$，我們算出有幾個$A_{i}$符合$A_{i}\&s=s$，叫它$f(s)$好了，那答案就是$\sum_{s=0}^{2^{20}}(-1)^{CntBit(s)}2^{f(s)}$了(取20是因為不管$A_{i}$怎麼&都一定$\leq 2^{20}-1$)

關鍵是怎麼快速算出$f(s)$

我們可以考慮一個二維DP，$DP[i][s]$代表有幾個$A_{i}$，$s$的前$i$個bit中是$1$的，$A_{i}$的那幾個bit也要是$1$，而後面$20-i$個bit，$A_{i}$和$s$要完全相同

因此，我們就可以一個bit一個bit慢慢地算出$f(s)$了

$DP[0][s]$可以直接算
如果$s$的第$i$個bit是$0$，$DP[i][s]=DP[i-1][s]+DP[i-1][s+2^{i-1}]$
如果$s$的第$i$個bit是$1$，$DP[i][s]=DP[i-1][s]$

因此，$DP[20][s]$就是$f(s)$了，應用在上述的排容原理即可算出答案

時間複雜度：$O(N+2^{20}*20)$

code:

#include<cstdio>
#include<cassert>
using namespace std;
typedef long long LL;
const LL MOD=1000000007LL;
int N;
LL CNT[21][1<<20],POW[1000001];
int CntBit(int x)
{
    x=(x&0x55555555)+((x&0xaaaaaaaa)>>1);
    x=(x&0x33333333)+((x&0xcccccccc)>>2);
    x=(x&0x0f0f0f0f)+((x&0xf0f0f0f0)>>4);
    x=(x&0x00ff00ff)+((x&0xff00ff00)>>8);
    x=(x&0x0000ffff)+((x&0xffff0000)>>16);
    return x;
}
int main()
{
//    freopen("in.txt","r",stdin);
    POW[0]=1LL;
    for(int i=1;i<=1000000;i++)POW[i]=(POW[i-1]*2LL)%MOD;
    while(scanf("%d",&N)==1)
    {
        for(int s=0;s<(1<<20);s++)CNT[0][s]=0LL;
        for(int i=0,v;i<N;i++)scanf("%d",&v),CNT[0][v]++;
        for(int i=1;i<=20;i++)
        {
            for(int s=0;s<(1<<20);s++)
            {
                if(s&(1<<(i-1)))CNT[i][s]=CNT[i-1][s];
                else CNT[i][s]=CNT[i-1][s]+CNT[i-1][s+(1<<(i-1))];
            }
        }
        LL ans=0LL;
        for(int s=0;s<(1<<20);s++)
        {
            if(CntBit(s)&1)(ans-=POW[CNT[20][s]])%=MOD;
            else (ans+=POW[CNT[20][s]])%=MOD;
        }
        printf("%I64d\n",(ans%MOD+MOD)%MOD);
    }
    return 0;
}