FWT - 快速沃尔什变换

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

$k$ $and, or$ 也是 FMT，然后又发现 FMT 我也不会，于是准备在挖个坑，以后有时间也补一下 FMT ...

这里额外说一下对于多项式约定俗成的几种运算表示什么~~相信你们一定都知道~~
$A$ $N$ $B$ $M$ 次。
$\max(N, M) = P$ 。
$\begin{aligned} (A, B) = (A (0), A (1), \dots, A (N), B (0), B (1), \dots, B (M)) 即拼接两个多项式 \\ A + B = (A (0) + B (0), A (1) + B (1), \dots, A (P) + B (P)) 即按位相加 \\ A - B = (A (0) - B (0), A (1) - B (1), \dots, A (P) - B (P)) 即按位相减 \\ A * B = (A (0) * B (0), A (1) * B (1), \dots, A (P) * B (P)) 即按位相乘，注意不是卷积 \\ A \times B = (\sum_{i + j = 0} A (i) \times B (j), \sum_{i + j = 1} A (i) \times B (j), \dots, \sum_{i + j = N + M} A (i) \times B (j)) 多项式卷积 \\ A \circ B = (\sum_{i \circ j = 0} A (i) \times B (j), \sum_{i \circ j = 1} A (i) \times B (j), \dots) 可以理解为广义上的卷积 \end{aligned}$

目的

FWT（快速沃尔什变换）一般用于处理形如如下式子的卷积：

C (x) = \sum_{i \circ j = x} A (i) \times B (j)

$\circ$ $and, or, xor$ 。

思路

与大多数多项式快速变换的思路一样，我们的目的都是找到一种变换，对于 FWT 可以考虑记作：

F W T (A)

我们需要让这个变换满足以下性质：

F W T (A) * F W T (B) = F W T (C)

且：

A \circ B = C

对于不同的运算都有着与之对应的不同的变换方式，我们的目的就是要找到一种优秀的变换并快速地进行变换。

或卷积

或卷积和与卷积应该算是 FWT 和 FMT 的交集了吧，我们这里为了方便理解亦或卷积所以也要讲一下或和与卷积。

显然式子如下：

C (x) = \sum_{i \lor j = x} A (i) \times B (j)

或者记作：

C = A | B

一些定义

这里我们定义 FWT 正变换为：

F W T (A) (i) = \sum_{j \subseteq i} A (j)

$(001101)_2 \subseteq (101101)_2$ 。

$A_0, A_1$ $A$ $A_0$ $2^{n - 1}$ $A_1$ $2^{n - 1}$ $n$ $2$ $0$ 开始）

一些性质与证明

显然有如下性质：

F W T (A + B) = F W T (A) + F W T (B)

证明也很简单，考虑将每一位分别考虑：

\begin{array}{r} F W T (A) (i) = \sum_{j \subseteq i} A (j) \\ F W T (B) (i) = \sum_{j \subseteq i} B (j) \end{array}

\begin{aligned} F W T (A + B) (i) & = \sum_{j \subseteq i} (A + B) (j) \\ = \sum_{j \subseteq i} A (j) + B (j) \\ = F W T (A) (i) + F W T (B) (i) \end{aligned}

显然我们可以得到如下的递归式子：

