CF914G Sum the Fibonacci

CF914G Sum the Fibonacci

洛谷Sum the Fibonacci

题目大意

给你一个长度为$n$的数组$s$，定义五元组$(a,b,c,d,e)$是合法的当且仅当：

• $1\le a,b,c,d,e\le n$
• $(s_a|s_b)\&s_c\&(s_d\oplus s_e)=2^i,i\in Z$
• $s_a\&s_b=0$

对于所有合法的五元组$(a,b,c,d,e)$，求$\sum f(s_a|s_b)\times f(s_c)\times f(s_d\oplus s_e)$

$f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}(i\ge 2)$

输出答案对$10^9+7$取模后的值。

$1\le n\le 10^6,0\le s_i<2^{17}$

题解

前置知识：快速沃尔什变换（$FWT$）

令$i=s_a\&s_b,j=s_c,k=s_d\oplus s_e$

题意即求

$$\sum _p\sum _{i\&j\&k=2^p}{f}_i\times f_j\times f_k\times (\sum _{s_a|s_b=i,s_a\&s_b=0}1)\times (\sum _{s_c=j}1)\times (\sum _{s_d\oplus s_e=k}1)$$

令$p_i$表示$i$在数组$s$中出现的次数，那么

$(\sum _{s_a|s_b=i,s_a\&s_b=0}1)=\sum _{x|y=i,x\&y=0}{p}_x\times p_y$

$(\sum _{s_c=j}1)=p_j$

$(\sum _{s_d\oplus s_e=k}1)=\sum _{i\oplus j=k}{p}_i\times p_j$

第二个式子很好求。对于第一个式子和第三个式子，用$FWT$的子集卷积和异或卷积，分别用$O(m{\log }^{2}m),O(m\log m)$的时间复杂度求出，其中$m=2^{17}$。

code

#include<bits/stdc++.h>
using namespace std;
int n,x,cnt[1<<17];
long long ans=0,f[1<<17],s[1<<17],t[20][1<<17],a[1<<17],b[1<<17],c[1<<17],v[1<<17];
const long long mod=1e9+7,ny2=5e8+4;
void pt(long long *w){for(int i=0;i<1<<17;i++) w[i]=s[i];
}
void fwt_or(long long *w,int fl){for(int s=2;s<=1<<17;s<<=1){int mid=s>>1;for(int v=0;v<1<<17;v+=s){for(int i=0;i<mid;i++){w[v+mid+i]=(w[v+mid+i]+fl*w[v+i]+mod)%mod;}}}
}
void fwt_and(long long *w,int fl){for(int s=2;s<=1<<17;s<<=1){int mid=s>>1;for(int v=0;v<1<<17;v+=s){for(int i=0;i<mid;i++){w[v+i]=(w[v+i]+fl*w[v+mid+i]+mod)%mod;}}}
}
void fwt_xor(long long *w,int fl){for(int s=2;s<=1<<17;s<<=1){int mid=s>>1;for(int v=0;v<1<<17;v+=s){for(int i=0;i<mid;i++){long long t1=w[v+i],t2=w[v+mid+i];w[v+i]=(t1+t2)%mod;w[v+mid+i]=(t1-t2+mod)%mod;if(fl==-1){w[v+i]=w[v+i]*ny2%mod;w[v+mid+i]=w[v+mid+i]*ny2%mod;}}}}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x);++s[x];}f[0]=0;f[1]=1;cnt[1]=1;for(int i=2;i<1<<17;i++){cnt[i]=cnt[i-(i&(-i))]+1;f[i]=(f[i-1]+f[i-2])%mod;}for(int i=0;i<1<<17;i++){t[cnt[i]][i]=s[i];}for(int i=0;i<=17;i++){fwt_or(t[i],1);}for(int i=0;i<=17;i++){for(int j=0;j<=i;j++){for(int k=0;k<1<<17;k++){v[k]=(v[k]+t[j][k]*t[i-j][k]%mod)%mod;}}fwt_or(v,-1);for(int j=0;j<(1<<17);j++){if(cnt[j]==i) a[j]=v[j];v[j]=0;}}pt(b);pt(c);fwt_xor(c,1);for(int i=0;i<1<<17;i++){c[i]=c[i]*c[i]%mod;}fwt_xor(c,-1);for(int i=0;i<1<<17;i++){a[i]=a[i]*f[i]%mod;b[i]=b[i]*f[i]%mod;c[i]=c[i]*f[i]%mod;}fwt_and(a,1);fwt_and(b,1);fwt_and(c,1);for(int i=0;i<1<<17;i++){v[i]=a[i]*b[i]%mod*c[i]%mod;}fwt_and(v,-1);for(int i=1;i<1<<17;i<<=1){ans=(ans+v[i])%mod;}printf("%lld",ans);return 0;
}