P4717
【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)
我决定直接记掉代码加结论走人。
这个东西是计算：
$$h_i=\sum_{j\oplus k=i}f_j\times g_k$$
这种卷积的。
其中 $\oplus$ 为某种位运算。
我们仍然希望能像 DFT 和 IDFT 那样，将这个位运算的卷积换成点积。并且这个变换是线性的。
所以我们不妨设数列 $\mathbf{f}$ 的 DWT 满足：
$$\hat{f_i}=\sum_{j=0}^{n-1}c(i,j)f_j$$
（仿照 DFT 的定义）称 $\mathbf{\hat{f}}$ 为 $\mathbf{f}$ 的 DWT。
我们不像 DFT 有单位根那样，这个 $c(i,j)$ 我们并不知道。
好像会有 $\hat{f_i}\cdot \hat{g_i}=\hat{h_i}$。
至于 DWT 这个过程如何分治。
我很难解释这个过程。因为这个东西本来就比较直觉且抽象，想给出一个比较数学的证明还挺那啥的。。。
技不如人，给出结论。。。
$$\hat{f_{0x}}=c(0,0)\hat{f_{0x}}+c(0,1)\hat{f_{1x}}$$
$$\hat{f_{1x}}=c(1,0)\hat{f_{0x}}+c(1,1)\hat{f_{1x}}$$
这里 $x$ 是一个二进制数，$0x$ 表示把 $0$ 接在 $x$ 前面组成二进制数，$1x$ 同理。
最后 $c$ 的构造有不同的矩阵。IDWT 就是对 DWT 的矩阵求个逆。
1. $\operatorname{Or}$ 卷积
矩阵是这个：
$$\begin{bmatrix}1 & 0 \\ 1 & 1\end{bmatrix}$$
它的逆是这个：
$$\begin{bmatrix}1 & 0 \\ -1 & 1\end{bmatrix}$$
2. $\operatorname{And}$ 卷积
矩阵是这个：
$$\begin{bmatrix}1 & 1 \\ 0 & 1\end{bmatrix}$$
它的逆是这个：
$$\begin{bmatrix}1 & -1 \\ 0 & 1\end{bmatrix}$$
3. $\operatorname{Xor}$ 卷积
矩阵是这个：
$$\begin{bmatrix}1 & 1 \\ 1 & -1\end{bmatrix}$$
它的逆是这个：
$$\begin{bmatrix}\dfrac{1}{2} & \dfrac{1}{2} \\ \dfrac{1}{2} & -\dfrac{1}{2}\end{bmatrix}$$
然后 $2$ 在 $\pmod{998244353}$ 下的逆元是 $499122177$。其他情况的逆元可以自己两分钟左右写个快速幂算出来。
时间复杂度 $O(n2^n)$。
代码：
1 |
|