\begin{matrix} F W T (A) = {\begin{cases} A & (n = 0) \\ (F W T (A_{0}), F W T (A_{0}) + F W T (A_{1})) & o t h e r w i s e \end{cases} \end{matrix}

证明：

$2^n$ 。

$n = 0$ 时显然成立。

$A_0$ $A_1$ $A_0$ $[0, 2^{n - 1} - 1]$ $A_1$ $[2^{n - 1}, 2^n - 1]$ $A_0, A_1$ $n = 5$ 时：

\begin{array}{r} A_{0} : (00000)_{2}, (00001)_{2}, \dots, (01111)_{2} \\ A_{1} : (10000)_{2}, (10001)_{2}, \dots, (11111)_{2} \end{array}

$A_0$ $A_1$ $A_1$ $A_0$ 的子集。

$FWT(A_0) + FWT(A_1)$ $FWT(A)$ 的右半部分，左半部分同理，得证。

还有一个性质，即我们这个变换之后的式子是可以按位乘的。

F W T (A) * F W T (B) = F W T (C)

证明：

有一种感性理解的证明方法，仔细思考了一下感觉挺正确的，这里也写一下：

$FWT(A)(i)$ $i$ $FWT(B)(i)$ $i$ $C(i)$ $i$ $C(i)$ $i$ $C$ $FWT(C)(i)$ 。

严格证明：

\begin{aligned} F W T (C) (i) & = \sum_{j \subseteq i} C (j) \\ = \sum_{j \subseteq i} \sum_{x \lor y = j} A (x) \times B (y) \\ = \sum_{(x \lor y) \subseteq j} A (x) \times B (y) \\ = \sum_{x \subseteq i} A (x) \times \sum_{x \subseteq i} B (y) \\ = F W T (A) (i) * F W T (B) (i) \end{aligned}

而对于 FWT 的逆运算，即 IFWT，仅需要把加法变成减法即可，即：

\begin{matrix} I F W T (A) = {\begin{cases} A & (n = 0) \\ (I F W T (A_{0}), I F W T (A_{1}) - I F W T (A_{0})) & o t h e r w i s e \end{cases} \end{matrix}

$FWT$ 的性质推一下即可：

\begin{aligned} F W T (A)_{0} = F W T (A_{0}) \\ ⟹ & A_{0} = I F W T (F W T (A_{0})) = I F W T (F W T (A)_{0}) \end{aligned}

\begin{aligned} F W T (A)_{1} = F W T (A_{0}) + F W T (A_{1}) \\ ⟺ & F W T (A_{1}) = F W T (A)_{1} - F W T (A_{0}) \\ ⟹ & A_{1} = I F W T (F W T (A_{1})) = I F W T (F W T (A)_{1} - F W T (A)_{0}) \end{aligned}

Code


xxxxxxxxxx
1
1
//TODO

与卷积

和或卷积几乎一样，求的是：

C (x) = \sum_{i \land j = x} A (i) \times B (j)

定义：

F W T (A) (i) = \sum_{i \subseteq j} A (j)

有递归式子：

\begin{matrix} F W T (A) = {\begin{cases} A & (n = 0) \\ (F W T (A_{0}) + F W T (A_{1}), F W T (A_{1})) & o t h e r w i s e \end{cases} \end{matrix}

\begin{matrix} I F W T (A) = {\begin{cases} A & (n = 0) \\ (I F W T (A_{0}) - I F W T (A_{1}), I F W T (A_{1})) & o t h e r w i s e \end{cases} \end{matrix}

Code:


xxxxxxxxxx
1
1
//TODO

异或卷积

异或卷积才是真正的 FWT 内容。

Tips: 这里建议如果下面的内容不太理解可以直接翻到下面，从矩阵的角度去思考，我个人感觉多项式这里如果能把矩阵理解透了，从转移矩阵去考虑，才会发现多项式美妙在哪里，而且整个推导过程很合理直观！

$\oplus$ $\oplus_2$ )

C (x) = \sum_{i \oplus j = x} A (i) \times B (j)

一些“人类智慧”的定义

$c_i$ $i$ $1$ $c_5 = c_{(101)_2} = 2$ 。

~~然后下面这个定义特别离谱~~

对于异或运算，由前人的智慧我们可知有如下的 FWT 变换：

F W T (A) (i) = \sum_{j = 0}^{2^{n} - 1} (- 1)^{c_{i \land j}} A (j)

或记作：

F W T (A) (i) = (\sum_{c_{i \land j} mod 2 = 0} A (j)) - (\sum_{c_{i \land k} mod 2 = 1} A (k))

看着就很离谱而且和异或没有关系，这个东西也确实很离谱，后面会进行证明。

此时我们考虑，为了更快速地算出结果，

并且有如下递归公式：

\begin{matrix} F W T (A) = {\begin{cases} A & (n = 0) \\ (F W T (A_{0}) + F W T (A_{1}), F W T (A_{0}) - F W T (A_{1})) & o t h e r w i s e \end{cases} \end{matrix}

这个看起来也很奇怪，如果实在不明白为什么会有这种思路也可以考再去看看与和或的卷积看完，难度上要比异或好理解。

一些离谱的证明

对于递推公式的证明：

$n = 0$ 的情况很显然，就不证明了。

$FWT(A)_0$ $0$ $FWT(A_0)$ $0$ $FWT(A_1)$ $1$ ，所以直接相加。

$FWT(A)_1$ $FWT(A_1)$ $c_{i \land j}$ $1$ $-1$ $FWT(A)_0$ 显然不会受到影响。

对于这个运算可以按位乘的证明，我认为比较离谱，如果从矩阵的角度考虑更好理解一些，所以标准的方法这里就咕掉了，具体的证明会在后文提到。

然后逆运算大概这样，和之前与和或的区别不大，同理证明。

\begin{matrix} I F W T (A) = {\begin{cases} A & (n = 0) \\ (\frac{I F W T (A_{0}) + I F W T (A_{1})}{2}, \frac{I F W T (A_{0}) - I F W T (A_{1})}{2}) & o t h e r w i s e \end{cases} \end{matrix}

Code


xxxxxxxxxx
1
1
//TODO

$k$ 进制与卷积和或卷积

这个网上似乎没有说的，有的也只是一句话，我感性理解了一下，似乎和二进制的差不多？把包含的定义感性理解为每一位都小于，应该就可以解决了吧（这个不保证正确性，也没找到合适的例题）

upd - 然后再某篇文章里看到了这样一句话，验证了猜想的正确性。

$k$ 进制下，FMT 仍然能解决或卷积以及和卷积，因此 FWT 一般用来解决异或卷积。

$k$ 进制异或卷积

$k$ $k$ $\bmod{k}$ $k$ 进制加法）
$k$ $k$ $\bmod{k}$ $k$ 进制乘法)
$k$ $\min$ $\max$ 。
$k$ $P(i)$ $\bmod{2}$ 。

单位根？

$-1$ $k$ $-1$ $k$ $\omega^0, \omega^1, \omega^2, \cdots, \omega^{k - 1}$ $\omega^i = \omega^{i \bmod{k}}$ 。

然而这里我们发现对于这个东西，似乎很难理解，这里我们全部重头再来，从矩阵的角度再次思考。

再看目的与思路

$T$ ，有如下式子：

F W T (A) = T A

$T$ 使其符合以下运算：

T A * T B = T C

再看二进制异或卷积

与卷积和或卷积比较好理解就不说了，我们直接考虑异或卷积。

$T$ $(i, j)$ $\omega(i, j)$ $2^n$ ，则显然我们可以得到如下式子：

F W T (A) (x) = \sum_{i = 0}^{2^{n} - 1} ω (x, i) \times A (i)

将我们的目标式子进行如下转化：

\begin{aligned} F W T (A) * F W T (B) = F W T (C) \\ ⟺ & F W T (A) (x) * F W T (B) (x) = F W T (C) (x) \\ ⟺ & \sum_{i = 0}^{2^{n} - 1} ω (x, i) \times A (i) \times \sum_{j = 0}^{2^{n} - 1} ω (x, j) \times B (j) = \sum_{k = 0}^{2^{n} - 1} ω (x, k) \times C (k) \end{aligned}

$i \oplus j = k$ 的值，或者写成：

\sum_{i \oplus j = k} A (i) \times B (j) \times ω (x, i) \times ω (x, j) = C (k) \times ω (x, k)

观察这个式子不难看出我们要构造的矩阵需要满足：

ω (x, i) \times ω (x, j) = ω (x, k) (i \oplus j = k)

这样式子就能转化为：

\sum_{i \oplus j = k} A (i) \times B (j) = C (k)

于是发现，我们想要的最终式子出现了！

然后我们考虑如何快速求，显然与之前的思路类似，进行递归。

$\omega$ 满足异或的性质，那么显然它一定满足可以按位拆分的性质，证明比较显然，通过这个性质应该就可以理解了：

i \oplus 0 = i

显然按位拆分后，异或起来值不变，所以我们可以将按位拆分的式子更严谨地写成如下：

ω (i, j) = \prod_{k = 0}^{\dots} ω (i \land 2^{k}, j \land 2^{k})

进行如下定义：

$A_0, A_1$ $A$ $A_0$ $2^{n - 1}$ $A_1$ $2^{n - 1}$ $0$ 开始）。

$x$ $x_1$ $x_0$ 。

考虑进行如下推导：

$2^n - 1$ $2^n$ 的形式，与 FFT 类似。

\begin{aligned} F W T (A) (x) & = \sum_{i = 0}^{2^{n} - 1} ω (x, i) \times A (i) \\ = \sum_{i = 0}^{2^{n - 1} - 1} ω (x, i) \times A (i) + \sum_{i = 2^{n - 1}}^{2^{n} - 1} ω (x, i) \times A (i) \\ = \sum_{i = 0}^{2^{n - 1} - 1} ω (x_{1}, 0) \times ω (x_{0}, i_{0}) \times A (i) + \sum_{i = 2^{n - 1}}^{2^{n} - 1} ω (x_{1}, 1) \times ω (x_{0}, i_{0}) \times A (i) \\ = ω (x_{1}, 0) \times F W T (A_{0}) (x_{0}) + ω (x_{1}, 1) \times F W T (A_{1}) (x_{0}) \end{aligned}

解释一下最后两步变换。

$0$ $1$ $i$ $0$ $1$ $1$ $0$ ，于是即可分解成第三步的两个式子。

对于第四步，简单观察即可发现很显然，于是我们便可以将其进行递归，可以通过主定理计算复杂度：

T (n) = 2 T (\frac{n}{2}) + O (n) = O (n \log n)

$T$ 。

$2 \times 2$ 的矩阵，又由于我们需要进行 IFWT，所以矩阵需要有逆。

即：

[\begin{matrix} ω (0, 0) & ω (0, 1) \\ ω (1, 0) & ω (1, 1) \end{matrix}]

其需要满足以下性质：

\begin{array}{r} ω (0, 0) \times ω (0, 0) = ω (0, 0) \\ ω (0, 1) \times ω (0, 0) = ω (0, 1) \\ ω (0, 0) \times ω (0, 1) = ω (0, 1) \\ ω (0, 1) \times ω (0, 1) = ω (0, 0) \\ ω (1, 0) \times ω (1, 0) = ω (1, 0) \\ ω (1, 1) \times ω (1, 0) = ω (1, 1) \\ ω (1, 0) \times ω (1, 1) = ω (1, 1) \\ ω (1, 1) \times ω (1, 1) = ω (1, 0) \end{array}

$2$ 。

于是可以考虑到如下矩阵：

[\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}] = {[\begin{matrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & - \frac{1}{2} \end{matrix}]}^{- 1}

矩阵求逆的方法这里不再赘述，到此我们就解决了 FWT 二进制异或卷积。


xxxxxxxxxx
1
1
//TODO

$k$ 进制

$k$ 进制与二进制的思路差距很小，无非就是一些细节的改变，理解了矩阵之后便豁然开朗。

我们同样目的是构造：

T A * T B = T C

$k^n$ 的形式。

$\omega$ $k$ $k$ 进制下拆分最高位，这里有一些细节需要注意：

$x$ $k$ $x_1$ $x_0$ 。

$A$ $k$ $A_0, A_1, A_2, \cdots, A_{k - 1}$ 。

于是和之前思路一样，有：

\begin{aligned} F W T (A) (x) & = \sum_{i = 0}^{k^{n} - 1} ω (x, i) \times A (i) \\ = \sum_{t = 0}^{k - 1} ω (x_{1}, t) \sum_{i_{1} = t} ω (x_{0}, i_{0}) \times A (i) \\ = \sum_{t = 0}^{k - 1} ω (x_{1}, t) \times F W T (A_{t}) (x_{0}) \end{aligned}

通过主定理计算时间复杂度：

T (n) = k T (\frac{n}{k}) + O (k n) = O (n k \log_{k}^{n})

$\omega$ 需要符合的性质：

ω (x, i) \times ω (x, j) = ω (x, m) (i \oplus_{k} j = m)

或写成：

ω (x, i) \times ω (x, j) = ω (x, m) (k | i + j - m)

$k \times k$ 矩阵：

[\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ 1 & ω_{k}^{1} & ω_{k}^{2} & \dots & ω_{k}^{k - 1} \\ 1 & ω_{k}^{2} & ω_{k}^{4} & \dots & ω_{k}^{2 (k - 1)} \\ \dots & \dots & \dots & \dots & \dots \\ 1 & ω_{k}^{k - 1} & ω^{2 (k - 1)} & \dots & ω_{k}^{(k - 1) (k - 1)} \end{matrix}]

观察发现这个矩阵显然符合我们的要求，且我们在 FFT 的时候就用过这个矩阵，且其存在逆矩阵，为：

\begin{matrix} \frac{1}{k} [\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ 1 & ω_{k}^{- 1} & ω_{k}^{- 2} & \dots & ω_{k}^{- (k - 1)} \\ 1 & ω_{k}^{- 2} & ω_{k}^{- 4} & \dots & ω_{k}^{- 2 (k - 1)} \\ \dots & \dots & \dots & \dots & \dots \\ 1 & ω_{k}^{- (k - 1)} & ω^{- 2 (k - 1)} & \dots & ω_{k}^{- (k - 1) (k - 1)} \end{matrix}] \end{matrix}

然后这个矩阵似乎叫范德蒙德矩阵~~（不会）~~

$k$ 进制 FWT 的推导。

Code


xxxxxxxxxx
1
1
//TODO

Luogu 模板题

P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

Code


xxxxxxxxxx
1
1
//TODO

$k$ 进制 FWT 题

【清华集训2016】石家庄的工人阶级队伍比较坚强

LG-P7930 [COCI2021-2022#1] Set

~~嗯这道题就是梦开始的地方~~

写在后面

关于 FWT 仍然有很多扩展，比如在模意义下考虑单位根不存在，然后进行扩域等一系列看不懂的操作，比如这个链接。

$k$ 很大的时候，如这个链接。

只能说学无止境吧，以后有时间再去研究研究。

UPD

update-2022_09_01 与和或完成

update-2022_09_02 初稿

FWT - 快速沃尔什变换

更好的阅读体验戳此进入

目的

思路

或卷积

一些定义

一些性质与证明

Code

与卷积

Code:

异或卷积

一些“人类智慧”的定义

一些离谱的证明

Code

k k 进制与卷积和或卷积

k k 进制异或卷积

单位根？

再看目的与思路

再看二进制异或卷积

回到 k k 进制

Code

Luogu 模板题

Code

k k 进制 FWT 题

【清华集训2016】石家庄的工人阶级队伍比较坚强

LG-P7930 [COCI2021-2022#1] Set

写在后面

UPD

$k$ 进制与卷积和或卷积

$k$ 进制异或卷积

$k$ 进制

$k$ 进制 FWT 题