最近刷题的时候碰到一道很有意思的题题目叫《算力训练》出处是某OJ编号P5577。题目标签非常简洁只有一个FWT但你要是真以为它是道板题那就太天真了。做这道题的过程中我把集合幂级数、异或卷积、卷积快速幂、生成函数建模这一整条线全部重新捋了一遍收获比预想中大得多。这篇就从一个普通做题人的视角讲讲我对这道题的理解它到底在算什么为什么非FWT不可以及实战中有哪些坑。1. 题目到底想让我们算什么1.1 先从模型说起这道题的具体描述我按自己比较认可的理解来展开。大致是有一堆元素每个元素的取值范围是0到2^m-1。每一次“训练”相当于对其中一个元素施加一次变换规则是把x变成x xor c其中c来自某个给定的变换集。要统计的是恰好执行K次训练之后整个集合到达目标状态的方案数。这里“方案”的统计口径很关键因为题目里不同位置、不同顺序是否算同一种方案会直接决定计数方式。我在做题时对比过同类题发现在这一点上如果不先想清楚后面推导很容易翻车。以通用模型而言通常把集合看成一个多重集的分布只关心每种取值的元素数量而不关心具体是哪个元素。这样处理后状态空间就从n个元素的排列问题降维成2^m个“桶”的计数问题才能继续往下做。1.2 为什么是卷积而不是矩阵乘法既然有了状态数组f接下来要处理“恰好K次”这个条件。如果一次变换是从状态x通过某种规则贡献到状态t那么两次变换呢显然要枚举第一次的结果作为中转把所有的中间结果加起来。这种“先枚举中间态再求和”的结构天然就是卷积。具体来说用数组g描述一次训练的作用g[c]表示“把x变成x xor c”这种转移有多少种权重。一次训练之后new_f[t] Σ_c f[t xor c] * g[c]如果把异或卷积定义为 h[t] Σ_{i xor j t} f[i] * g[j]那上式恰好就是t位置上的卷积值。两次训练就是 (f ⊗ g) ⊗ g f ⊗ g^{⊗2}K次就是 f ⊗ g^{⊗K}。因为异或卷积满足交换律和结合律幂次可以放心展开。到这里问题就非常数学化了算一个数组和一个固定数组的卷积的K次幂。1.3 朴素做法为什么不行如果m比较小比如m10状态数是1024暴力卷积一次需要1024^2 约100万次运算K次就要100万×K。K如果到1e9直接爆炸。如果m到17状态数是131072暴力卷积一次就要1.7e10次运算连一次都跑不动。所以必须使用快速变换。这里其实还有其他路比如把状态转移看成循环矩阵然后做矩阵快速幂。但循环矩阵乘法本质还是卷积你仍然需要NTT或者FWT。因为本题的合并运算是异或而不是模加法所以FFT/NTT那一套行不通得用FWT。2. FWT原理与前置知识2.1 异或卷积的定义先明确一下异或卷积的定义。给定两个长度都为n2^m的数组a和b异或卷积的结果c定义为c[k] Σ_{i xor j k} a[i] * b[j]如果直接用双重循环复杂度O(n^2)。但别忘了i xor j k这个条件在二进制下是按位独立决定的所以存在快速算法。它和普通卷积的区别只在于“合并规则”普通卷积是ijk这里是i xor jk。这里可以打个比方。假设a[i]表示左边口袋里有i颗糖的方案数b[j]表示右边口袋有j颗糖的方案数。普通卷积就是问两个口袋总共有k颗糖的方案数异或卷积则是问“糖数按位异或起来等于k”的方案数。后者在直觉上反常规但在二进制位运算的场景里非常自然。2.2 FWT在干什么点值化学过FFT的人都知道FFT之所以快是因为先把时域信号变换到频域把卷积变成逐点乘法算完再逆变换回来。FWT就是异或卷积世界的“FFT”。具体来说存在一个可逆线性变换T使得T(a ⊗ b)[i] T(a)[i] * T(b)[i]一旦有了这个性质卷积就可以拆成三步正变换、逐点乘、逆变换。对于异或卷积这个变换T是Hadamard变换矩阵由H_1 [[1, 1], [1, -1]]做张量积扩展而来。二维的H_2是四阶矩阵每一行互相正交并且 H_n^2 n I。这意味着逆变换和正变换几乎一样只是最后要除以n。2.3 为什么Hadamard矩阵能对角化异或卷积这里需要解释一个关键恒等式。设 w_i(x) (-1)^{popcount(i x)}也就是按位与后统计1的个数的奇偶性。那么w_i(p xor q) w_i(p) * w_i(q)为什么成立因为 (p xor q) i 的第bit位等于 (p i) 的第bit位异或 (q i) 的第bit位而(-1)的异或等于两个(-1)相乘。这个性质意味着异或运算在这个“特征空间”里变成了普通乘法。接着做变换推导A[i] Σ_x a[x] * w_i(x)C[i] Σ_k c[k] * w_i(k) Σ_k Σ_{x xor y k} a[x] b[y] w_i(x xor y) Σ_x Σ_y a[x] b[y] w_i(x) w_i(y) A[i] * B[i]整个过程清晰可见FWT的本质就是换成一组基把异或卷积变成普通乘法。2.4 FWT、FFT与NTT的选型对比我在做题时经常会把FWT和NTT搞混这里做一个对比表方便参考。变换适用运算变换矩阵逆变换适用场景FFT/NTT模加法的循环卷积单位根原根点乘后除以n多项式乘法、加法卷积FWT-xor异或卷积Hadamard矩阵正变换后除以n位运算题目、集合幂级数FWT-and/or按位与/或卷积0/1矩阵变体正变换后除以n位运算覆盖计数选型依据只有一个题目里的“合并运算”到底是什么。如果是加法用NTT如果是异或、与、或用FWT。这道题合并运算是异或答案明确。3. 核心实现与代码解析3.1 建模与预处理写代码之前先把数组定义清楚。设 N 1 m。f[x]初始多重集中值恰好为x的元素个数。g[c]一次训练中将某个元素从x变为x xor c的转移权重。如果题目说每次可选的c来自集合S那么g[c]就加1如果某些c出现多次或带权按权累计。答案数组 ans f ⊗ g^{⊗K}其中ans[t]表示经过K次训练后多重集中值为t的状态数量或方案数取决于统计口径。这里要强调如果元素之间的顺序也要区分处理方式会不一样。我见过很多题解直接写“答案就是卷积幂”但实际题目往往还有组合系数。稳妥做法先在规模很小的数据上手推答案确认卷积幂的语义和题目完全吻合之后再去套模板。至少对我而言这一步花的调试时间比FWT本身多得多。3.2 FWT模板放上我常用的异或FWT模板。它很短但细节非常多。#include bits/stdc.h using namespace std; typedef long long ll; const int MOD 998244353; ll qpow(ll a, ll b) { ll r 1; while (b) { if (b 1) r r * a % MOD; a a * a % MOD; b 1; } return r; } void fwt_xor(ll a[], int n) { for (int len 1; len n; len 1) { for (int i 0; i n; i (len 1)) { for (int j 0; j len; j) { ll u a[i j]; ll v a[i j len]; a[i j] (u v) % MOD; a[i j len] (u - v MOD) % MOD; } } } } void ifwt_xor(ll a[], int n) { fwt_xor(a, n); ll inv_n qpow(n, MOD - 2); for (int i 0; i n; i) a[i] a[i] * inv_n % MOD; }几个容易写错的点外层循环len从1开始每次乘2直到len n内层j只走到len-1不要走到2len减法必须加MOD再取模否则出来负数大数据直接错。注意如果想验证模板可以拿n4的随机数组先正变换再逆变换看是否还原。如果输出是全0或全变成n倍基本能锁定是变换或除法的问题。3.3 快速幂与整体流程有了模板之后主流程非常短int main() { int n, m, K; scanf(%d%d%d, n, m, K); int N 1 m; vectorll f(N, 0), g(N, 0); for (int i 0; i n; i) { int x; scanf(%d, x); f[x]; } int cnt; scanf(%d, cnt); for (int i 0; i cnt; i) { int c; scanf(%d, c); g[c]; } fwt_xor(f.data(), N); fwt_xor(g.data(), N); for (int i 0; i N; i) { ll cur qpow(g[i], K); f[i] f[i] * cur % MOD; } ifwt_xor(f.data(), N); for (int i 0; i N; i) { printf(%lld , f[i]); } return 0; }最核心的一行是f[i] f[i] * qpow(g[i], K) % MOD;。它利用了FWT把卷积幂变成逐点幂的性质。如果K非常大比如1e18也只需要log_K约60次乘法。3.4 几个容易忽略的边界第一个是K0。从语义上讲一次都不训练答案应该就是f本身。按照上面代码此时逐点快速幂qpow(g[i], 0) 1所以f经过正变换、乘1、逆变换之后还是f逻辑正确。但如果你在快速幂里特判0^0务必返回1否则在g[i] 0且K 0时出错。第二个是模数。998244353是质数可以直接用费马小定理求逆元。如果模数不是质数求逆元就得换exgcd或者利用n是2的幂每次除以2。建议优先用质数模数。第三个是输入范围。f和g数组长度都是1 mvector内存没问题但读入别用int存1 m的移位结果m大时会溢出。竞赛题一般m不超过20问题不大。4. 复杂度分析与常数优化4.1 理论复杂度一次FWT的时间复杂度是O(n log n)。每一层蝶形操作总数是n/2共log n层所以是(n/2) log n忽略常数后O(n log n)。本题做了两次FWTf和g、一次IFWTf加上O(n log K)的逐点快速幂。总复杂度O(n log n n log K n log n) O(n (m log K))以m17为例n 131072n log n约2.2e6n log K约3.9e6K到1e9合计约6e6次运算C轻松跑进1秒。对比暴力卷积一次n^2约1.7e10K次根本不可行。FWT在这里不是锦上添花而是唯一出路。4.2 常数与取模优化模运算比较贵可以做几件事加法合并uv最多2MOD用if (x MOD) x - MOD;代替%。减法合并u-v可能为负先加MOD再判断避免%。快速幂底数为0或1时可提前返回减少无谓乘法。开O2之后编译器会自动优化不少。给一个蝶形的快速写法示例ll u a[i j], v a[i j len]; a[i j] u v; if (a[i j] MOD) a[i j] - MOD; a[i j len] u - v; if (a[i j len] 0) a[i j len] MOD;每个蝶形只做两次条件判断没有模运算。快不少但可读性略降建议对拍通过后再换。4.3 空间与内存FWT是原地变换除了两个数组外几乎不占额外空间。内存方面1 20的long long数组是8MB一个两个16MB完全没问题。如果题目有多组询问可以把变换后的g缓存下来逐点幂或者按K离线排序避免重复正逆变换。这是进阶玩法本题单组询问一般用不到。5. 常见问题与踩坑实录5.1 正变换和逆变换搞混FWT模板太短很多人凭记忆敲。我见过不止一个人把逆变换写成每个蝶形除以2// 错误示范 a[i j] (u v) / 2; a[i j len] (u - v) / 2;模意义下的除法不是这么做的。正确做法是先做一次正变换再整体乘n的逆元。检测方法拿随机数组先正变换再逆变换看看能否还原。如果所有元素变成原来的n倍说明没除n如果乱七八糟说明变换本身写错。5.2 蝶形运算写错边界外层len从1到n步进加倍内层i步进len 1内层j到len - 1。我曾经把j写成0到len 1结果数组一片混乱。排查方法n 4的小数据手算一遍跟代码对拍。FWT手算只需几分钟能省几小时。以n4举例设输入为[a0, a1, a2, a3]FWT后的四个值分别是a0 a1 a2 a3a0 - a1 a2 - a3a0 a1 - a2 - a3a0 - a1 - a2 a3用这个公式验证自己的模板如果输出不对说明某一层写错了。5.3 减法取模的坑很多模板写(u - v MOD) % MOD在u-v为正时多一次无用模运算不影响正确性。但如果偷懒写(u - v) % MODu-v为负时结果是负数后面累加直接爆炸。我初学犯过一次后来养成习惯减法取模一律先加MOD。5.4 建模阶段的隐藏坑这道题表面上FWT真正决定AC的往往是“建模”而不是“变换”。我最开始直接把f和g丢进卷积样例过不了。后来发现题目要求的是“多重集”上的计数而f数组只统计了每个值的数量却没处理元素顺序带来的组合系数。解决方法如果一次训练选的c有重复g累计如果多重集中相同值的元素会被区分为不同方案f[x]初始时不能只记数量要考虑阶乘逆元等组合系数。如果完全不区分元素顺序f初始值就是普通计数卷积结果再乘阶乘即可。换句话说FWT只是锤子建模决定你钉的是钉子还是螺丝。我在这题卡了一晚上最后发现不是FWT的问题而是把“元素数量”和“方案数”搞混了。5.5 对拍建议确保模板无误的方式写一个暴力异或卷积在n4或8的随机数据上对拍。vectorll brute_conv(vectorll a, vectorll b) { int n a.size(); vectorll c(n, 0); for (int i 0; i n; i) for (int j 0; j n; j) c[i ^ j] (c[i ^ j] a[i] * b[j]) % MOD; return c; }对拍通过后后面出错基本锁定在建模部分而不是模板本身。我个人做完这道题之后最大的体会是FWT模板本身是“背下来就能用”级别的真正值钱的是理解它为什么能把卷积变成点乘。如果你正在准备竞赛我建议不要急着背代码先手推一次n4的Hadamard矩阵乘法再自己写一遍暴力卷积最后再上模板。这个过程虽然多花一个小时但之后遇到任何异或卷积的题目你都不会再慌。至于这道题它的建模部分如果读题不仔细哪怕FWT写得飞起也会被卡住。所以下次看到标签上只写了“FWT”的题记得多留个心眼锤子只是工具能不能钉好钉子看的是你对题目的理解。