使用矩阵和张量积构造 FWT

对于位运算卷积 $C_k = \sum_{i \oplus j = k} A_i B_j$（其中 $\oplus$ 为 OR、AND 或 XOR）。

我们希望构造一个线性变换 $F$，使得变换后的点值可以直接相乘。

即 $F(C)_i = F(A)_i \cdot F(B)_i$，然后再通过逆变换 $F^{-1}$ 还原出 $C$。

OR 卷积

要求构造一个线性变换 $F(A) = M \cdot A$，满足：

为了找出矩阵 $M$ 必须满足的条件，我们将等式两边进行代数展开。

设我们要计算的 OR 卷积结果为数组 $C = A \cup B$，即：$$Ck = \sum{x \cup y = k} Ax By$$

根据矩阵乘法，$F(C)i = \sum{k} m{i, k} Ck$。

将 $C_k$ 的定义代入：$$F(C)i = \sum{k} m{i, k} \left( \sum{x \cup y = k} Ax By \right)$$

我们可以直接枚举所有的 $x$ 和 $y$：$$F(C)i = \sum{x} \sum{y} m{i, x \cup y} Ax By$$

这说明，在左边的多项式中，项 $A_x B_y$ 的系数是 $m_{i, x \cup y}$。

展开等式右边 $F(A)_i \cdot F(B)_i$

将变换的定义式直接相乘： $$ F(A)i \cdot F(B)i = \left( \sum{x} m{i, x} Ax \right) \cdot \left( \sum{y} m{i, y} By \right) $$ 利用乘法分配律展开： $$ F(A)i \cdot F(B)i = \sum{x} \sum{y} (m{i, x} \cdot m{i, y}) Ax By $$ 这说明，在右边的多项式中，项 $A_x B_y$ 的系数是 $(m_{i, x} \cdot m_{i, y})$。

为了让 $F(A \cup B)_i = F(A)_i \cdot F(B)_i$ 对于任意数组 $A$ 和 $B$ 都恒成立，根据多项式恒等定理，等式两边 $A_x B_y$ 的系数必须完全相等。

由此我们得到了 FWT 的基本约束： $m_{i, x \cup y} = m_{i, x} \cdot m_{i, y}$

现在我们将问题缩小到 1 位二进制（长度为 $2$，下标仅为 $0$ 和 $1$），利用刚才推导出的约束来求解 $2 \times 2$ 矩阵 $M_1$： $$ M1 = \begin{bmatrix} m{00} & m{01} \ m{10} & m_{11} \end{bmatrix} $$ 对于任意行 $i \in \{0, 1\}$，代入 $x, y \in \{0, 1\}$ 推导：

1. 当 $x=0, y=0$ 时：

   $m_{i, 0 \lor 0} = m_{i, 0} \cdot m_{i, 0} \implies m_{i, 0} = m_{i, 0}^2$

   解得 $m_{i, 0} = 0$ 或 $1$。但如果取 $0$，会导致矩阵的一整列为 $0$ 从而不可逆，因此必须取 $m_{i, 0} = 1$。

2. 当 $x=1, y=1$ 时：

   $m_{i, 1 \lor 1} = m_{i, 1} \cdot m_{i, 1} \implies m_{i, 1} = m_{i, 1}^2$

   解得 $m_{i, 1} = 0$ 或 $1$。

这意味着矩阵的每一行只能是 $[1, 0]$ 或 $[1, 1]$。为了让 $M_1$ 可逆（两行线性无关），我们取这两行作为矩阵的上下两行，得到： $$ M1 = \begin{bmatrix} 1 & 0 \ 1 & 1 \end{bmatrix} $$ 由于二进制的按位独立性，整体系数必定是各单比特系数的连乘积。在代数上，这等价于对 $M1$ 求 $n$ 次张量积： $$ Mn = M1 \otimes M1 \otimes \dots \otimes M1 $$ 利用张量积的结合律，我们提取出最高位（最左边的 $M_1$），把剩下的 $n-1$ 位记为 $M_{n-1}$： $$ Mn = M1 \otimes M{n-1} = \begin{bmatrix} 1 & 0 \ 1 & 1 \end{bmatrix} \otimes M{n-1} $$ 将 $M_{n-1}$ 作为一个整体乘进去，得到： $$ Mn = \begin{bmatrix} 1 \cdot M{n-1} & 0 \cdot M{n-1} \ 1 \cdot M{n-1} & 1 \cdot M{n-1} \end{bmatrix} = \begin{bmatrix} M{n-1} & 0 \ M{n-1} & M{n-1} \end{bmatrix} $$ 但是现在我们只能做到 $O(4^n)$ ，考虑怎么做到 $O(n2^n)$。

