题目链接：/contest/914/problem/G
子集卷积+FWT的板子题，记一个子集卷积的板子
代码：
#include<bits/stdc++.h>#define xx first#define yy second#define mp make_pair#define pb push_backusing namespace std;typedef long long ll;typedef pair<int,int> pii;const int MOD=1e9+7;const int INV2=MOD-MOD/2;const int MAXN=1e6+5;const int M=(1<<17)+5;int s[MAXN],f[MAXN],g[18][M],h[18][M],d[MAXN];int A[M],B[M],C[M],D[M],cnt[M];void FMT(int *A,int o){for(int i=1;i<(1<<17);i<<=1)for(int j=0;j<(1<<17);j++)if(i&j) (A[j]+=A[j^i]*o)%=MOD;}void FWT(int a[],int n,int op){for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){int x=a[i+j],y=a[i+j+d];if(op==0) a[i+j]=(x+y)%MOD,a[i+j+d]=(x-y+MOD)%MOD;if(op==1) a[i+j]=(x+y)%MOD;}}void UFWT(int a[],int n,int op){for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){int x=a[i+j],y=a[i+j+d];if(op==0) a[i+j]=1LL*(x+y)*INV2%MOD,a[i+j+d]=(1LL*(x-y)*INV2%MOD+MOD)%MOD;if(op==1) a[i+j]=((x-y)%MOD+MOD)%MOD;}}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&s[i]);f[0]=0,f[1]=1;for(int i=2;i<M;i++)f[i]=(f[i-1]+f[i-2])%MOD;for(int i=1;i<M;i++)cnt[i]=__builtin_popcount(i);for(int i=1;i<=n;i++){d[s[i]]++;g[cnt[s[i]]][s[i]]++;B[s[i]]=(B[s[i]]+f[s[i]])%MOD;}for(int i=0;i<=17;i++) FMT(g[i],1);for(int i=0;i<=17;i++){for(int j=0;j<=i;j++)for(int k=0;k<(1<<17);k++)(h[i][k]+=1ll*g[j][k]*g[i-j][k]%MOD)%=MOD;FMT(h[i],-1);for(int k=0;k<(1<<17);k++) if(cnt[k]!=i) h[i][k]=0;//if(i!=17) FMT(h[i],1);}for(int i=0;i<=17;i++)for(int k=0;k<(1<<17);k++){A[k]=(A[k]+1LL*h[i][k]*f[k]%MOD)%MOD;}FWT(d,(1<<17),0);for(int i=0;i<(1<<17);i++)d[i]=(1LL*d[i]*d[i])%MOD;UFWT(d,(1<<17),0);for(int i=0;i<(1<<17);i++)C[i]=(C[i]+1LL*d[i]*f[i]%MOD)%MOD;FWT(A,(1<<17),1);FWT(B,(1<<17),1);FWT(C,(1<<17),1);for(int i=0;i<(1<<17);i++)D[i]=1LL*A[i]*B[i]%MOD*C[i]%MOD;UFWT(D,(1<<17),1);ll ans=0;for(int i=0;i<17;i++)ans=(ans+D[1<<i])%MOD;printf("%lld\n",ans);return 0;}
