快速沃尔什变换 FWT

题意：

给定长度为 $2^n$ 两个序列 $A,B$，设
$C_i=\sum_{(j\operatorname\circ k) = i}A_j \times B_k$
分别当 $\operatorname\circ$ 是 or, and, xor 时求出 $C$。

输入格式：

第一行，一个整数 $n$。

第二行，$2^n$ 个数 $A_0, A_1, \ldots, A_{2^n-1}$。

第三行，$2^n$ 个数 $B_0, B_1, \ldots, B_{2^n-1}$。

输出格式：

三行，每行 $2^n$ 个数，分别代表 $\operatorname\circ$ 是 or, and, xor 时 $C_0, C_1, \ldots, C_{2^n-1}$ 的值$\bmod 998244353$。

数据范围：

$1 \le n \le 17$。

$\mathcal{Part}\ 0$ 简介

在 OI 中，FWT 是用于解决对下标进行位运算卷积问题的方法。

具体地，对于已知序列 $a,b$ ，FWT 可以在 $\mathcal{O}(n \log n)$ 的复杂度内计算出

$c_i=\sum_{i=(j \operatorname{\circ} k)} a_j b_k$

其中 $\operatorname{\circ}$ 为二元位运算的一种。在本题中即为 $\lor,\,\land,\,\oplus$ （或/与/异或）

FWT 的灵感来源于 FFT ，具体思路详见参考文献2。本文仅介绍基本的原理。

$\mathcal{Part}\ 1$ 或运算

计算

$c_i=\sum_{i=(j \operatorname\lor k)} a_j b_k$

由于 $(j \lor k) = i,~(k \lor i) = i$ 可推出 $((j \lor k) \lor i) = i$ 。

考虑构造 $f_a(i) = \sum_{(j \lor i) = i}a_j$ ，那么

$\begin{aligned} f_a \times f_b & =\left(\sum_{(j \lor i)=i} a_j\right)\left(\sum_{(k \lor i)=i} b_k\right) \\[6pt]& =\sum_{(j \lor i) = i}\sum_{(k \lor i)=i} a_j b_k \\[6pt]& =\sum_{((j \lor k) \lor i) = i} a_j b_k \\[6pt]& =f_c \end{aligned}$

考虑如何求 $f_a$ ，令 $a_0$ 为 $a$ 中下标最高位为 $0$ 的那部分，$a_1$ 表示 $a$ 中下标最高位为 $1$ 的那部分，则

$f_a = f_{a_0} \cup (f_{a_0} + f_{a_1})$

分治即可。反正，我们要转换回 $a$ ，根据上式则有

$a = a_0 \cup (a_1 - a_0)$

提示：上述公式中 $\cup$ 表示序列的拼接，$+$ 和 $-$ 表示对应位置相加减。

这部分的代码：

void OR(int *f, int x = 1)
{
    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++) add(f[i + j + k], f[i + j] * x % mod);
} // a -> f(a) 则 x = 1, f(a) -> a 则 x = - 1

$\mathcal{Part}\ 2$ 与运算

和或运算同理，直接贴代码了。

void AND(int *f, int x = 1)
{
    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++) add(f[i + j], f[i + j + k] * x % mod);
} // a -> f(a) 则 x = 1, f(a) -> a 则 x = - 1

$\mathcal{Part}\ 3$ 异或运算

定义 $x\otimes y = \mathrm{popcount}(x\land y) \bmod 2$ ，即 $x,y$ 的与在二进制下 $1$ 的个数

那么 $(i \otimes j) \oplus (i \otimes k) = i \otimes (j \oplus k)$

考虑构造

$f_a(i) = \sum_{(i\otimes j) = 0} a_j - \sum_{(i\otimes j) = 1}a_j$

那么

$\small \begin{aligned} f_a\times f_b & =\left(\sum_{(i \otimes j)=0} a_j-\sum_{(i \otimes j)=1} a_j\right)\left(\sum_{(i \otimes k)=0} b_k-\sum_{(i \otimes k)=1} b_k\right) \\[6pt]& =\left(\sum_{(i \otimes j)=0} a_j\right)\left(\sum_{(i \otimes k)=0} b_k\right)-\left(\sum_{(i \otimes j)=0} a_j\right)\left(\sum_{(i \otimes k)=1} b_k\right) -\left(\sum_{(i \otimes j)=1} a_j\right)\left(\sum_{(i \otimes k)=0} b_k\right)+\left(\sum_{(i \otimes j)=1} a_j\right)\left(\sum_{(i \otimes k)=1} b_k\right) \\[6pt]& =\sum_{(i \otimes(j \oplus k))=0} a_j b_k-\sum_{(i \otimes(j \oplus k))=1} a_j b_k \\[6pt]& =f_c \end{aligned}$

因此

$f_a = (f_{a_0} + f_{a_1})\cup(f_{a_0} - f_{a_1}) \\[6pt] a = \frac{a_0 + a_1}{2} \cup \frac{a_0 - a_1}{2}$

提示：这里 $\frac{1}{2}$ 也是对应位置乘上 $\frac{1}{2}$ 的意思。

这部分的代码：

void XOR(int *f, int x = 1)
{
    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++)
            {
                f[i + j] = (f[i + j] + f[i + j + k]) % mod;
                f[i + j + k] = (f[i + j] + mod - 2 * f[i + j + k] % mod) % mod;
                f[i + j] = f[i + j] * x % mod; f[i + j + k] = f[i + j + k] * x % mod;
            }
} // a -> f(a) 则 x = 1, f(a) -> a 则 x = 1 / 2

注意这里是 $\frac{1}{2}$ 。

$\mathcal{Part}\ 4$ 完整实现

时间复杂度 $\mathcal{O}(n \log n)$ ，其中 $n$ 是序列的长度

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1 << 17) + 15)

const int inv2 = 499122177;
int n, A[N], B[N], a[N], b[N];
void OR(int *f, int x = 1)
{
    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++) add(f[i + j + k], f[i + j] * x % mod);
}
void AND(int *f, int x = 1)
{
    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++) add(f[i + j], f[i + j + k] * x % mod);
}
void XOR(int *f, int x = 1)
{
    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++)
            {
                f[i + j] = (f[i + j] + f[i + j + k]) % mod;
                f[i + j + k] = (f[i + j] + mod - 2 * f[i + j + k] % mod) % mod;
                f[i + j] = f[i + j] * x % mod; f[i + j + k] = f[i + j + k] * x % mod;
            }
}
void init() { rep(i, 0, n - 1) { a[i] = A[i]; b[i] = B[i]; } }
void print(int *f) { rep(i, 0, n - 1) cout << f[i] << " \n"[i == n - 1]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> m; n = 1 << m;
    rep(i, 0, n - 1) { cin >> A[i], A[i] %= mod; }
    rep(i, 0, n - 1) { cin >> B[i], B[i] %= mod; }
    
    init(); OR(a); OR(b);
    rep(i, 0, n - 1) a[i] = a[i] * b[i] % mod;
    OR(a, mod - 1); print(a);

    
    init(); AND(a); AND(b);
    rep(i, 0, n - 1) a[i] = a[i] * b[i] % mod;
    AND(a, mod - 1); print(a);

    init(); XOR(a); XOR(b);
    rep(i, 0, n - 1) a[i] = a[i] * b[i] % mod;
    XOR(a, inv2); print(a);
    return 0;
}