题目描述: 给你两个二进制数的集合，给出q次询问，输出两个集合之间元素或的值等于查询值的种数。
题目链接: Card Game
快速沃尔什变换详解请看快速沃尔什变换详解
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
const int maxn = 1 << 18;
LL a[maxn], b[maxn];
int n, m;
char s[20];
void FWT(LL a[], int n)
{
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];
int y = a[i + j + d];
a[i + j + d] = x + y;
}
}
}
}
void UFWT(LL a[], int n)
{
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];
int y = a[i + j + d];
a[i + j + d] = y - x;
}
}
}
}
void solve(LL a[], LL b[], int n)
{
FWT(a, n);
FWT(b, n);
for (int i = 0; i < n; i++) {
a[i] = a[i] * b[i];
}
UFWT(a, n);
}
int main()
{
int t, q;
scanf("%d", &t);
for (int cas = 1; cas <= t; cas++) {
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
scanf("%d%d", &n, &m);
int l, x;
for (int i = 0; i < n; i++) {
x = 0;
scanf("%s", s);
l = strlen(s);
for (int j = 0; j < l; j++)
x = (x << 1) + s[j] - '0';
a[x]++;
}
for (int i = 0; i < n; i++) {
x = 0;
scanf("%s", s);
l = strlen(s);
for (int j = 0; j < l; j++)
x = (x << 1) + s[j] - '0';
b[x]++;
}
solve(a, b, (1 << m));
scanf("%d", &q);
printf("Case #%d:\n", cas);
while (q--) {
scanf("%s", s);
x = 0;
l = strlen(s);
for (int i = 0; i < l; i++)
x = (x << 1) + s[i] - '0';
printf("%lld\n", a[x]);
}
}
return 0;
}
