题目描述

给定两个长度为 $2^n$ 的序列 $a_0,a_1,\cdots,a_{2^n-1}$ 和 $b_0,b_1,\cdots,b_{2^n-1}$，你需要求出一个序列 $c_0,c_1,\cdots,c_{2^n-1}$，其中 $c_k$ 满足：

$$c_k=\sum_{\substack{i\& j=0 \\\ i\mid j=k}} a_i b_j$$

其中$~\mid~$表示按位或，$\&$表示按位与。

答案对 $10^9+9$ 取模。

过程

在没有条件 $i \& j = 0$ 时，这就是一个普通的 FWT 卷积，考虑如何消掉这个条件。

若有一个序列 $f$，我们重新定义它的值为 $f’$，$p(x)$ 表示 $x$ 二进制表示下 $1$ 的个数。

$f’_{j,i}\left\{\begin{array}{l} f_i,& p(i) = j,\\ 0, & otherwise. \end{array}\right.$

于是发现当 $p(i) + p(j) = p(k)$ 且 $i | j = k$ 时，一定满足 $i \& j = 0$，所以我们只需在 FWT 的基础上多增加一维即可。

时间复杂度 $O(n^2 2^n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 21, mod = 1e9 + 9;
int a[N][1 << N], b[N][1 << N], c[N][1 << N];

int p(int x) {return __builtin_popcount(x);}

void OR(int *a, int n, int x) {
    for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for (int i = 0; i < n; i += o)
            for (int j = 0; j < k; j ++ )
                a[i + j + k] = ((a[i + j + k] + a[i + j] * x) % mod + mod) % mod;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < (1 << n); i ++ ) scanf("%d", &a[p(i)][i]);
    for (int i = 0; i < (1 << n); i ++ ) scanf("%d", &b[p(i)][i]);
    for (int i = 0; i <= n; i ++ ) OR(a[i], 1 << n, 1), OR(b[i], 1 << n, 1);
    for (int i = 0; i <= n; i ++ ) {
        for (int j = 0; j <= i; j ++ )
            for (int k = 0; k < (1 << n); k ++ )
                c[i][k] = (c[i][k] + 1ll * a[j][k] * b[i - j][k] % mod) % mod;
        OR(c[i], 1 << n, -1);
    }
    for (int i = 0; i < (1 << n); i ++ ) printf("%d ", c[p(i)][i]);
    return 0;
}