JZTXT

FWT 的另一种理解

发布时间 2023-11-16 11:04:18作者: Reliauk

思路

若要 \(\oplus\) 卷积 \(a\) 和 \(b\)（此处 \(\oplus\) 可以是任意运算），我们希望存在一个线性变换 \(\mathscr F\)，满足：

\[c_k = \sum_{i\oplus j = k} a_ib_j \Longleftrightarrow \mathscr F(a) \cdot \mathscr F(b) = \mathscr F(c) \]

若求 \(\mathscr F(x)\) 和 \(\mathscr F^{-1}(x)\) 的时间复杂度为 \(\mathcal O(T)\)，则卷积可以以 \(\mathcal O(n + T)\) 的时间复杂度完成。

设 \(\mathscr F\) 的系数矩阵为 \(F\)，分析一下这个式子：

\[\begin{aligned} \mathscr F(a) \cdot \mathscr F(b) = \mathscr F(c) &\Longleftrightarrow \forall x, \mathscr F(a)_x \times \mathscr F(b)_x = \mathscr F(c)_x \\ &\Longleftrightarrow \forall x, (\sum_{i=0}^{n-1} F(i, x)a_i) (\sum_{i=0}^{n-1} F(i, x)b_i) = \sum_{i=0}^{n-1} F(i, x)c_i\\ &\Longleftrightarrow \forall x, \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}F(i, x)F(j, x)a_ib_j = \sum_{i=0}^{n - 1}F(i, x)c_i\\ &\Longleftrightarrow \forall x, \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}F(i, x)F(j, x)a_ib_j = \sum_{i=0}^{n - 1}\sum_{j=0}^{n-1} F(i\oplus j, x)a_ib_j\\ \end{aligned} \]

所以，若上式对任意 \(a, b\) 及 \(c = a * b\) 都成立，则其等价于 \(F(i, x)F(j, x) = F(i \oplus j, x)\)。

\(\oplus = \&\)

令 \(F(i, j) = [i \text{ or } j = i]\)，显然有 \(F(i, x) F(j, x) = F(i\& j, x)\)。

此时 \(\mathscr F(x)\) 即为 \(x\) 的高维后缀和，从而 \(\mathscr F^{-1}(x)\) 就是高维后缀差分。

时间复杂度 \(\mathcal O(n 2^n)\)。

\(\oplus = \text{or}\)

令 \(F(i, j) = [i \text{ or }j = j]\)，显然有 \(F(i, x) F(j, x) = F(i\text{ or }j,x)\)。

此时 \(\mathscr F(x)\) 即为 \(x\) 的高维前缀和，从而 \(\mathscr F^{-1}(x)\) 就是高维前缀差分。

时间复杂度 \(\mathcal O(n 2^n)\)。

\(\oplus = \text{xor}\)

下面记 \(|x| = \text{popcount}(x)\)。

注意到有 \(|i| + |j| \equiv |i \text{ xor } j|\pmod 2\)，从而有 \((-1)^{|i|}(-1)^{|j|} = (-1)^{|i \text{ xor } j|}\)。

又因为 \((a \text{ xor } b) \& c = (a \& c)\text{ xor } (b\& c)\)，于是令 \(F(i, j) = (-1)^{|i \& j|}\)，显然 \(F(i, x)F(j, x) = F(i \text{ xor } j, x)\) 成立。

现在的问题在于如何快速求出 \(\mathscr F(x)\) 和 \(\mathscr F^{-1}(x)\)。

考虑分治求 \(x' = \mathscr F(x)\)，若要求 \(x'_0 \sim x'_{2^n - 1}\)，则对于 \(0 \leq k < 2^{n - 1}\)，有：

\[x'_k = \sum_{i=0}^{2^n - 1} x_i (-1)^{|i \& k|} = \sum_{i=0}^{2^{n -1 } - 1} x_i(-1)^{|i\&k|} + \sum_{i=0}^{2^{n -1 } - 1} x_{i + 2^{n -1 }}(-1)^{|i\&k|} = x0'_k + x1'_k \]

\[x'_{k + 2^{n - 1}} = \sum_{i=0}^{2^n - 1} x_i (-1)^{|i \& (k + 2^{n - 1})|} = \sum_{i=0}^{2^{n -1 } - 1} x_i(-1)^{|i\&k|} + \sum_{i=0}^{2^{n -1 } - 1} x_{i + 2^{n -1 }}(-1)^{|i\&k|+1} = x0'_k - x1'_k \]

其中 \(x0\) 表示分治求出的前一半的答案，\(x1\) 表示分治求出的后一半的答案。

类似 FFT，可以把这个过程变成非递归的，减小常数还好写。

至于求 \(\mathscr F^{-1}(x)\)，幸运地，我们有 \(F^{-1} = \dfrac 1n F\)，因此求出 \(\mathscr F(x)\) 再除以 \(2^n\) 就好了。

时间复杂度 \(\mathcal O(n 2^n)\)。