FWT
快速沃尔什变换，用来解决位运算相关的卷积。常见的有与、或、异或三种。
P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)
给定长度为 \(2^n\) 两个序列 \(A,B\)，设
\[C_i=\sum_{j\oplus k = i}A_j \times B_k \]分别当 \(\oplus\) 是 or,and,xor 时求出 \(C\)。
\(n\le 17\)。
\(\operatorname{merge}(A, B)\) 表示将数列 \(B\) 拼接到数列 \(A\) 后面形成的新数列。
考虑构造一种可逆的线性变换，记 \(A\) 变换后为 \(\hat{A}\)，那么满足
\[C = A * B \Leftrightarrow \hat{C} = \hat{A} \times \hat{B}
\]
其中 \(\times\) 号表示对应位相乘，\(*\) 号是卷积。然后求出 \(\hat{C}\) 的逆变换即可。
因为变换是线性的，所以 \(\hat{(A + B)} = \hat{A} + \hat{B}\)，其中 \(+\) 表示对应位相加。
然后考虑如何构造这个变换。
or
设现在数列长度为 \(2 ^ n\)，\(A_0\) 表示 \(A\) 的前 \(2 ^ {(n - 1)}\) 个数，其下标二进制下第 \(n\) 位为 \(0\)。\(A_1\) 表示 \(A\) 的后 \(2 ^ {(n - 1)}\) 个数，其下标二进制下第 \(n\) 位为 \(1\)。\(B_0, B_1, C_0, C_1\) 类似。
显然 \(C_0 = A_0 * B_0, C_1 = A_0 * B_1 + A_1 * B_0 + A_1 * B_1\)，即 \(\hat{C_0} = \hat{A_0} \times \hat{B_0}\)