FWT

标签：... begin end sum FWT mathcal align

前言

FWT 一般被用来快速求类似

\[\begin{align*} C_k=\sum_{i\star j=k}A_i\cdot B_j \end{align*} \]

的卷积，其中 \(\star\) 一般是按位与，按位或和按位异或，下文我们先以二进制按位异或为例，将异或卷积直接记为 \(C=A\oplus B\)。

高维卷积

事实上，我们可以把 FWT 看作是高维的卷积：由于是按位运算，我们不妨也按位拆开下标，设下标有 \(K\) 位，记 \(a_n=a(x_1,x_2,\cdots,x_K),x_i\in\{0,1\}\)， 其中 \(x_i\) 是 \(n\) 的第 \(i\) 位二进制位，则卷积

\[\begin{align*} C_k=\sum_{i\oplus j=k}A_i\cdot B_j \end{align*} \]

可以记作

\[\begin{align*} A(x_1,x_2,\cdots,x_K)\cdot B(y_1,y_2,\cdots,y_K)\rightarrow C(x_1+y_1\operatorname{mod} 2,x_2+y_2\operatorname{mod}2,\cdots,x_K+y_K\operatorname{mod}2) \end{align*} \]

不难发现，这是对每一维进行循环卷积。

FWT

对于一维的情况，我们只需要对两个个序列进行一次循环卷积，此时我们可以对两个序列分别做 DFT，然后将两个序列对应位置相乘，再进行一次 IDFT，就能得到卷积后的序列。即 \(C=A* B\Leftrightarrow \mathcal{F}(C)=\mathcal{F}(A)\cdot\mathcal{F}(B)\)，其中 \(*\) 是循环卷积，\(\cdot\) 是对应位置直接相乘。

那么我们能不能将其推广到高维呢？具体的，我们想要找到一个变换 \(\mathcal{F}_K\)，使得对于序列 \(A,B,C\) 满足 \(C=A\oplus B\)，我们有 \(\mathcal{F}_K(C)=\mathcal{F}_K(A)\cdot\mathcal{F}_K(B)\)。并且 \(\mathcal{F}_K\) 应当有逆变换 \(\mathcal{F}_K^{-1}\)（不然你算个头）。

我们考虑从 \(1\) 到 \(K\) 逐次构造变换 \(\mathcal{F}_K\)，假如我们已经得到了变换 \(\mathcal{F}_{K-1}\)，对于数列 \(A(x_1, x_2, ..., x_K),B(y_1, y_2, ..., y_K),C(z_1, z_2, ..., z_K)\) 满足 \(C=A\oplus B\)，我们先固定第 \(K\) 维，对前 \(K-1\) 个维度做变换 \(\mathcal{F}_{K-1}\)：

\[\begin{align*} & A'(x_1,x_2,...,x_{K-1},0) = \mathcal{F}_{K-1}(A(x_1,x_2,...,x_{K-1},0)) \\ & A'(x_1,x_2,...,x_{K-1},1) = \mathcal{F}_{K-1}(A(x_1,x_2,...,x_{K-1},1)) \\ & B'(x_1,x_2,...,x_{K-1},0) = \mathcal{F}_{K-1}(B(x_1,x_2,...,x_{K-1},0)) \\ & B'(x_1,x_2,...,x_{K-1},1) = \mathcal{F}_{K-1}(B(x_1,x_2,...,x_{K-1},1)) \\ & C'(x_1,x_2,...,x_{K-1},0) = \mathcal{F}_{K-1}(C(x_1,x_2,...,x_{K-1},0)) \\ & C'(x_1,x_2,...,x_{K-1},1) = \mathcal{F}_{K-1}(C(x_1,x_2,...,x_{K-1},1)) \\ \end{align*} \]

其中 \(x_1,x_2,...,x_{K-1}\) 是变量。

简单尝试一下，不难发现，如果我们枚举 \(n_1,n_2,...,n_{K-1}\)，简记

