【CF449D】Jzzhu and Numbers

· · 题解

题目

提供一个非容斥做法——FWT

我们发现我们要求的东西就是一个背包，只不过是在and意义下的

自然有

dp_{i,j}=\sum_{k\&a_i=j}dp_{i-1,k}+dp_{i-1,j}

我们发现这个柿子本质上就是一个和卷积

于是两边取fwt，我们就可以得到一个暴力fwt的代码

for(re int i=1;i<=n;i++) {
        memset(A,0,sizeof(A));
        A[a[i]]=1;Fwtand(A,1);
        for(re int j=0;j<len;j++) S[j]=S[j]+S[j]*A[j];
}
Fwtand(S,-1);

我们发现其实fwt的正向变换求得是超集和，又因为我们这里只有一个A[a[i]]=1，所以所有A_j最多就是1，A_j=1的时候会使得S_j翻倍，所以整体下来我们只需要关心S_j翻了多少倍

显然有多个a_i是j的超集就能翻多少倍，于是我们对A整体来一个fwt就好了

但是非常蛇皮的一点就是当a全是0的时候会把空集算入答案，因此需要特判一下

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=2500005;
const int mod=1e9+7;
inline int read() {
    char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int len,n,M;
LL S[maxn],A[maxn],a[maxn],pw[maxn];
inline void Fwt(LL *f,int o,int mod) {
    for(re int i=2;i<=len;i<<=1)
        for(re int ln=i>>1,l=0;l<len;l+=i)
            for(re int x=l;x<l+ln;++x)
                f[x]+=o*f[ln+x],f[x]=(f[x]+mod)%mod;
}
int main() {
    n=read();
    for(re int i=1;i<=n;i++) a[i]=read(),M=max(M,a[i]);
    len=1;while(len<=M) len<<=1;
    pw[0]=1;
    for(re int i=1;i<=n;i++) pw[i]=(pw[i-1]+pw[i-1])%mod;
    for(re int i=1;i<=n;i++) A[a[i]]++;
    Fwt(A,1,mod-1);
    for(re int i=0;i<len;i++) A[i]=pw[A[i]];
    Fwt(A,-1,mod);
    if(A[0]==pw[n]) std::cout<<A[0]-1;
    else std::cout<<A[0];
    return 0;
}