OI-wiki 快速沃尔什变换（FWT）完全指南：位运算卷积的原理、矩阵视角与 K 维推广

OI-wiki 快速沃尔什变换FWT完全指南位运算卷积的原理、矩阵视角与 K 维推广【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki快速沃尔什变换Fast Walsh TransformFWT是算法竞赛中用于在 $O(n\log n)$ 时间内求解下标按位运算卷积或卷积、与卷积、异或卷积的核心工具。本文以 OI-wiki 的 docs/math/poly/fwt.md 为主体完整推导或 / 与 / 异或 / 同或四种卷积的变换构造、分治求值与逆变换过程并从位矩阵与线性变换的角度揭示 FWT 的本质最后延伸到 K 进制下的 K 维 FWT 与例题实战。读完本文你将掌握 FWT 的完整推导脉络、可直接套用的迭代代码以及处理模意义下无单位根情形的扩域技巧。背景为什么需要沃尔什变换沃尔什变换Walsh Transform最初是在频谱分析中作为离散傅立叶变换DFT的替代方案提出的在信号处理领域应用广泛。它与 FFT 的关键区别在于FFT 将信号拆解到不同频率的正弦 / 余弦波上系数是浮点数必须做浮点乘法且存在精度误差而沃尔什变换把信号拆解到不同震荡频率的方波上因此所有变换系数都是绝对值大小相同的整数不需要浮点运算速度更快。在算法竞赛语境下FWT 的意义被重新定位为对下标进行位运算卷积的快速算法。它解决的问题是$$ C_{i} \sum_{ij \oplus k}A_{j} B_{k} $$其中 $\oplus$ 是二元位运算中的某一种按位或、按位与、按位异或等。核心思想与 FFT 同构的三段式流程FWT 与 FFT 的核心思想完全相同——都是对数组做某种变换把难以快速计算的卷积变成逐点相乘。记对数组 $A$ 进行快速沃尔什变换后的结果为 $FWT[A]$求解 $CA\cdot B$ 的标准流程是正向变换得到 $FWT[A]$ 与 $FWT[B]$点值相乘根据 $FWT[C]FWT[A]\cdot FWT[B]$在 $O(n)$ 的时间内求出 $FWT[C]$其中 $\cdot$ 是序列对应位置相乘逆向变换对 $FWT[C]$ 做逆变换还原出原序列 $C$。总时间复杂度为 $O(n\log n)$。下面我们以 $\cup$按位或、$\cap$按位与和 $\oplus$按位异或三种运算为例逐一推导。或卷积构造、分治与逆变换变换的构造与正确性若 $ki\cup j$那么 $i$ 中为 $1$ 的二进制位和 $j$ 中为 $1$ 的二进制位必然是 $k$ 中为 $1$ 的二进制位的子集。为了得到 $FWT[C]FWT[A]\cdot FWT[B]$我们按定义构造$$ FWT[A]i Ai \sum{ii\cup j}A{j} $$即 $j$ 满足二进制中 $1$ 的位置是 $i$ 的子集。可以验证该构造满足卷积定理$$ \begin{aligned} FWT[A]i\cdot FWT[B]i\left(\sum{i\cup ji} A_j\right)\left(\sum{i\cup ki} B_k\right) \ \sum_{i\cup ji}\sum_{i\cup ki}A_jB_k \ \sum_{i\cup(j\cup k)i}A_jB_k \ FWT[C]_i \end{aligned} $$分治求值从 $O(n^2)$ 到 $O(n\log n)$直接按定义枚举是 $O(n^2)$ 的无法接受于是考虑分治。把整个区间二分后下标写成二进制形式会呈现规律令 $A_0$ 表示 $A$ 的前一半$A_1$ 表示后一半$A_0$ 中下标的最高位为 $0$其子集就是它本身的子集最高位恒为 $0$不会跨到 $A_1$ 去因此 $FWT[A_0]$ 可独立递归计算$A_1$ 中下标的最高位为 $1$它满足条件的子集不仅包含自身还包含所有最高位为 $0$ 的子集即需要加上 $FWT[A_0]$。于是得到或卷积的递推式merge 表示把两个数组像字符串拼接一样接起来$$ 为普通加法、对应位相加$$ FWT[A] merge(FWT[A_0],; FWT[A_0] FWT[A_1]) $$这样二分拼接每次只需 $O(n)$ 次加法共 $O(\log n)$ 层总复杂度 $O(n\log n)$。逆变换反演反演非常简单已知 $A_0FWT[A_0]$自身的子集就是自己而 $A_1$ 的变换结果是 $FWT[A_0]FWT[A_1]$把加上的部分减回去即可$$ UFWT[A] merge(UFWT[A_0],; UFWT[A_1] - UFWT[A_0]) $$容易发现顺变换与逆变换可以合并为同一个函数顺变换时 $\text{type}1$逆变换时 $\text{type}-1$。OI-wiki 给出了常数更小的迭代实现void Or(ll *a, ll type) { // 迭代实现常数更小 for (ll x 2; x n; x 1) { ll k x 1; for (ll i 0; i n; i x) { for (ll j 0; j k; j) { (a[i j k] a[i j] * type) % P; } } } }其中 $n$ 为数组长度通常补齐为 $2$ 的幂$P$ 为模数数组下标均从 $0$ 开始。外层循环枚举块长 $x$内层对每个长度为 $x$ 的块把左半部分对应 $FWT[A_0]$叠加到右半部分对应 $FWT[A_0]FWT[A_1]$上逆变换时type -1即完成减法。与卷积与运算可以完全类比或运算得到。由于 $ki\cap j$ 时$i,j$ 中为 $1$ 的位置是 $k$ 中为 $1$ 的位置的超集变换构造方向与或卷积相反$$ FWT[A] merge(FWT[A_0] FWT[A_1],; FWT[A_1]) $$$$ UFWT[A] merge(UFWT[A_0] - UFWT[A_1],; UFWT[A_1]) $$同样顺变换时 $\text{type}1$逆变换时 $\text{type}-1$。与卷积的迭代实现只需把叠加方向反过来void And(ll *a, ll type) { for (ll x 2; x n; x 1) { ll k x 1; for (ll i 0; i n; i x) { for (ll j 0; j k; j) { (a[i j] a[i j k] * type) % P; } } } }异或卷积关键引理异或卷积基于如下原理令 $x\circ y$ 表示 $x\cap y$ 中 $1$ 的数量的奇偶性即$$ x\circ y\text{popcnt}(x\cap y)\bmod 2 $$容易验证 $(x\circ y)\oplus (x\circ z)x\circ(y\oplus z)$。变换的定义与正确性证明定义变换$$ FWT[A]i\sum{i\circ j0}A_j-\sum_{i\circ j1}A_j $$其卷积定理可证明如下$$ \begin{aligned} FWT[A]iFWT[B]i\left(\sum{i\circ j0}A_j-\sum{i\circ j1}A_j\right)\left(\sum_{i\circ k0}B_k-\sum_{i\circ k1}B_k\right) \ \left(\sum_{i\circ j0}A_j\sum_{i\circ k0}B_k\sum_{i\circ j1}A_j\sum_{i\circ k1}B_k\right)-\left(\sum_{i\circ j0}A_j\sum_{i\circ k1}B_k\sum_{i\circ j1}A_j\sum_{i\circ k0}B_k\right) \ \sum_{(j\oplus k)\circ i0}A_jB_k-\sum_{(j\oplus k)\circ i1}A_jB_k \ FWT[C]_i \end{aligned} $$分治求值依旧分治讨论最高位对最高位为 $0$ 的子数列 $A_0$与 $0$ 或 $1$ 做 $\circ$ 运算结果都不变因为 $0\cap 00,;0\cap10$所以 $\sum_{i\circ j1}A_j0$对最高位为 $1$ 的子数列 $A_1$与 $0$ 运算结果为 $0$、与 $1$ 运算结果为 $1$因为 $1\cap 00,;1\cap11$。综合两者得到$$ FWT[A] merge(FWT[A_0] FWT[A_1],; FWT[A_0] - FWT[A_1]) $$逆变换只需解一个二元一次方程组$$ UFWT[A] merge\left(\frac{UFWT[A_0] UFWT[A_1]}{2},; \frac{UFWT[A_0] - UFWT[A_1]}{2}\right) $$迭代实现顺变换时 $\text{type}1$逆变换时 $\text{type}\frac{1}{2}$注意这里与或 / 与卷积不同逆变换的缩放系数是 $\frac{1}{2}$ 而非 $-1$因为异或的位矩阵行列式为 $2$void Xor(ll *a, ll type) { for (ll x 2; x n; x 1) { ll k x 1; for (ll i 0; i n; i x) { for (ll j 0; j k; j) { (a[i j] a[i j k]) % P; (a[i j k] a[i j] - a[i j k] * 2) % P; (a[i j] * type) % P; (a[i j k] * type) % P; } } } }同或卷积类比异或运算可给出同或卷积的公式。设 $C_1$ 表示 $\text{popcnt}(x\cup y)\bmod 2$ 为 $0$ 的集合$C_2$ 表示该值为 $1$ 的集合定义$$ FWT[A]{i} \sum{C_1}A_{j} - \sum_{C_2}A_{j} $$分治递推式为$$ FWT[A] merge(FWT[A_1] - FWT[A_0],; FWT[A_1] FWT[A_0]) $$$$ UFWT[A] merge\left(\frac{UFWT[A_1] - UFWT[A_0]}{2},; \frac{UFWT[A_1] UFWT[A_0]}{2}\right) $$同或运算在竞赛中出现频率较低但其与异或之间仅相差一次下标翻转理解异或后即可自然迁移。另一个角度的 FWT位矩阵视角以上推导看似各运算各有各的形态实际上可以用统一的系数矩阵语言重新描述。设 $c(i,j)$ 是 $A_j$ 对 $FWT[A]_i$ 的贡献系数则变换过程可以重写为$$ FWT[A]i \sum{j0}^{n-1} c(i,j) A_j $$由 $FWT[A]_i\cdot FWT[B]_iFWT[C]_i$ 可以简单证明$$ c(i,j)c(i,k)c(i,j\odot k) $$其中 $\odot$ 是任意一种位运算。这是 FWT 构造的核心充要条件——任何满足该恒等式的系数矩阵都给出一种合法的变换。按位拆分只需要一个 2×2 矩阵$c$ 函数还有一个重要性质它可以按位处理。直接计算 $FWT[A]i \sum{j0}^{n-1} c(i,j) A_j$ 是 $O(n^2)$ 的但把它按最高位拆成两半$$ FWT[A]i \sum{j0}^{n/2-1} c(i,j) A_j\sum_{jn/2}^{n-1} c(i,j) A_j $$前后两个求和式中 $i,j$ 只有最高位不同。去除最高位后记 $i,j$并记 $i_0$ 为 $i$ 的最高位有$$ FWT[A]i c(i_0,0)\sum{j0}^{n/2-1} c(i,j) A_jc(i_0,1)\sum_{jn/2}^{n-1} c(i,j) A_j $$当 $i_00$ 时得到 $FWT[A]i c(0,0)\sum{j0}^{n/2-1} c(i,j) A_jc(0,1)\sum_{jn/2}^{n-1} c(i,j) A_j$当 $i_01$ 时得到 $FWT[A]i c(1,0)\sum{j0}^{n/2-1} c(i,j) A_jc(1,1)\sum_{jn/2}^{n-1} c(i,j) A_j$。也就是说我们只需要$$ \begin{bmatrix} c(0,0) c(0,1) \ c(1,0) c(1,1) \end{bmatrix} $$这四个数即位矩阵就可以完成整个变换——每一层分治只需对每个块应用这个 $2\times2$ 线性变换。逆变换则需要位矩阵的逆矩阵$$ A_i \sum_{j0}^n c^{-1}(i,j) FWT[A]_j $$注意逆矩阵不一定存在如果矩阵出现一整排 $0$ 或一整列 $0$该矩阵就没有逆构造时必须格外小心。按位或的位矩阵构造 $\begin{bmatrix}1 0 \ 1 1\end{bmatrix}$ 满足 $c(i,j)c(i,k)c(i,j\cup k)$。把它代入按位拆分的框架得到的正是前文推导的 $FWT[A]\text{merge}(FWT[A_0], FWT[A_0]FWT[A_1])$。该矩阵的逆为 $\begin{bmatrix}1 0 \ -1 1\end{bmatrix}$按顺变换的方法代入即可完成逆变换。值得警惕的是满足 $c(i,j)c(i,k)c(i,j\cup k)$ 的矩阵不止一个例如 $\begin{bmatrix}1 1 \ 1 0\end{bmatrix}$ 也满足条件但 $\begin{bmatrix}0 0 \ 1 1\end{bmatrix}$ 虽然同样满足该恒等式却因为存在一整排 $0$ 而没有逆不能用于逆变换因此不合法。按位与的位矩阵构造 $\begin{bmatrix}1 1 \ 0 1\end{bmatrix}$ 满足 $c(i,j)c(i,k)c(i,j\cap k)$逆矩阵为 $\begin{bmatrix}1 -1 \ 0 1\end{bmatrix}$。按位异或的位矩阵构造 $\begin{bmatrix}1 1 \ 1 -1\end{bmatrix}$ 满足 $c(i,j)c(i,k)c(i,j\oplus k)$即阿达马矩阵逆矩阵为 $\begin{bmatrix}0.5 0.5 \ 0.5 -0.5\end{bmatrix}$。逆矩阵中出现的 $0.5$ 因子正是异或逆变换代码里 $\text{type}\frac{1}{2}$ 的来源。FWT 是线性变换从矩阵视角立即可以看出FWT 是线性变换满足$$ FWT[AB]FWT[A]FWT[B] $$以及数乘保持$$ FWT[c\cdot A]c\cdot FWT[A] $$线性性在实战中有重要应用它意味着我们可以先对两个序列分别做 FWT、逐点相乘、再做逆变换也允许把一个序列整体变换到点值域后直接做幂运算如例题中求 $n$ 次幂而无需回到原域逐次卷积。K 维 FWT从二进制推广到 K 进制位运算的本质是对一个 $n$ 维 ${0,1}$ 向量逐维运算或运算就是每一维取 $\max$与运算就是每一维取 $\min$异或运算则是每一维对应相加再 $\bmod 2$。位运算有个特点向量的每一位都是独立的。把 ${0,1}$ 扩展到 $[0,K)\cap \mathbf{Z}$即 $K$ 进制看看会得到什么。max 运算或的推广将 $\cup$ 拓展为按位取 $\max$仍要求 $c(i,j)c(i,k)c(i,j\cup k)$。取 $jk$ 得 $c(i,j)c(i,j)c(i,j)$即每一行的 $1$ 只能出现在 $0$ 的前面否则不满足幂等性。手玩可得一组合法构造以 $K4$ 为例$$ \begin{bmatrix} 1 0 0 0 \ 1 1 0 0 \ 1 1 1 0 \ 1 1 1 1 \end{bmatrix} $$求逆得$$ \begin{bmatrix} 1 0 0 0 \ -1 1 0 0 \ 0 -1 1 0 \ 0 0 -1 1 \end{bmatrix} $$min 运算与的推广将 $\cap$ 拓展为按位取 $\min$由 $c(i,j)c(i,j)c(i,j)$ 可知每一行的 $1$ 只能出现在 $0$ 的后面。合法构造$$ \begin{bmatrix} 1 1 1 1 \ 0 1 1 1 \ 0 0 1 1 \ 0 0 0 1 \end{bmatrix} $$求逆得$$ \begin{bmatrix} 1 -1 0 0 \ 0 1 -1 0 \ 0 0 1 -1 \ 0 0 0 1 \end{bmatrix} $$前两者用得较少竞赛中更常见的是——不进位加法异或的推广范德蒙德矩阵将 $\oplus$ 拓展为按位相加再 $\bmod K$要求 $c(i,j)c(i,k)c(i,j\oplus k)$。若构造 $c(i,j)\omega_{K}^{j}$ 即可满足 $\omega_{K}^{j}\omega_{K}^{k}\omega_{K}^{j\oplus k}$但这样每一行都相同矩阵没有逆于是改用 $c(i,j)\omega_{K}^{(i-1)j}$得到$$ \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} $$此即范德蒙德矩阵求逆可得$\frac{1}{K}$ 为整体缩放因子指数取相反数$$ \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} $$如果题目给出的模数存在 $K$ 次单位根就可以直接用上述矩阵实现这正是 docs/math/poly/ntt.md 中原根思想的推广。模意义下没有单位根怎么办扩域与分圆多项式单位根在模意义下可能不存在例如模 $2^{58}$ 时。此时考虑扩域人为定义一个 $x$ 满足 $x^K1$直接把 $x$ 代入计算于是每个数都变成一个关于 $x$ 的 $k-1$ 次多项式在 $\bmod {x^K-1}$ 下做运算矩阵即为将 $\omega_K$ 全部替换为 $x$ 的形式。但 $\bmod x^K-1$ 可能存在零因子即一个数有多种表示方法无法确定真实值。解决方法是改为 $\bmod$分圆多项式$\Phi_{K}(x)$——它满足 $x$ 的阶恰为 $K$且在 $\mathbb{Q}$ 上不可约从而消除零因子问题。实际实现时由于 $\Phi_{K}(x)\mid x^k-1$可以先按 $\bmod x^k-1$ 计算分圆多项式次数更高、常数更大最后再 $\bmod \Phi_{K}(x)$收尾即可。例题实战CF 1103E「Radix sum」十进制不进位加法 K 维 FWT给定长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$对每个 $p\in[0,n-1]$ 求满足以下条件的整数序列 $i_1,i_2,\dots,i_n$ 的方案数对 $2^{58}$ 取模$\forall j \in [1,n] , i_j \in [1,n]$$\sum_{j1}^n a_{i_j} p$这里加法定义为十进制不进位加法。数据范围$n\le10^5,;a_i\le10^5$。思路设计 DP状态 $f_{i,s}$ 表示考虑到第 $i$ 个数、当前加法状态为 $s$ 的方案数。因为 FWT 是线性变换可以先把数组变换到 FWT 点值表示逐点变成自己的 $n$ 次幂再逆变换回来。本题难点在于模数 $2^{58}$ 下没有单位根因此必须扩域分圆多项式 $\Phi_{10}(x)x^4-x^3x^2-x1$。更麻烦的是UFWT 时需要除以进制 $10$而 $10$ 在模 $2^{58}$ 下没有逆元因为含因子 $2$。处理方法$5$ 在 $2^{58}$ 下存在逆元 $57646075230342349$先除以 $5$再单独处理因子 $2$。设已除以 $5$ 的答案为 $x$真实答案为 $y$即 $2^5y\equiv x\pmod{2^{64}}$那么 $y\equiv \frac{x}{2^5}\pmod{2^{64-5}}$即 $y\equiv \frac{x}{2^5}\pmod{2^{59}}$所以直接把最后答案除以 $2^5$ 再取下模即可。CF103329F「The Struggle」XXII OpenCup, Grand Prix of Xian给出一个椭圆 $E$其中所有整点坐标均在 $[1,4\cdot 10^6]$ 之间求$$ \sum_{(x,y) \in E} (x \oplus y)^{33}x^{-2}y^{-1} \bmod 10^97 $$这是一道比较不裸的题综合了椭圆整点计数、异或卷积与快速幂出题人提供了详细英文题解OI-wiki 中给出了原题与题解链接以便深入研究。参考资料与延伸阅读本文主体内容继承自 docs/math/poly/fwt.md作者Xeonacid、nocriz、ZnPdCo其原始推导参考了桃酱的算法笔记与 ZnPdCo 的博客沃尔什变换的数学背景可参见维基百科。在该文档之外OI-wiki 中还有多处与 FWT 直接相关的资源可供交叉阅读docs/math/poly/ntt.md数论变换与 FWT 同属变换到点值域再逐点相乘的框架其中原根、单位根的讨论是理解 K 维 FWT 模数条件的基础docs/math/poly/fft.md 与 docs/math/poly/intro.mdFFT 与多项式 / 生成函数的基本概念docs/math/combinatorics/inclusion-exclusion-principle.md容斥原理一文的 min-max 容斥部分明确使用了 FMT也称子集前缀和、FWT 或变换在 $O(2^nn)$ 时间内批量计算子集和是 FWT 在计数问题中的典型应用场景。掌握 FWT 的关键在于牢记 $FWT[C]FWT[A]\cdot FWT[B]$ 三段式流程、理解位矩阵 $c(i,j)c(i,k)c(i,j\odot k)$ 的构造条件、以及逆变换必须使用可逆矩阵警惕全零行 / 列。在此基础上无论是二进制下的或 / 与 / 异或卷积还是 K 进制下的不进位加法卷积都能在 $O(n\log n)$ 时间内统一解决。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考