\[\begin{align*} & \hat{A}(0)=A'(n_1,n_2,...,n_{K-1},0) \\ & ... \end{align*} \]

那么有

\[\begin{align*} \hat{A}(i)\cdot \hat{B}(j) & =\mathcal{F}_{K-1}(\sum_{\substack{x_k+y_k\equiv n_k(\operatorname{mod}2) \\k\in[1,K-1]}}A(x_1,x_2,...,x_{K-1},i)\cdot B(y_1,y_2,...,y_{K-1},j)) \end{align*} \]

而

\[\begin{align*} \hat{C}(k) & =\mathcal{F}_{K-1}({\sum_{i+j\equiv k(\operatorname{mod}2)}\sum_{\substack{x_k+y_k\equiv n_k(\operatorname{mod}2) \\k\in[1,K-1]}}A(x_1,x_2,...,x_{K-1},i)\cdot B(y_1,y_2,...,y_{K-1},j)}) \end{align*} \]

也就是说，在 \(\mathcal{F}_{K-1}\) 的里面，\(\hat{C}\) 和 \(\hat{A},\hat{B}\) 构成了一个循环卷积。
注意到在 DFT 中，两个数列的和的 DFT 是等于两个数列的 DFT 的和，即

\[\begin{align*} \mathcal{F}(A+B) & =\mathcal{F}(A)+\mathcal{F}(B) \end{align*} \]

其中 \(+\) 代表数列的对应位置相加。

那么我们不妨猜想其高维推广也具有这样的性质，则有

\[\begin{align*} C(k) & =\mathcal{F}_{K-1}({\sum_{i+j\equiv k(\operatorname{mod}2)}\sum_{\substack{x_k+y_k\equiv n_k(\operatorname{mod}2) \\k\in[1,K-1]}}a(x_1,x_2,...,x_{K-1},i)\cdot b(y_1,y_2,...,y_{K-1},j)})\\ & =\sum_{i+j\equiv k(\operatorname{mod}2)}\mathcal{F}_{K-1}({\sum_{\substack{x_k+y_k\equiv n_k(\operatorname{mod}2) \\k\in[1,K-1]}}a(x_1,x_2,...,x_{K-1},i)\cdot b(y_1,y_2,...,y_{K-1},j)})\\ & =\sum_{i+j\equiv k(\operatorname{mod}2)}A(i)\cdot B(j) \end{align*} \]

注意这里我们将 \(A(x_1,x_2,...,x_K-1,i)\) 看作 \(K-1\) 维的数列，因为 \(i\) 实际上是常量而不是下标。
也就是说 \(\hat{C}\) 的确是 \(\hat{A},\hat{B}\) 的循环卷积，那么对于序列 \(A,B\)，我们分别做一次 DFT，就能得到 \(\mathcal{F}_{K}\)。
总结一下，对 \(A(x_1,x_2,...,x_K)\) 进行 \(\mathcal{F}_{K}\) 时，我们先枚举 \(x_K\)，对 \(A(x_1,x_2,...,x_{K-1},0/1)\) 递归计算 \(\mathcal{F}_{K-1}\)，然后枚举 \(x_1,x_2,...,x_{K-1}\)，计算 \(\left\{A(x_1,x_2,...,x_{K-1},0),A(x_1,x_2,...,x_{K-1},1)\right\}\) 的 DFT。形式化的说，

\[\begin{align*} & \mathcal{F}_{K}(A(x_1,x_2,...,x_K))=\mathcal{F}(\left\{\mathcal{F}_{K-1}(A(x_1,x_2,...,x_{K-1},0)),\mathcal{F}_{K-1}(A(x_1,x_2,...,x_{K-1},1))\right\}) \\ & \mathcal{F}_{1}=\mathcal{F}\ \text{为离散傅里叶变换} \end{align*} \]

于是我们递归定义了高维的 DFT，成功得到了变换 \(\mathcal{F}_{K}\)，这允许我们快速地计算异或卷积。
上文的可加性也能简单地通过归纳法证明，此处不再赘述。

FMT

由上文将 DFT 推广至高维的过程，我们发现它其实和 DFT 并没有关系，以“或”卷积为例：
我们尝试构造一个类似 DFT 的矩阵 \(M\)，对于数列 \(A,B,C\) 满足 \(C=A\operatorname{or} B\)，有

\[\begin{gather*} MC=MA\cdot MB \end{gather*} \]

（我们把 \(A,B,C\) 看作向量，\(\cdot\) 是向量的对应分量相乘）
展开，有

\[\begin{gather*} \sum_im_{n,i}c_i=\sum_im_{n,i}a_i\cdot\sum_im_{n,i}b_i\\ \sum_i m_{n,i}\sum_j\sum_ka_jb_k[j\operatorname{or} k=i]=\sum_im_{n,i}a_i\cdot\sum_im_{n,i}b_i\\ \sum_j\sum_ka_jb_km_{n,j\operatorname{or} k}=\sum_i\sum_ja_ib_jm_{n,i}m_{n,j} \end{gather*} \]

即

\[\begin{gather*} \sum_i\sum_jm_{n,i\operatorname{or} j}(a_ib_j)=\sum_i\sum_jm_{n,i}m_{n,j}(a_ib_j) \end{gather*} \]

对比等式两端系数，有

\[\begin{gather*} m_{n,i}m_{n,j}=m_{n,i\operatorname{or} j} \end{gather*} \]

构造一个满足条件且可逆的矩阵即可，例如

\[\begin{gather*} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \end{gather*} \]

而运算 \(\operatorname{and}\) 对应的矩阵为

\[\begin{align*} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \end{align*} \]

考虑计算过程，这实际上就是高维的前/后缀和.

K进制异或(不进位加法)

事实上，和二进制异或是一样的，以三进制为例，把 DFT 矩阵换成 \(3\times3\) 的

\[\begin{gather*} \begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega^4 \\ \end{pmatrix} \end{gather*} \]

其中 \(\omega\) 为三次单位根。

逆变换

这是个线性算法，反着走一遍算法流程就是逆运算了（

复杂度分析

显然，\(n\) 维每维 \([0,d)\) 的朴素实现时间复杂度是 \(O(nd^n\cdot d^2)\)，FWT 利用 FFT 优化可以达到 \(O(nd^n\cdot d\log d)\)，FMT 则直接使用前/后缀和优化到 \(O(nd^n\cdot d\log d)\)。

标签：...,begin,end,sum,FWT,mathcal,align
From： https://www.cnblogs.com/watware-cym/p/17178601.html