这个东西好玄乎呀 首先就是它可以干什么： codeforces 914G 然后你就会说：“这tm什么鬼题！” 好，我们这次就是要解决这个问题，看完这篇你应该就可以掌握FWT 的代码了 我肯定是不会讲的，我们移步这里： http://picks.logdown.com/posts/179290-fast-walsh-hadamard-transform 看完之后应该差不多了 如果要看数学证明可以去这里： http://blog.csdn.net/zhshrs/article/details/54838466
先说上面那个题的做法吧： (sa|sb) ( s a | s b ) & sc s c & (sd ( s d ^ se) s e ) 我们记 ai=∑nj=1[sj=i] a i = ∑ j = 1 n [ s j = i ] ，也就是i在s中的出现次数 然后我们就可以把这三部分分开考虑（以&为分割） 我们计算3个数组A,B,C，分别代表三部分的答案 Ai=fibi∗∑j∑k[j A i = f i b i ∗ ∑ j ∑ k [ j | k=i][j k = i ] [ j & k=0]aj∗ak k = 0 ] a j ∗ a k Bi=fibi∗ai B i = f i b i ∗ a i Ci=fibi∗∑j∑k[j C i = f i b i ∗ ∑ j ∑ k [ j ^ k=i]aj∗ak k = i ] a j ∗ a k 第一部分就是子集卷积，可以直接 3n 3 n ，也可以 n22n n 2 2 n 第二部分直接算 第三部分就是个异或FWT 然后再把A,B,C卷起来就好辣（当然是与卷积辣） 然后枚举每一位算答案就好辣 时间复杂度： O(3n+n2n) O ( 3 n + n 2 n ) 代码在这里：
#include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<algorithm> #include<cstdlib> #define LL long long using namespace std; inline int read(){ int x=0,f=1;char ch=' '; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return x*f; } const LL N=1<<17,mod=1e9+7,inv=5e8+4; inline void FWT_AND(LL *a){ for(int d=1;d<N;d<<=1) for(int i=0;i<N;i+=d<<1) for(int j=0;j<d;++j){ LL x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y)%mod; } } inline void IFWT_AND(LL *a){ for(int d=1;d<N;d<<=1) for(int i=0;i<N;i+=d<<1) for(int j=0;j<d;++j){ LL x=a[i+j],y=a[i+j+d]; a[i+j]=(x-y+mod)%mod; } } inline void FWT_XOR(LL *a){ for(int d=1;d<N;d<<=1) for(int i=0;i<N;i+=d<<1) for(int j=0;j<d;++j){ LL x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y)%mod;a[i+j+d]=(x-y+mod)%mod; } } inline void IFWT_XOR(LL *a){ for(int d=1;d<N;d<<=1) for(int i=0;i<N;i+=d<<1) for(int j=0;j<d;++j){ LL x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y)*inv%mod;a[i+j+d]=(x-y+mod)*inv%mod; } } LL n,A[N],B[N],C[N],a[N],fib[N]; int main(){ fib[1]=1; for(int i=2;i<N;++i)fib[i]=(fib[i-1]+fib[i-2])%mod; n=read(); for(int i=1;i<=n;++i){ int x=read(); a[x]++; } for(int i=0;i<N;++i){ A[i]=0; B[i]=a[i]; C[i]=a[i]; } for(int i=0;i<N;++i){ int t=(N-1)&~i; for(int b=t;;b=(b-1)&t){ A[i|b]=(A[i|b]+a[i]*a[b])%mod; if(!b)break; } } FWT_XOR(C); for(int i=0;i<N;++i)C[i]=C[i]*C[i]%mod; IFWT_XOR(C); for(int i=0;i<N;++i)A[i]=A[i]*fib[i]%mod; for(int i=0;i<N;++i)B[i]=B[i]*fib[i]%mod; for(int i=0;i<N;++i)C[i]=C[i]*fib[i]%mod; FWT_AND(A); FWT_AND(B); FWT_AND(C); for(int i=0;i<N;++i)A[i]=A[i]*B[i]%mod*C[i]%mod; IFWT_AND(A); LL ans=0; for(int i=0;i<17;++i)ans=(ans+A[1<<i])%mod; printf("%I64d",ans); return 0; }然后我要说的就是代码 我们肯定不能用递归版的，常数大概3倍（不要问我怎么知道的，问rqy） 上面那个就是非递归版的 其实就和FFT差不多 而且比FFT好背 然后就没什么了 完结撒花❀
