题目链接
集合大小为n。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod = 1e9 + 9;
const int maxn = 1 << 21;
int a[22][maxn], b[22][maxn], c[22][maxn], cnt[maxn];
void fwt_or_mod(int* x, int len, int opt, int mod)
{
    for (int i = 1;i < len;i <<= 1)
    {
        for (int p = i << 1, j = 0;j < len;j += p)
        {
            for (int k = 0;k < i;k++)
            {
                if (opt == 1) x[i + j + k] = (x[j + k] + x[i + j + k]) % mod;
                else x[i + j + k] = (x[i + j + k] + mod - x[j + k]) % mod;
            }
        }
    }
}

int main(void)
{
    int n;
    scanf("%d", &n);
    int now = n;
    n = 1 << n;

    for (int i = 1;i <= n;i++)
        cnt[i] = cnt[i >> 1] + (i & 1);

    for (int i = 0;i < n;i++)
        scanf("%d", &a[cnt[i]][i]);
    for (int i = 0;i < n;i++)
        scanf("%d", &b[cnt[i]][i]);

    for (int i = 0;i <= now;i++)
        fwt_or_mod(a[i], n, 1, mod), fwt_or_mod(b[i], n, 1, mod);
    for (int i = 0;i <= now;i++)
        for (int j = 0;j <= i;j++)
            for (int len = 0;len < n;len++)
                c[i][len] = (c[i][len] + 1ll * a[j][len] * b[i - j][len]) % mod;
    for (int i = 0;i <= now;i++)
        fwt_or_mod(c[i], n, -1, mod);

    for (int i = 0;i < n;i++)
        printf("%d ", c[cnt[i]][i]);

    return 0;
}