专栏文章

浅谈 FWT

ZZnPdCo
P4717题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqohise
此快照首次捕获于
2025/12/04 08:09
3 个月前
此快照最后确认于
2025/12/04 08:09
3 个月前
查看原文
我们先速通一下前面的部分：

按位或

A=merge(A0,A0+A1)A=\text{merge}(A_0, A_0+A_1) a=merge(a0,a1−a0)a=\text{merge}(a_0, a_1-a_0)

按位与

A=merge(A0+A1,A1)A=\text{merge}(A_0+A_1, A_1) a=merge(a0−a1,a1)a=\text{merge}(a_0 - a_1, a_1)

按位异或

A=merge(A0+A1,A0−A1)A=\text{merge}(A_0+A_1, A_0-A_1) a=merge(a0+a12,a0−a12)a=\text{merge}(\frac{a_0+a_1}{2}, \frac{a_0-a_1}{2})
我们设 c(i,j)c(i,j) 是 aja_j 对 AiA_i 的贡献系数。我们可以重新描述 FWT 变换的过程：
Ai=∑j=0n−1c(i,j)ajA_i = \sum_{j=0}^{n-1} c(i,j) a_j
因为有：
AiBi=CiA_iB_i=C_i
所以我们可以通过简单的证明得到：c(i,j)c(i,k)=c(i,j⊙k)c(i,j)c(i,k)=c(i,j\odot k)。其中 ⊙\odot 是任意一种位运算。
同时，cc 函数还有一个重要的性质，它可以按位处理。
举个例子，我们变换的时候：
Ai=∑j=0n−1c(i,j)ajA_i = \sum_{j=0}^{n-1} c(i,j) a_j
这么做是比较劣的，我们将其拆分：
Ai=∑j=0(n−1)/2c(i,j)aj+∑j=(n−1)/2+1n−1c(i,j)ajA_i = \sum_{j=0}^{(n-1)/2} c(i,j) a_j+\sum_{j=(n-1)/2+1}^{n-1} c(i,j) a_j
考虑前面的式子和后面的式子 i,ji,j 的区别，发现只有最高位不同。
所以我们将 i,ji,j 去除最高位的值为 i′,j′i',j'，并记 i0i_0 为 ii 的最高位。有：
Ai=c(i0,0)∑j=0(n−1)/2c(i′,j′)aj+c(i0,1)∑j=(n−1)/2+1n−1c(i′,j′)ajA_i = c(i_0,0)\sum_{j=0}^{(n-1)/2} c(i',j') a_j+c(i_0,1)\sum_{j=(n-1)/2+1}^{n-1} c(i',j') a_j
如果 i0=0i_0=0，则有：
Ai=c(0,0)∑j=0(n−1)/2c(i′,j′)aj+c(0,1)∑j=(n−1)/2+1n−1c(i′,j′)ajA_i = c(0,0)\sum_{j=0}^{(n-1)/2} c(i',j') a_j+c(0,1)\sum_{j=(n-1)/2+1}^{n-1} c(i',j') a_j
i0=1i_0=1 则有：
Ai=c(1,0)∑j=0(n−1)/2c(i′,j′)aj+c(1,1)∑j=(n−1)/2+1n−1c(i′,j′)ajA_i = c(1,0)\sum_{j=0}^{(n-1)/2} c(i',j') a_j+c(1,1)\sum_{j=(n-1)/2+1}^{n-1} c(i',j') a_j
也就是说，我们只需要：
[c(0,0)c(0,1)c(1,0)c(1,1)]\begin{bmatrix} c(0,0) & c(0,1) \\ c(1,0) & c(1,1) \end{bmatrix}
四个数就可以完成变换了。我们称这个矩阵为位矩阵。
如果我们要进行逆变换，则需要上面的位矩阵的逆矩阵。
若逆矩阵为 c−1c^{-1}，可以通过类似操作得到原数：
ai=∑j=0nc−1(i,j)Aja_i = \sum_{j=0}^n c^{-1}(i,j) A_j
逆矩阵不一定存在，比如如果有一排 00 或者一列 00 那么这个矩阵就没有逆，我们在构造时需要格外小心。