我们将长度为 $2^n$ 的原数组 $A$ 按最高位切成两半：$A = \begin{bmatrix} A0 \ A1 \end{bmatrix}$。

将其与拆开后的 $M_n$ 相乘： $$ F(A) = Mn \cdot A = \begin{bmatrix} M{n-1} & 0 \ M{n-1} & M{n-1} \end{bmatrix} \begin{bmatrix} A0 \ A1 \end{bmatrix} $$ 按矩阵乘法规则展开： $$ F(A) = \begin{bmatrix} M{n-1} \cdot A0 \ M{n-1} \cdot A0 + M{n-1} \cdot A1 \end{bmatrix} $$ 由于 $M_{n-1} \cdot A_0$ 本质上就是对子数组递归做变换，即 $F(A_0)$。代入替换后，我们就得到了最终的分治转移方程： $$ \begin{bmatrix} F(A0) \ F(A1) \end{bmatrix} = \begin{bmatrix} F(A0) \ F(A0) + F(A_1) \end{bmatrix} $$ 有主定理 ：$T(2^n) = 2 \times T(2^{n-1}) + O(2^n) = O(n2^n)$。

那我们怎么求逆呢。

张量积的逆等于逆的张量积。所以我们只需对 $M_1$ 求逆： $$ M_1^{-1} = \begin{bmatrix} 1 & 0 \ 1 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 \ -1 & 1 \end{bmatrix} $$

实现还是很简单的，递归写法：

非递归写法：

AND 卷积

对于与卷积，同理我们需要构造线性变换满足 $m_{i, x \cap y} = m_{i, x} \cdot m_{i, y}$ 。

可得满足该条件的矩阵 $M_1$ 为： $$ \begin{bmatrix} 1 & 1 \ 0 & 1 \end{bmatrix} $$ 读者自证不难。

然后有： $$ Mn = \begin{bmatrix} 1 & 1 \ 0 & 1 \end{bmatrix} \otimes M{n-1} = \begin{bmatrix} M{n-1} & M{n-1} \ 0 & M_{n-1} \end{bmatrix} $$

可得： $$ \begin{bmatrix} F(A0) \ F(A1) \end{bmatrix} = \begin{bmatrix} F(A0) + F(A1) \ F(A_1) \end{bmatrix} $$ 求逆与 OR 卷积同理：

对 $M_1$ 求逆： $$ M_1^{-1} = \begin{bmatrix} 1 & -1 \ 0 & 1 \end{bmatrix} $$

XOR 卷积

在张量积的帮助下，我们推导 XOR 卷积会自然很多。

约束：$m{i, x \oplus y} = m{i, x} \cdot m_{i, y}$。

1. 代入 $x=0, y=0$：

​ $m_{i, 0 \oplus 0} = m_{i, 0} \cdot m_{i, 0} \implies m_{i, 0} = m_{i, 0}^2$

​ 为了防全 $0$ 行，必须取 $m_{i, 0} = 1$。第一列全为 $1$。

2. 代入 $x=1, y=1$：

​ $m_{i, 1 \oplus 1} = m_{i, 1} \cdot m_{i, 1} \implies m_{i, 0} = m_{i, 1}^2$

​ 已知 $m_{i, 0} = 1$，所以 $1 = m_{i, 1}^2$，解得 $m_{i, 1} = 1$ 或 $-1$。

两行分别为 $[1, 1]$ 和 $[1, -1]$： $$ M1 = \begin{bmatrix} 1 & 1 \ 1 & -1 \end{bmatrix} $$ 有： $$ Mn = \begin{bmatrix} 1 & 1 \ 1 & -1 \end{bmatrix} \otimes M{n-1} = \begin{bmatrix} M{n-1} & M{n-1} \ M{n-1} & -M_{n-1} \end{bmatrix} $$

对 $M_1$ 求逆： $$ M1^{-1} = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} \ \frac{1}{2} & -\frac{1}{2} \end{bmatrix} $$ 代入： $$ F^{-1}(A) = \begin{bmatrix} \frac{1}{2}M{n-1}^{-1} & \frac{1}{2}M{n-1}^{-1} \ \frac{1}{2}M{n-1}^{-1} & -\frac{1}{2}M{n-1}^{-1} \end{bmatrix} \begin{bmatrix} A0 \ A_1 \end{bmatrix} $$