题目描述: 给你两个二进制数的集合，给出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;
}