按位或

我们可以构造：
[1011]\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}
这样满足 c(i,j)c(i,k)=c(i,j∪k)c(i,j)c(i,k)=c(i,j\cup k)。我们发现，这和我们前面推出的 A=merge(A0,A0+A1)A=\text{merge}(A_0, A_0+A_1) 一模一样！同理，下面也是一个满足这个条件的矩阵，但我们一般使用上面这个：
[1110]\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}
虽然下面这个矩阵也满足 c(i,j)c(i,k)=c(i,j∪k)c(i,j)c(i,k)=c(i,j\cup k)，但这个矩阵存在一排 00，不存在逆，所以不合法：
[0011]\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}
如果我们要进行逆变换，则需要对矩阵求逆，以最上面这个矩阵为例，得：
[10−11]\begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix}
然后按照顺变换的方法，把逆变换矩阵代入即可。

按位与

我们可以构造：
[1101]\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}
这样满足 c(i,j)c(i,k)=c(i,j∩k)c(i,j)c(i,k)=c(i,j\cap k)。
逆矩阵：
[1−101]\begin{bmatrix} 1 & -1 \\ 0 & 1 \end{bmatrix}

按位异或

我们可以构造：
[111−1]\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}
这样满足 c(i,j)c(i,k)=c(i,j⊕k)c(i,j)c(i,k)=c(i,j\oplus k)。
逆矩阵：
[0.50.50.5−0.5]\begin{bmatrix} 0.5 & 0.5 \\ 0.5 & -0.5 \end{bmatrix}

K 维 FWT

其实位运算的本质是对一个 nn 维 {0,1}\{0,1\} 向量的运算。或运算就是每一维取 max⁡\max。且运算就是每一维取 min⁡\min。异或运算则是每一维对应相加再  mod 2\bmod 2。
位运算有个特点：向量的每一位都是独立的。
我们把 {0,1}\{0,1\} 扩展到 [0,K)∩Z[0,K)\cap Z 也就是扩展到 KK 进制，看看会得到什么？

max 运算

我们将 ∪\cup 运算拓展到 KK 进制，定义 i∪ji\cup j 表示按位取 max⁡\max，有：
c(i,j)c(i,k)=c(i,j∪k)c(i,j)c(i,k)=c(i,j\cup k)
若 j=kj=k，那么上式又是：
c(i,j)c(i,j)=c(i,j)c(i,j)c(i,j)=c(i,j)
也就是说，每一行的 11 必定只能在 00 的前面，如果在后面则不合法了。手玩一下可以发现一组合法构造：
[1000110011101111]\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix}
求逆可得：
[1000−11000−11000−11]\begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix}

min 运算

我们将 ∩\cap 运算拓展到 KK 进制，定义 i∩ji\cap j 表示按位取 min⁡\min，有：
c(i,j)c(i,k)=c(i,j∩k)c(i,j)c(i,k)=c(i,j\cap k)
若 j=kj=k，那么上式又是：
c(i,j)c(i,j)=c(i,j)c(i,j)c(i,j)=c(i,j)
也就是说，每一行的 11 必定只能在 00 的后面，如果在前面则不合法了。手玩一下可以发现一组合法构造：
[1111011100110001]\begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix}
求逆可得：
[1−10001−10001−10001]\begin{bmatrix} 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 1 \end{bmatrix}
前两者用得比较少，用得比较多的是：

不进位加法

