题目链接
集合大小为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;
}