CF 914 G Sum the Fibonacci —— 子集卷积，FWT

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int Max(int x,int y){return x>y?x:y;}
int const xm=(<<)+,mod=1e9+;
int n,p[xm],F[xm],f[][xm],g[xm],h[xm],t[xm],bin[],cnt[xm],inv2,lm;
ll pw(ll a,int b){ll ret=; for(;b;b>>=,a=a*a%mod)if(b&)ret=ret*a%mod; return ret;}
int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}
int cal(int s){int ret=; while(s)ret+=(s&),s>>=; return ret;}
int get(int x){int ret=; while(x)ret++,x>>=; return ret;}
void init()
{
F[]=; F[]=;
for(int i=;i<bin[lm];i++)F[i]=upt(F[i-]+F[i-]);
}
void fmt(int *a,int tp)
{
for(int d=;d<bin[lm];d<<=)
for(int s=;s<bin[lm];s++)
if(s&d)a[s]=upt(a[s]+a[s^d]*tp);
}
void fwt1(int *a,int tp)//&
{
for(int mid=;mid<bin[lm];mid<<=)
for(int j=,len=(mid<<);j<bin[lm];j+=len)
for(int k=;k<mid;k++)
a[j+k]=upt(a[j+k]+a[j+mid+k]*tp);
}
void fwt2(int *a,int tp)//^
{
for(int mid=;mid<bin[lm];mid<<=)
for(int j=,len=(mid<<);j<bin[lm];j+=len)
for(int k=;k<mid;k++)
{
int x=a[j+k],y=a[j+mid+k];
a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);
if(tp==-)a[j+k]=(ll)a[j+k]*inv2%mod,a[j+mid+k]=(ll)a[j+mid+k]*inv2%mod;
}
}
int main()
{
n=rd(); lm=;
bin[]=; for(int i=;i<=lm;i++)bin[i]=bin[i-]*;
for(int s=;s<bin[lm];s++)cnt[s]=cal(s);
int mx=;
for(int i=,x;i<=n;i++)x=rd(),p[x]++,mx=Max(mx,x);
lm=get(mx)+; init();
for(int s=;s<bin[lm];s++)f[cnt[s]][s]=p[s];
for(int i=;i<lm;i++)fmt(f[i],);
/*
for(int i=1;i<lm;i++)
{
for(int j=0;j<=i;j++)
for(int s=0;s<bin[lm];s++)
f[i][s]=(f[i][s]+(ll)f[j][s]*f[i-j][s])%mod;
for(int s=0;s<bin[lm];s++)if(cnt[s]!=i)f[i][s]=0;
}
for(int i=0;i<lm;i++)fmt(f[i],-1);
for(int s=0;s<bin[lm];s++)g[s]=f[cnt[s]][s];
*/
for(int i=;i<lm;i++)
{
memset(t,,sizeof t);
for(int j=;j<=i;j++)
for(int s=;s<bin[lm];s++)
t[s]=(t[s]+(ll)f[j][s]*f[i-j][s])%mod;
fmt(t,-);
for(int s=;s<bin[lm];s++)
if(cnt[s]==i)g[s]=upt(g[s]+t[s]);
} for(int s=;s<bin[lm];s++)h[s]=p[s];
inv2=pw(,mod-); fwt2(h,);
for(int s=;s<bin[lm];s++)h[s]=(ll)h[s]*h[s]%mod;
fwt2(h,-); for(int s=;s<bin[lm];s++)g[s]=(ll)g[s]*F[s]%mod;
for(int s=;s<bin[lm];s++)h[s]=(ll)h[s]*F[s]%mod;
for(int s=;s<bin[lm];s++)p[s]=(ll)p[s]*F[s]%mod;
fwt1(g,); fwt1(h,); fwt1(p,);
for(int s=;s<bin[lm];s++)g[s]=(ll)g[s]*h[s]%mod*p[s]%mod;
fwt1(g,-); int ans=;
for(int i=;i<lm;i++)ans=upt(ans+g[bin[i]]);
printf("%d\n",ans);
return ;
}