我们将 ⊕\oplus 运算拓展到 KK 进制，定义 i⊕ji\oplus j 表示按位相加再  mod K\bmod K，有：
c(i,j)c(i,k)=c(i,j⊕k)c(i,j)c(i,k)=c(i,j\oplus k)
我们构造 c(i,j)=ωKjc(i,j)=\omega_{K}^j，就可以满足要求了：
ωKjωkk=ωK(j+k) mod K\omega_{K}^j\omega_{k}^k=\omega_{K}^{(j+k)\bmod K}
但是每一行都一样矩阵也没有逆，所以我们可以构造 c(i,j)=ωK(i−1)jc(i,j)=\omega_{K}^{(i-1)j} 即可。
有下面这个矩阵：
[111⋯11ωK1ωK2⋯ωKk−11ωK2ωK4⋯ωK2(k−1)1ωK3ωK6⋯ωK3(k−1)⋮⋮⋮⋱⋮1ωKk−1ωK2(k−1)⋯ωK(k−1)(k−1)]\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_{K}^1 & \omega_{K}^2 & \cdots & \omega_{K}^{k-1} \\ 1 & \omega_{K}^2 & \omega_{K}^4 & \cdots & \omega_{K}^{2(k-1)} \\ 1 & \omega_{K}^3 & \omega_{K}^6 & \cdots & \omega_{K}^{3(k-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_{K}^{k-1} & \omega_{K}^{2(k-1)} & \cdots & \omega_{K}^{(k-1)(k-1)} \end{bmatrix}
此即为 范德蒙德矩阵，求逆可得：
1K[111⋯11ωK−1ωK−2⋯ωK−(k−1)1ωK−2ωK−4⋯ωK−2(k−1)1ωK−3ωK−6⋯ωK−3(k−1)⋮⋮⋮⋱⋮1ωK−(k−1)ωK−2(k−1)⋯ωK−(k−1)(k−1)]\frac{1}{K}\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega_{K}^{-1} & \omega_{K}^{-2} & \cdots & \omega_{K}^{-(k-1)} \\ 1 & \omega_{K}^{-2} & \omega_{K}^{-4} & \cdots & \omega_{K}^{-2(k-1)} \\ 1 & \omega_{K}^{-3} & \omega_{K}^{-6} & \cdots & \omega_{K}^{-3(k-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_{K}^{-(k-1)} & \omega_{K}^{-2(k-1)} & \cdots & \omega_{K}^{-(k-1)(k-1)} \end{bmatrix}
如果我们题目给出的模数是存在单位根的，我们就可以简单实现。
但是单位根在模意义下可能不存在，所以我们考虑扩域，就是人为地定义一个 xx，满足 xK=1x^K=1，然后直接把 xx 代入计算，这样每个数都是一个关于 xx 的 k−1k-1 次多项式。我们只需要在 (modxK−1)\pmod {x^K-1} 下计算即可。那么矩阵可以这么表示：
[111⋯11x1x2⋯xk−11x2x4⋯x2(k−1)1x3x6⋯x3(k−1)⋮⋮⋮⋱⋮1xk−1x2(k−1)⋯x(k−1)(k−1)]\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & x^1 & x^2 & \cdots & x^{k-1} \\ 1 & x^2 & x^4 & \cdots & x^{2(k-1)} \\ 1 & x^3 & x^6 & \cdots & x^{3(k-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x^{k-1} & x^{2(k-1)} & \cdots & x^{(k-1)(k-1)} \end{bmatrix}
但是这么做可能会存在零因子，也就是一个数有多种表示方法，我们无法确定一个数的真实值。
我们考虑不 (modxK−1)\pmod {x^K-1} 了，我们  mod \bmod 分圆多项式 ΦK(x)\Phi_{K}(x)，他满足 xx 的阶为 kk，且在 QQ 上不可约。所以我们定义上面的计算是在 (modΦK(x))\pmod {\Phi_{K}(x)} 下进行即可。
另一方面，如何求分圆多项式，这一点可以在因式分解这道题的题解区里了解。这里给出分圆多项式的表：
还有一个问题是， mod ΦK(x)\bmod \Phi_{K}(x) 常数大（因为 Φ\Phi 本身就是一个多项式）。但是因为 ΦK(x)∣xk−1\Phi_{K}(x)\mid x^k-1，我们只需要在计算时  mod xk−1\bmod x^k -1，最后再  mod ΦK(x)\bmod \Phi_{K}(x) 即可。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...