FWT

[CSU1911]Card Game

Posted by Dispwnl on February 28, 2019

题目

题目大意

给定两个长度为$n$的序列，求从这两个序列中各选出一个数使得它们的异或和为$x$的方案数，多组询问

Sample Input

1
4 4
1001 11 1100 1000
1110 1001 10 100
2
1100
111

Sample Output

Case #1:
2
1

题解

用$FWT$板子充数的我真是嗨到不行啊

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=(1<<18)+1;
int T,n,m,lim,Q,cnt;
LL a[MAX],b[MAX];
char s[21];
void FWT_OR(LL *A,int tt=1)
{
	for(int i=1;i<lim;i<<=1)
	  for(int l=i<<1,j=0;j<lim;j+=l)
	    for(int k=0;k<i;++k)
	      A[i+j+k]=A[i+j+k]+tt*A[j+k];
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m),lim=1<<m;
		memset(a,0,lim<<3);
		memset(b,0,lim<<3);
		for(int i=1,_n,x;i<=n;++i)
		  {
		  	scanf("%s",s),_n=strlen(s),x=0;
		  	for(int j=_n-1;j>=0;--j)
		  	  if(s[j]=='1') x+=(1<<_n-j-1);
		  	++a[x];
		  }
		for(int i=1,_n,x;i<=n;++i)
		  {
		  	scanf("%s",s),_n=strlen(s),x=0;
		  	for(int j=_n-1;j>=0;--j)
		  	  if(s[j]=='1') x+=(1<<_n-j-1);
		  	++b[x];
		  }
		FWT_OR(a),FWT_OR(b);
		for(int i=0;i<=lim;++i)
		  a[i]*=b[i];
		FWT_OR(a,-1),scanf("%d",&Q),printf("Case #%d:\n",++cnt);
		for(int i=1,x,_n;i<=Q;++i)
		  {
		  	scanf("%s",s),_n=strlen(s),x=0;
			for(int j=_n-1;j>=0;--j)
			  if(s[j]=='1') x+=(1<<_n-j-1);
			printf("%d\n",a[x]);
		  }
	}
	return 0;
}
FRIENDS