看到洛谷 P5577 这道题的时候标签里只写着一个“FWT”我大概就猜到了它想考什么把一个计数问题放到 k 进制不进位加法卷积上再用广义快速沃尔什变换一次性算完。算力训练这道题本质上不是考你会不会背 FWT 模板而是考你能不能把“选择若干能力值最终异或和为某个数”这个模型干净地转成“多项式卷积 快速幂”。如果你只会二进制版本的异或 FWT第一次见到 k 进制版本多半会懵一会儿。这篇文章把整道题的拆解过程、数学原理、实现细节和调试心得都写清楚适合刚理解 FWT 但是还想再往深处走一步的选手。1. 题目到底在算什么k 进制不进位加法卷积1.1 从普通加法到不进位加法平时我们熟悉的卷积是普通加法卷积C[k] sum(A[i] * B[k - i])这个可以用多项式乘法和 FFT/NTT 解决。还有一种很常见的卷积是按位异或C[k] sum(A[i] * B[i xor k])这个用二进制 FWT 解决。算力训练里用的运算既不完全是普通加法也不是二进制异或而是“k 进制不进位加法”。什么叫 k 进制不进位加法把一个数写成 k 进制两个数相加时每一位各自相加然后对 k 取模不向下一位进位。比如 k3 的时候数字 5 写成三进制是12数字 7 写成三进制是21逐位相加最低位2 1 3模 3 后是 0次低位1 2 3模 3 后是 0所以 5 和 7 的三进制不进位加法结果是 0。你看这本质上是把数字拆成若干个独立的“位”每一位上的运算就是模 k 的同余类加法。换句话说这是一个群运算全体状态构成一个d维的向量空间(Z_k)^d。在这个群里做卷积普通的多项式卷积定义不适用了因为下标之间的“加法”不再是整数加法。但是只要是群上的卷积就存在对应的傅里叶变换也就是把卷积变成点乘。这就是 k 进制 FWT 存在的原因。1.2 两种常见的计数模型这类 FWT 计数题表面上千变万化实际上建模之后基本落在两个模型里。第一种模型是“同一个多项式自乘 m 次”。假设现在有 n 种能力值每次训练随机选一个能力值训练 m 次问最终能力值等于某个目标值的方案数。记初始数组f[x]为“一次选择得到能力值 x 的方案数”那么两次选择的方案数就是f * f这里的*是 k 进制不进位加法卷积。最终答案就是g f^(*m)也就是 f 在卷积意义下自乘 m 次。这个模型最舒服的地方在于FWT 之后点值域的乘法是普通乘法所以可以直接pow(fwt[f[i]], m)再逆变换回来。第二种模型是“每个物品最多选一次”。这时每个能力值 a 贡献的因子是1 x^a所有物品的生成函数是G(x) product_i (1 x^{a_i})需要求的是这个生成函数在目标下标上的系数。这里同样可以做 FWT变换域里每个点值变成G_hat[b] product_i (1 omega^{dot(b, a_i)})如果相同能力值数量很多可以按照计数合并再用快速幂处理重复项。算力训练这题我用第一种模型作为主线讲因为它的实现最干净也是最能体现“FWT 点值快速幂”套路核心的形式。如果你拿到的是第二种题面把最后的点值处理换成连续乘快速幂即可模板部分完全一样。1.3 复杂度目标和数据范围推测设总状态数N k^d其中 d 是 k 进制位数。朴素做法是每次做一次 O(N^2) 的卷积再做 m 次显然不可接受。FWT 的复杂度是O(d * N * k^2)这里 d 等于log_k(N)。当 k2 时它就是 O(N log N)当 k 是个很小的数时复杂度依然能接受。题目如果把 k 给得很大k^2 的常数就会很痛所以通常 k 是较小整数或者题目保证 k 整除模数减一。2. FWT 的本质群上的傅里叶变换2.1 从二进制异或 FWT 说起二进制异或 FWT 大家应该很熟了。长度为 2^d 的数组每一层都做这样的蝶形操作for len 1; len N; len 1: for i 0; i N; i len 1: for j 0; j len; j: u a[i j] v a[i j len] a[i j] u v a[i j len] u - v为什么这样变换之后卷积就变成点乘了因为异或群(Z_2)^d上的特征标只有两个取值1 和 -1。对每一维做长度为 2 的离散傅里叶变换就是上面这个加减操作。把 d 维都做完实际上就是对整个群做了多维傅里叶变换。卷积定理在任何局部紧阿贝尔群上都成立所以在异或群上也成立。2.2 推广到任意 k 进制现在把每一位的取值从 0/1 换成 0 到 k-1每一位上的运算是模 k 加法整个群是(Z_k)^d。这个时候特征标不再是 ±1而是 k 次单位根。我们需要一个 k 次本原单位根记为 omega满足omega^k 1且对于任意1 t komega^t ! 1。接下来对每一维做长度为 k 的 DFT。假如一个维上有 k 个值x[0..k-1]做 DFT 后得到X[b] sum_{a0}^{k-1} x[a] * omega^{a * b}这里的 a 是这个维度的取值b 是变换后的频率。把所有维度都这样变换一遍就完成了整个数组的 k 进制 FWT。为什么可以对每一维单独做因为群(Z_k)^d的特征标可以分解成每一维特征标的乘积。多维 DFT 是可分离的和一维 DFT 一样我们可以一维一维地做先做最低位维度再做次低位维度直到最高位维度。2.3 模意义下的单位根在模998244353意义下做 FWT而不是用浮点复数这是竞赛题里最常见的处理。前提是模数下存在 k 次本原单位根。998244353 是一个质数它有一个原根 3任意 k 次本原单位根可以这样求root 3^((MOD - 1) / k) mod MOD但这个式子成立的前提是(MOD - 1)能被 k 整除。998244353 减一是2^23 * 7 * 17所以只有当 k 的所有质因子都在{2, 7, 17}里时模意义下才存在对应的 k 次本原单位根。如果题目给的 k 不满足这个条件就要考虑换一个满足条件的质数或者用别的办法属于进阶话题这里先不展开。实际生成根的时候最好顺手验证一下检查pow(root, k)是否等于 1并且pow(root, k / p) ! 1对 k 的每个质因子 p 都成立。虽然多数时候出题人保证了存在性但自己写一遍校验总没坏处。3. 核心实现k 进制 FWT 模板与点值幂处理3.1 可复用的 k 进制 FWT 模板直接说结论模板按“下标是 k 进制数”来写。设数组长度为N k^d从低位开始每一轮按当前位分组组的间隔是len组大小是k * len。对每个分组内部取出间隔为len的 k 个元素做一次长度为 k 的 DFT。核心代码长这样#include bits/stdc.h using namespace std; const int MOD 998244353; const int G 3; long long qpow(long long a, long long b) { long long r 1; while (b) { if (b 1) r r * a % MOD; a a * a % MOD; b 1; } return r; } void fwt(vectorint a, int k, int d, bool inv) { int N 1; for (int i 0; i d; i) N * k; long long root qpow(G, (MOD - 1) / k); if (inv) root qpow(root, MOD - 2); // 逆变换用共轭单位根 // 预处理 k 进制 DFT 矩阵 vectorint pw(k); pw[0] 1; for (int i 1; i k; i) pw[i] pw[i - 1] * root % MOD; vectorvectorint mat(k, vectorint(k)); for (int i 0; i k; i) { for (int j 0; j k; j) { int exp (i * j) % k; if (inv) exp (k - exp) % k; mat[i][j] pw[exp]; } } long long invK qpow(k, MOD - 2); for (int len 1; len N; len * k) { for (int i 0; i N; i len * k) { for (int j 0; j len; j) { vectorint old(k), nxt(k); for (int t 0; t k; t) { old[t] a[i j t * len]; } // 一维 DFTnxt[b] sum_a old[a] * mat[b][a] for (int b 0; b k; b) { long long sum 0; for (int t 0; t k; t) { sum 1LL * old[t] * mat[b][t] % MOD; } nxt[b] sum % MOD; } for (int t 0; t k; t) { a[i j t * len] nxt[t]; } // 逆变换时每一维归一化 if (inv) { for (int t 0; t k; t) { a[i j t * len] a[i j t * len] * invK % MOD; } } } } } }这里的细节很容易出错重点说几个。第一len的更新是乘 k不是乘 2。因为这一轮处理的是 k 进制下的一位下一轮低位的跨度要扩大 k 倍。第二取出元素的下标是i j t * len。len是当前维度的权值t是该位上的取值。你可以想象一个 k 进制数当前位的值从 0 到 k-1它们恰好落在间隔为len的位置上。第三矩阵mat[b][a]里行是变换后的频率 b列是原值 a。正变换用omega^{a*b}逆变换用omega^{-a*b}。写反了会导致完全错误的结果。第四逆变换归一化。对于每一维 DFS 矩阵的逆要乘1/k。模板里每个分组做完逆变换后立刻乘以invKd 轮下来总共乘了 d 次等于乘了k^{-d}恰好抵消正变换没有缩放的问题。一些写法选择最后统一乘一次结果一样但逐维除更不容易漏。3.2 主流程点值快速幂自卷积对于“同一个多项式自乘 m 次”的模型主流程很短int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d, k; long long m; cin n m k d; int N 1; for (int i 0; i d; i) N * k; vectorint f(N, 0); for (int i 0; i n; i) { int x; cin x; f[x]; } fwt(f, k, d, false); for (int i 0; i N; i) { f[i] qpow(f[i], m); } fwt(f, k, d, true); int target; cin target; cout f[target] \n; return 0; }这里f[x]是一次训练选择到能力值 x 的方案数。自乘 m 次之后f[target]就是 m 次训练后能力值为 target 的方案数。如果你遇到的是第二种模型每个能力值最多选一次那么主流程就变成统计每个能力值的个数cnt[a]然后对每个频率 bfor (int b 0; b N; b) { long long res 1; for (auto [a, c] : cntMap) { // 计算 dot(b, a)b 和 a 的 k 进制逐位乘积之和 mod k int dot 0; int x b, y a; for (int bit 0; bit d; bit) { dot (dot (x % k) * (y % k)) % k; x / k; y / k; } long long base (1 pw[dot]) % MOD; res res * qpow(base, c) % MOD; } f[b] res; } // 然后逆变换这种模型适合能力值种类少的情况如果种类也接近 N额外的枚举代价就会很高。做题时先判断清楚题目是“同一个 f 自乘”还是“多个不同因子相乘”。3.3 为什么 FWT 之后可以直接点乘幂这一点值得多说两句。FWT 是线性变换把卷积变成点乘FWT(f * g) FWT(f) .* FWT(g)所以FWT(f^(*m)) FWT(f)^m这里的右乘是逐元素幂。卷积运算在变换域里“去卷积化”了原本每一层都要 O(N^2) 的卷积变成一层 O(N) 的普通乘法。再配合快速幂就把整个问题压到了接近线性对数的级别。这和普通 NTT 做多项式幂的思路完全一致只不过 FWT 处理的是群卷积。4. 复杂度分析、边界情况与题目变体4.1 复杂度对比做法单次卷积复杂度m 次总复杂度朴素幂FWT 幂次优化后暴力卷积O(N^2)O(m * N^2)—k 进制 FWTO(d * N * k^2)O(m * d * N * k^2)O(d * N * k^2 N log m)当 N 是 1e5 量级时暴力显然不行当 m 很大时连一层一层“快速幂式卷积”也不如直接变换域逐点幂。所以这个套路最大的优势在于不管 m 有多大都只在每个频率上做一次快速幂代价是 O(N log m)而不是 O(log m * 卷积代价)。4.2 特判和边界数据N 1 时即 d 0fwt 函数里的循环一次都不进逆变换也什么都不用做。此时所有能力值都是 0答案就是n^m或者类似的形式注意别让代码越界。k 1 时没有意义的因为每一位只有 0 一种取值数组长度永远是 1。一般题目不会出。m 0 时答案是单位元数组也就是只在能力值 0 的位置有 1。如果没特判快速幂也能得到正确结果0 的 0 次幂在模意义下按 1 处理但在某些实现里qpow(0, 0)可能会返回 0这里最好在循环里统一处理成当 m 0 时所有下标都赋 0再把f[0]赋成 1。如果读入的能力值可能大于 N说明能力值范围没有完全覆盖 k 进制位数那么要先检查输入是否合法或者在构造数组前把范围缩小。4.3 如果 K 进制位数不足做不对称的 FWT有些题目不是固定给 d而是给定能力值上限比如最大能力值小于 k^d但没有保证等于 k^d。这种情况下数组长度取大于等于最大值的k^d即可。变换时把不足 d 位的数在高位补 0因为补 0 不影响不进位加法。还有一种常见变体每一位的进制数不同比如最低位是 2 进制、次低位是 3 进制。这种“混合进制”的不进位加法也可以做 FWT只需要每一轮使用对应进制的单位根和 DFT 矩阵。实现上不要用统一的 k而是维护一个进制数组base[0..d-1]。洛谷 P5577 的原题应该是每一位进制相同的版本但如果你以后遇到混合进制原理是一样的。5. 踩坑记录与调试心得5.1 常见错误速查表症状可能原因解决办法逆变换后数组整体变大 k^d 倍逆变换没乘 1/k或少乘了一维每维依次乘逆元或者最后统一乘qpow(qpow(k, d), MOD-2)k2 的小样例过不了DFT 矩阵方向写反行/列混淆手推一个长度为 2 的数组逐层验证大样例答案差一点单位根选错(MOD-1) % k ! 0检查 k 是否整除 MOD-1或者打印pow(root,k)看是否等于 1FWT 变换后卷积性质不对len 的更新写成了乘 2改成 len * k速度很慢每个块都现算 DFT 矩阵预处理 k × k 矩阵不要在分组循环里重复算下标越界分组时i j t * len写错模拟 k2, N4手动走一遍循环5.2 对拍时怎么验证我写这类模板题习惯先做三步自测。第一步构造 k2、d2 的例子和一个已经写对的普通异或 FWT 模板对比。k 进制模板在 k2 时应完全退化成二进制 FWT这个对照能同时验证 len 循环和逆变换归一化。第二步用小数据随机验证卷积性质。随机生成数组 A 和 B用三重循环暴力算 k 进制不进位加法卷积 C然后用 FWT 快速还原。这里的卷积定义可以这样写for (int i 0; i N; i) { for (int j 0; j N; j) { int x i, y j, sum 0, mul 1, carry 0; for (int bit 0; bit d; bit) { int xi x % k, yi y % k; int s (xi yi) % k; sum s * mul; mul * k; x / k; y / k; } C[sum] (C[sum] 1LL * A[i] * B[j]) % MOD; } }对比fwt(fwt(A) .* fwt(B), true)的结果确认一致。第三步验证快速幂。取 m2暴力算f * f再对比fwt(qpow(fwt(f), 2), true)。这三步都过了基本可以确定模板没有结构性问题。5.3 一个容易忽视的性能点如果 k 比较大比如 k20d 又大朴素 O(N * d * k^2) 会非常吃力。这时候可以优化 DFT 矩阵乘法由于矩阵形状固定过程就是 k 维向量乘 k×k 矩阵。虽然复杂度仍然是 O(k^2)但可以通过位运算预计算、循环展开、或者只在每个分组里做一次矩阵乘来减少常数。更极端的情况还可以用快速傅里叶变换把一维 DFT 的 O(k^2) 降到 O(k log k)但对于 OI 题目里常见的 k 10没太大必要。另一个性能点点值快速幂的时候如果 m 很大且很多位置的值一样可以合并同类位置只做一次快速幂省去重复计算。实际比赛中常有人忽视这一点结果在极限数据上被卡常数。5.4 调试时的小技巧我习惯在 fwt 函数开头加一个断言检查N是否真的等于pow(k, d)。如果题目读入的不是 d 而是直接给 N就把 d 算出来这一步可以避免很多下标混乱。单位根初始化后顺手打印if (qpow(root, k) ! 1) cerr bad root\n; if (qpow(root, k / 2) 1 k % 2 0) cerr not primitive\n;我的经验是k 进制 FWT 模板写对一次之后后面很多类似题目都可以直接复用。重点不在于把代码背下来而在于理解每一层循环在做什么下标是 k 进制数当前位是哪一个对应的 DFT 矩阵是什么。理解了这些遇到混合进制、多维卷积、生成函数乘积多种变体都不会慌。这题对我个人最大的帮助是彻底把 FWT 从“二进制位运算加速工具”升级成了“阿贝尔群上的傅里叶变换”这个视角。以后再看到异或、同或、按位取模、循环移位这些运算第一反应都会是它是不是一个群运算如果是那就试一下能不能用广义 FWT 把卷积变成点乘。最后再分享一个小技巧如果身边没有板子现场推导 k2 异或 FWT 的蝶形步骤是最快的兜底方案但如果你把“一维 DFT 逐维扫描”的思路想清楚就算忘了模板也能从矩阵乘法现写一个能跑的版本。前提是单位根存在、模数允许。做这类题之前先看一眼MOD - 1的质因子比什么都强。