快速沃尔什变换（FWT）是一类解决位运算卷积问题的算法。

        看下面一个式子：

        这明显是一个卷积，可以通过FFT或者NTT（MTT）解决，但是如果遇到了下面的情况：

        这里的$\bigoplus$是位运算（or、ans、xor），如何求卷积？这就是快速沃尔什变换解决的问题，它可以在$O(nlogn)$复杂度下解决问题。
        FWT的优化思想与FFT相同：构造映射tf，使得下面式子成立：

        前面的乘号$*$是卷积乘法。同样需要反向映射utf满足：

        只需要将tf和utf运算压至$O(nlogn)$即可。
        FWT中有着分治思想：将长度为2的方幂的序列一分为2，即将序列$A$分为$A_0$和$A_1$，记为$A=(A_0,A_1)$。则三类位运算的tf与utf构造方法如下：

or运算

and运算

xor运算

代码模板

        证明略。模板题。
        将FFT的板子改一改就可以得到FWT的板子，注意取模。除以2时需要转化为乘2的逆元499122177。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>

#define MOD 998244353
using namespace std;
typedef long long ll;
ll f[1 << 20], g[1 << 20], a[1 << 20], b[1 << 20];
int n;

inline void FWT_or(ll *s, int type) {
    for (int mid = 1; mid < n; mid <<= 1) {
        for (int len = mid << 1, j = 0; j < n; j += len) {
            for (int k = 0; k < len >> 1; k++) {
                s[j + mid + k] = (s[j + mid + k] + type * s[j + k]) % MOD;
            }
        }
    }
}

inline void FWT_and(ll *s, int type) {
    for (int mid = 1; mid < n; mid <<= 1) {
        for (int len = mid << 1, j = 0; j < n; j += len) {
            for (int k = 0; k < len >> 1; k++) {
                s[j + k] = (s[j + k] + type * s[j + mid + k]) % MOD;
            }
        }
    }
}

inline void FWT_xor(ll *s, int type) {
    for (int mid = 1; mid < n; mid <<= 1) {
        for (int len = mid << 1, j = 0; j < n; j += len) {
            for (int k = 0; k < len >> 1; k++) {
                ll v = s[j + k];
                s[j + k] = (s[j + k] + s[j + mid + k]) % MOD, s[j + k + mid] = (v - s[j + mid + k]) % MOD;
                if (type == -1)s[j + k] = s[j + k] * 499122177 % MOD, s[j + k + mid] = s[j + k + mid] * 499122177 % MOD;
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    n = 1 << n;
    for (int i = 0; i < n; i++)cin >> f[i];
    for (int i = 0; i < n; i++)cin >> g[i];
    for (int i = 0; i < n; i++)a[i] = f[i], b[i] = g[i];
    FWT_or(a, 1), FWT_or(b, 1);
    for (int i = 0; i < n; i++)a[i] = a[i] * b[i] % MOD;
    FWT_or(a, -1);
    for (int i = 0; i < n; i++)cout << (a[i] + MOD) % MOD << " ";
    cout << endl;
    for (int i = 0; i < n; i++)a[i] = f[i], b[i] = g[i];
    FWT_and(a, 1), FWT_and(b, 1);
    for (int i = 0; i < n; i++)a[i] = a[i] * b[i] % MOD;
    FWT_and(a, -1);
    for (int i = 0; i < n; i++)cout << (a[i] + MOD) % MOD << " ";
    cout << endl;
    for (int i = 0; i < n; i++)a[i] = f[i], b[i] = g[i];
    FWT_xor(a, 1), FWT_xor(b, 1);
    for (int i = 0; i < n; i++)a[i] = a[i] * b[i] % MOD;
    FWT_xor(a, -1);
    for (int i = 0; i < n; i++)cout << (a[i] + MOD) % MOD << " ";
    return 0;
}