【CSU1911】Card Game(FWT)

题面

vjudge
题目大意：
给定两个含有\(n\)个数的数组
每次询问一个数\(x\)，回答在每个数组中各选一个数，或起来之后的结果恰好为\(x\)的方案数。

题解

\(FWT\)的模板题
\(FWT\)写起来是真的舒服

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
inline int read()
{RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t;
}
inline int gi()
{int x=0;char ch[20];scanf("%s",ch+1);for(int i=1,l=strlen(ch+1);i<=l;++i)x=(x<<1)+(ch[i]-48);return x;
}
int n,m,Q,N;
ll a[1<<19],b[1<<19];
void FWT(ll *P,int opt)
{for(int i=2;i<=N;i<<=1)for(int p=i>>1,j=0;j<N;j+=i)for(int k=j;k<j+p;++k)P[k+p]+=P[k]*opt;
}
int main()
{int T=read();for(int tt=1;tt<=T;++tt){printf("Case #%d:\n",tt);n=read();m=read();N=1<<m;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=1;i<=n;++i)a[gi()]++;for(int i=1;i<=n;++i)b[gi()]++;FWT(a,1);FWT(b,1);for(int i=0;i<N;++i)a[i]*=b[i];FWT(a,-1);Q=read();while(Q--)printf("%lld\n",a[gi()]);}return 0;
}