P5577 这题我第一次在洛谷题库里看到时说实话有点被名字唬住。“算力训练”听起来像要搞什么神经网络优化点进去看到一堆人刷 FWT又以为是那种需要大量数学推导的省选难题。实际坐下来推了一遍之后发现这道题的核心非常本质它就是给你一个带“异或”操作的递推过程最后用快速沃尔什变换把合并过程加速到可做的复杂度。如果你之前只听说过 FWT 的名字没真正上手推过异或卷积这篇复盘会比较适合你。我先把一个比较通用的“算力训练”模型讲清楚再沿着“为什么能用卷积建模”这条线走一遍最后把完整代码和踩过的坑一起摆出来。题目题面在不同平台的表述可能有点区别但只要看到“每个元素每一轮可以选择保持原值或者异或上某个给定常数”这种操作基本就是同一个套路。1. 先把手玩明白算力到底在训练什么把障碍词汇剥掉这个题的实际操作很简洁。假设有一堆初始元素第 i 个元素带着一个“算力值” a_i。接下来有 K 轮训练每轮训练里每个元素可以做出一次选择保持当前算力值不变把当前算力值异或上某个给定的常数 B_j其中 j 属于给定的操作集合。所有元素的选择互不影响所以本质上我们不是在跟踪单个元素而是在跟踪“当前值为 x 的方案数有多少”。最后题目要求的是经过 K 轮之后每个算力值 x 对应的方案数通常还会要求取模输出。这里一个很关键的点是因为只关心方案数不关心具体是哪条路径所以状态天然可以压缩成一个计数数组。[ dp[x] \text{当前值为 } x \text{ 的方案数} ]初始时dp[x] 就是输入里值为 x 的元素个数。每轮训练dp 数组会按照“保持”和“异或 B_j”两种转移规则更新。如果一次训练中允许的异或常数有多个就把每个都当作一个可选转移互不冲突。我刚开始做这题的时候第一反应是直接暴力模拟每一轮每一轮对每个位置枚举所有可选的 B_j 去更新数组。这个做法的问题非常明显假设值域大小是 (2^L)一轮的复杂度是 (O(2^L \cdot m))K 轮就是 (O(K \cdot 2^L \cdot m))。只要 K 稍微大一点完全受不了。但如果你观察每一轮的转移形式会发现它根本不是单点更新而是一个非常标准的卷积结构这就打开了另一条路。简单举个小例子体会一下。假设值域只有 0 到 3初始分布是[ dp [1, 1, 0, 0] ]也就是说有两个元素一个算力值是 0一个算力值是 1。再假设只有一种可选异或常数 (B 2)。那么经过一轮训练值为 0 的元素可以保持 0也可以异或 2 变成 2值为 1 的元素可以保持 1也可以异或 2 变成 3。所以最终分布是[ dp [1, 1, 1, 1] ]这看起来只是一个简单的分发过程但你要意识到dp 的每一个位置都同时收到了来自两个来源的贡献这种“多个来源合并到一个位置”的模式正是卷积的直觉。2. 把“保持/异或”两个动作装进一张卷积表如果要把每一步的训练过程写成数学式子可以定义一张转移计数表 g。g[s] 表示“每一轮里从某个值变成与之异或 s 的方案数”。因为每轮可以选择保持不动也可以选择异或某个 B_j所以[ g[0] 1 ][ g[B_j] \text{ 对应位置加上 1} ]用我们刚才的例子来说只有 B2 时[ g [1, 0, 1, 0] ]表示从 x 可以转移到 x xor 0也就是自己以及 x xor 2。现在看 dp 更新。一轮训练后某个值 x 的新方案数应该是所有能从旧状态转移到 x 的方案数之和。对于任意一个旧值 y如果想让 y 变成 x需要满足[ x y \oplus s ]也就是[ s x \oplus y ]所以[ dp_{new}[x] \sum_{y} dp_{old}[y] \cdot g[x \oplus y] ]这个式子是不是眼熟如果定义异或卷积[ (f * g)[x] \sum_{y} f[y] \cdot g[x \oplus y] ]那么一轮训练的本质就是[ dp_{new} dp_{old} * g ]其中的 * 是异或卷积。这个结论非常重要因为它意味着我们不用真的去枚举每个转移可以把每一轮训练看成一次整体卷积。很多同学第一次看到“把 DP 写成卷积”会觉得有点抽象。这里我自己的理解方式是卷积算的就是“来源和转移”的配对。旧位置 y 相当于贡献者g 里的每一个非零位置 s 相当于一种转移方式两者合法配对时目标位置恰好是 x。如果把一轮写成卷积那么两轮就是[ dp_2 (dp_0 * g) * g ]三轮就是[ dp_3 ((dp_0 * g) * g) * g ]于是 K 轮训练就变成了[ dp_K dp_0 * g * g * \cdots * g ]也就是 dp_0 和 K 个 g 做异或卷积。到这里问题从“模拟 K 轮”变成了“算 K 次异或卷积”但直接算卷积依然是 O(值域大小平方) 的复杂度K 轮还是没法接受。真正的转机在于异或卷积有一种非常漂亮的加速方法那就是 FWT。3. FWT 如何把异或卷积变成点值相乘快速沃尔什变换Fast Walsh-Hadamard Transform做的事情和 FFT 在多项式卷积里做的事情非常像它把“卷积”变成“对应位置相乘”。先定义异或卷积下的 FWT 变换。对于一个长度为 (2^L) 的数组 f定义它变换后某个下标 S 的值为[ F[S] \sum_{x} f[x] \cdot (-1)^{popcount(x S)} ]这里的 popcount 是二进制里 1 的个数。这个式子初看很奇怪但它的核心性质非常完美。如果你有两个数组 f 和 g它们的异或卷积是 h那么对于任意一个 S都有[ H[S] F[S] \cdot G[S] ]也就是说先把 f 和 g 都做一次 FWT 变换然后在变换后的域里把对应位置乘起来最后逆变换回去就能得到 h。这比直接在原数组上做卷积要快得多。为什么这个性质成立关键在于那个符号因子[ (-1)^{popcount((x \oplus y) S)} ]可以拆成[ (-1)^{popcount(x S)} \cdot (-1)^{popcount(y S)} ]因为逐位异或只会影响 1 的个数的奇偶性如果某一位上 x 和 y 在该位都为 1那么异或后的这一位是 0但同时两个符号相乘会带来一个 (-1) 的平方。整体来看奇偶性是线性可拆的。于是卷积求和里的每一项都能分离成两个独立因子的乘积整理之后自然就得到了点值相乘的结论。算法竞赛里写 FWT 的迭代实现实际上就是不断套用一个叫“蝴蝶变换”的操作。对于异或 FWT核心递推关系是[ a_{new}[i] a[i] a[i len] ][ a_{new}[i len] a[i] - a[i len] ]整个流程大致是首先让 len 从 1 开始每次翻倍直到 len 等于整个数组长度。每一轮都把数组按照 2*len 的大小分成一段段在每一段内部对相距 len 的两个位置做上面的加减操作。如果你手推一个长度为 4 的小例子会看到它其实是在不断合并相邻块的信息。标准异或 FWT 的逆变换也很简单把同样的蝴蝶操作再做一遍最后整体乘以 (2^{-L})。因为变换矩阵自身有个非常对称的性质做两次蝴蝶操作相当于乘上 (2^L)。这一步我可以给一个非常直观的类比FFT 是把时域信号转换到频域卷积在频域里变成乘法FWT 就是把“异或操作的世界”映射到另一个坐标系在这个坐标系里异或卷积也变成了逐点乘法。虽然两个变换矩阵长得不一样但思想完全一脉相承。4. 多轮训练的实质点值域里做一次快速幂回到算力训练这道题。我们已经把一轮训练表达成异或卷积[ dp_{t1} dp_t * g ]把两边都做 FWT 变换。设变换后的数组用大写字母表示那么根据上一节的核心性质[ DP_{t1}[S] DP_t[S] \cdot G[S] ]这就有意思了。原来在原数组里每一轮都要做一次完整的卷积但变换后的域里每一轮只是把 DP 的每一个位置都乘以 G 的对应位置。K 轮之后[ DP_K[S] DP_0[S] \cdot (G[S])^K ]所以整个算法流程非常简洁根据初始元素构造 dp 数组根据“保持”和“异或 B_j”构造 g 数组分别对 dp 和 g 做 FWT对每个位置 S计算 (G[S]^K)然后乘上 (DP_0[S])对整个结果数组做逆 FWT逐位输出答案。这里最重要的思想就是“变换后的点值可以直接做幂运算”。因为 FWT 是线性变换而且异或卷积在变换域里就是逐点乘积所以重复卷积等于重复逐点乘法自然可以合并成一次快速幂。如果题目给定的每一轮转移常数不同那就不能无脑快速幂了需要把每一轮的 G 都变换出来然后逐点乘起来。但那已经不是“算力训练”这一题的典型形态思路是一样的。复杂度方面也很清爽。设值域大小是 (N 2^L)一次 FWT 是 O(NL)快速幂部分每个位置需要跑一次 O(log K) 的幂运算所以总复杂度是[ O(NL N \log K NL) ]也就是[ O(NL N \log K) ]这个复杂度对于 (2^{17}) 左右的值域规模K 给到 (10^{18}) 级别都是可以轻松承受的。回到刚才那个小例子验证一遍。初始 dp [1, 1, 0, 0]g [1, 0, 1, 0]K1。先对 dp 做 FWT得到[ DP [2, 0, 2, 0] ]对 g 做 FWT得到[ G [2, -2, 0, 0] ]逐点相乘[ DP \cdot G [4, 0, 0, 0] ]逆 FWT 之后得到[ [1, 1, 1, 1] ]和我们手推的结果一致。这个过程虽然简单但已经把一个普通的 DP 模拟题成功转化成了 FWT 的板子。5. 完整代码与容易踩的细节下面这份 C 代码是我比较习惯的写法按前面说的流程实现。输入格式不做死板假设大致就是先读元素个数 n、异或常数个数 m、训练轮数 K再读 n 个初始值然后读 m 个转移常数。实际做题时按题面微调输入部分就行。#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 998244353; ll mod_pow(ll a, ll e) { ll r 1; while (e 0) { if (e 1) r r * a % MOD; a a * a % MOD; e 1; } return r; } void fwt(vectorll a, int inv) { int n a.size(); 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 x a[i j]; ll y a[i j len]; a[i j] (x y) % MOD; a[i j len] (x - y MOD) % MOD; } } } if (inv) { ll inv_n mod_pow(n, MOD - 2); for (int i 0; i n; i) a[i] a[i] * inv_n % MOD; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; ll K; cin n m K; int maxv 0; vectorll init(n); for (int i 0; i n; i) { cin init[i]; maxv max(maxv, (int)init[i]); } vectorll op(m); for (int i 0; i m; i) { cin op[i]; maxv max(maxv, (int)op[i]); } int L 0; while ((1 L) maxv) L; int len 1 L; vectorll dp(len, 0), g(len, 0); for (ll x : init) dp[x] (dp[x] 1) % MOD; g[0] 1; for (ll x : op) g[x] (g[x] 1) % MOD; fwt(dp, 0); fwt(g, 0); for (int i 0; i len; i) { dp[i] dp[i] * mod_pow(g[i], K) % MOD; } fwt(dp, 1); for (int i 0; i len; i) { cout dp[i] \n; } return 0; }这个代码里我觉得最需要提醒的有四个地方每一个我都实际踩过。第一个坑是 g[0] 容易漏。如果你只把 B_j 的位置设成 1忘了“保持不动”这个转移那一轮训练之后的总方案数会从原来翻倍变成只增加 m 个位置显然不对。g[0] 就是那个保持转移的计数别漏。第二个坑是 FWT 逆变换里的除法。很多模板用除以 n 表示但这里 n 是 2 的幂在模 998244353 意义下需要求逆元用模意义下的逆而不是直接用整数去除。费马小定理在这里很合适因为 998244353 是质数。如果你写成每次蝴蝶操作都除以 2也可能对但效率会差而且容易把模数搞混。第三个坑是负值取模。FWT 过程中会出现减法比如 (x - y) % MOD 在 C 里可能得到负数。虽然数学上负数取模也合法但后续乘法可能会出问题。稳妥的做法是统一写成(x - y MOD) % MOD只加一次 MOD 就够了因为 x 和 y 都已经被约束在 [0, MOD) 内减完一定大于 -MOD。第四个坑是值域长度。不要只根据 init 的最大值去定 L还要看操作数 op 里的最大值。因为异或运算可能把值提升到和 op 同级别的位如果 op 里有更大的二进制位而数组长度没开够访问就会越界或者丢方案。稳妥起见计算 L 的时候把初始值和操作数全部扫一遍取 max。除了这四点还有一个细节是 K 为 0 的情况。K0 表示没有训练答案应该就是初始分布。上面的代码里 mod_pow(g[i], 0) 会返回 1乘完之后 dp 不变所以也能正确处理不需要额外特判。6. 把套路抽出来异或卷积幂还能用在哪些地方算力训练这题做完之后我自己最大的收获并不是“会写 FWT 板子”而是建立了一种识别问题模型的直觉只要看到 DP 转移是“x 可以变成 x xor B”这种形式并且要统计方案数十有八九是异或卷积如果再配上“操作重复 K 轮”这个条件那就是异或卷积幂也就是 FWT 加快速幂。沿着这个想法很多变体就都能看穿了。比如说每轮训练不是只能选一个异或常数而是允许从一组常数里自由选那只需要把 g 里对应位置多加几个 1。如果说每个转移还有不同权重那就在 g 里对应位置加权本质完全不变。如果说转移不只是异或还有按位与或者按位或那就可以用另外两种 FWT 变体来处理逻辑上是同一套“变换后点值相乘”的框架。我还想提一个比较常见的扩展方向如果把 K 轮改成一棵树上从根到叶子的路径询问每轮允许的转移集合不同那就不能用快速幂了而是要把每一步的 g 分别做 FWT然后利用线段树维护区间乘积。也就是说FWT 点值域里的“乘法”和普通线段树维护的信息可以无缝结合。这类题目通常会把数据范围设计成“总轮数很多但每轮独立”这时候不要傻乎乎一轮一轮乘回去要想办法批量处理。最后分享一点个人心得。我学 FWT 的时候曾经一直死记那个蝴蝶变换的加减顺序后来才发现最好的记忆方式就是回到二维小例子长度为 2 时变换矩阵就是 [[1, 1], [1, -1]]因为异或只有 0 和 1 两个值符号因子恰好能构成这个矩阵。更大的长度只是不断对每个二进制维度递归套用这个二维变换理解了这一点代码里的三层循环就再也不会写错了。如果你也是第一次接触这种题建议把题目中的小数据手动模拟一遍再用代码对拍。尤其是那种 K 很小、值域也很小的测试点手推一遍再跑一遍程序比单纯看十篇题解都管用。FWT 本身不难写难的是想通“为什么重复卷积可以放进点值域做快速幂”这一步想通了算力训练这类题的题眼就算彻底抓住了。 
长河君 · 2026/10/13 1:15:17 · 阅读 1.2k FWT解决异或卷积幂：从算力训练看快速沃尔什变换的应用
P5577 这题我第一次在洛谷题库里看到时说实话有点被名字唬住。“算力训练”听起来像要搞什么神经网络优化点进去看到一堆人刷 FWT又以为是那种需要大量数学推导的省选难题。实际坐下来推了一遍之后发现这道题的核心非常本质它就是给你一个带“异或”操作的递推过程最后用快速沃尔什变换把合并过程加速到可做的复杂度。如果你之前只听说过 FWT 的名字没真正上手推过异或卷积这篇复盘会比较适合你。我先把一个比较通用的“算力训练”模型讲清楚再沿着“为什么能用卷积建模”这条线走一遍最后把完整代码和踩过的坑一起摆出来。题目题面在不同平台的表述可能有点区别但只要看到“每个元素每一轮可以选择保持原值或者异或上某个给定常数”这种操作基本就是同一个套路。1. 先把手玩明白算力到底在训练什么把障碍词汇剥掉这个题的实际操作很简洁。假设有一堆初始元素第 i 个元素带着一个“算力值” a_i。接下来有 K 轮训练每轮训练里每个元素可以做出一次选择保持当前算力值不变把当前算力值异或上某个给定的常数 B_j其中 j 属于给定的操作集合。所有元素的选择互不影响所以本质上我们不是在跟踪单个元素而是在跟踪“当前值为 x 的方案数有多少”。最后题目要求的是经过 K 轮之后每个算力值 x 对应的方案数通常还会要求取模输出。这里一个很关键的点是因为只关心方案数不关心具体是哪条路径所以状态天然可以压缩成一个计数数组。[ dp[x] \text{当前值为 } x \text{ 的方案数} ]初始时dp[x] 就是输入里值为 x 的元素个数。每轮训练dp 数组会按照“保持”和“异或 B_j”两种转移规则更新。如果一次训练中允许的异或常数有多个就把每个都当作一个可选转移互不冲突。我刚开始做这题的时候第一反应是直接暴力模拟每一轮每一轮对每个位置枚举所有可选的 B_j 去更新数组。这个做法的问题非常明显假设值域大小是 (2^L)一轮的复杂度是 (O(2^L \cdot m))K 轮就是 (O(K \cdot 2^L \cdot m))。只要 K 稍微大一点完全受不了。但如果你观察每一轮的转移形式会发现它根本不是单点更新而是一个非常标准的卷积结构这就打开了另一条路。简单举个小例子体会一下。假设值域只有 0 到 3初始分布是[ dp [1, 1, 0, 0] ]也就是说有两个元素一个算力值是 0一个算力值是 1。再假设只有一种可选异或常数 (B 2)。那么经过一轮训练值为 0 的元素可以保持 0也可以异或 2 变成 2值为 1 的元素可以保持 1也可以异或 2 变成 3。所以最终分布是[ dp [1, 1, 1, 1] ]这看起来只是一个简单的分发过程但你要意识到dp 的每一个位置都同时收到了来自两个来源的贡献这种“多个来源合并到一个位置”的模式正是卷积的直觉。2. 把“保持/异或”两个动作装进一张卷积表如果要把每一步的训练过程写成数学式子可以定义一张转移计数表 g。g[s] 表示“每一轮里从某个值变成与之异或 s 的方案数”。因为每轮可以选择保持不动也可以选择异或某个 B_j所以[ g[0] 1 ][ g[B_j] \text{ 对应位置加上 1} ]用我们刚才的例子来说只有 B2 时[ g [1, 0, 1, 0] ]表示从 x 可以转移到 x xor 0也就是自己以及 x xor 2。现在看 dp 更新。一轮训练后某个值 x 的新方案数应该是所有能从旧状态转移到 x 的方案数之和。对于任意一个旧值 y如果想让 y 变成 x需要满足[ x y \oplus s ]也就是[ s x \oplus y ]所以[ dp_{new}[x] \sum_{y} dp_{old}[y] \cdot g[x \oplus y] ]这个式子是不是眼熟如果定义异或卷积[ (f * g)[x] \sum_{y} f[y] \cdot g[x \oplus y] ]那么一轮训练的本质就是[ dp_{new} dp_{old} * g ]其中的 * 是异或卷积。这个结论非常重要因为它意味着我们不用真的去枚举每个转移可以把每一轮训练看成一次整体卷积。很多同学第一次看到“把 DP 写成卷积”会觉得有点抽象。这里我自己的理解方式是卷积算的就是“来源和转移”的配对。旧位置 y 相当于贡献者g 里的每一个非零位置 s 相当于一种转移方式两者合法配对时目标位置恰好是 x。如果把一轮写成卷积那么两轮就是[ dp_2 (dp_0 * g) * g ]三轮就是[ dp_3 ((dp_0 * g) * g) * g ]于是 K 轮训练就变成了[ dp_K dp_0 * g * g * \cdots * g ]也就是 dp_0 和 K 个 g 做异或卷积。到这里问题从“模拟 K 轮”变成了“算 K 次异或卷积”但直接算卷积依然是 O(值域大小平方) 的复杂度K 轮还是没法接受。真正的转机在于异或卷积有一种非常漂亮的加速方法那就是 FWT。3. FWT 如何把异或卷积变成点值相乘快速沃尔什变换Fast Walsh-Hadamard Transform做的事情和 FFT 在多项式卷积里做的事情非常像它把“卷积”变成“对应位置相乘”。先定义异或卷积下的 FWT 变换。对于一个长度为 (2^L) 的数组 f定义它变换后某个下标 S 的值为[ F[S] \sum_{x} f[x] \cdot (-1)^{popcount(x S)} ]这里的 popcount 是二进制里 1 的个数。这个式子初看很奇怪但它的核心性质非常完美。如果你有两个数组 f 和 g它们的异或卷积是 h那么对于任意一个 S都有[ H[S] F[S] \cdot G[S] ]也就是说先把 f 和 g 都做一次 FWT 变换然后在变换后的域里把对应位置乘起来最后逆变换回去就能得到 h。这比直接在原数组上做卷积要快得多。为什么这个性质成立关键在于那个符号因子[ (-1)^{popcount((x \oplus y) S)} ]可以拆成[ (-1)^{popcount(x S)} \cdot (-1)^{popcount(y S)} ]因为逐位异或只会影响 1 的个数的奇偶性如果某一位上 x 和 y 在该位都为 1那么异或后的这一位是 0但同时两个符号相乘会带来一个 (-1) 的平方。整体来看奇偶性是线性可拆的。于是卷积求和里的每一项都能分离成两个独立因子的乘积整理之后自然就得到了点值相乘的结论。算法竞赛里写 FWT 的迭代实现实际上就是不断套用一个叫“蝴蝶变换”的操作。对于异或 FWT核心递推关系是[ a_{new}[i] a[i] a[i len] ][ a_{new}[i len] a[i] - a[i len] ]整个流程大致是首先让 len 从 1 开始每次翻倍直到 len 等于整个数组长度。每一轮都把数组按照 2*len 的大小分成一段段在每一段内部对相距 len 的两个位置做上面的加减操作。如果你手推一个长度为 4 的小例子会看到它其实是在不断合并相邻块的信息。标准异或 FWT 的逆变换也很简单把同样的蝴蝶操作再做一遍最后整体乘以 (2^{-L})。因为变换矩阵自身有个非常对称的性质做两次蝴蝶操作相当于乘上 (2^L)。这一步我可以给一个非常直观的类比FFT 是把时域信号转换到频域卷积在频域里变成乘法FWT 就是把“异或操作的世界”映射到另一个坐标系在这个坐标系里异或卷积也变成了逐点乘法。虽然两个变换矩阵长得不一样但思想完全一脉相承。4. 多轮训练的实质点值域里做一次快速幂回到算力训练这道题。我们已经把一轮训练表达成异或卷积[ dp_{t1} dp_t * g ]把两边都做 FWT 变换。设变换后的数组用大写字母表示那么根据上一节的核心性质[ DP_{t1}[S] DP_t[S] \cdot G[S] ]这就有意思了。原来在原数组里每一轮都要做一次完整的卷积但变换后的域里每一轮只是把 DP 的每一个位置都乘以 G 的对应位置。K 轮之后[ DP_K[S] DP_0[S] \cdot (G[S])^K ]所以整个算法流程非常简洁根据初始元素构造 dp 数组根据“保持”和“异或 B_j”构造 g 数组分别对 dp 和 g 做 FWT对每个位置 S计算 (G[S]^K)然后乘上 (DP_0[S])对整个结果数组做逆 FWT逐位输出答案。这里最重要的思想就是“变换后的点值可以直接做幂运算”。因为 FWT 是线性变换而且异或卷积在变换域里就是逐点乘积所以重复卷积等于重复逐点乘法自然可以合并成一次快速幂。如果题目给定的每一轮转移常数不同那就不能无脑快速幂了需要把每一轮的 G 都变换出来然后逐点乘起来。但那已经不是“算力训练”这一题的典型形态思路是一样的。复杂度方面也很清爽。设值域大小是 (N 2^L)一次 FWT 是 O(NL)快速幂部分每个位置需要跑一次 O(log K) 的幂运算所以总复杂度是[ O(NL N \log K NL) ]也就是[ O(NL N \log K) ]这个复杂度对于 (2^{17}) 左右的值域规模K 给到 (10^{18}) 级别都是可以轻松承受的。回到刚才那个小例子验证一遍。初始 dp [1, 1, 0, 0]g [1, 0, 1, 0]K1。先对 dp 做 FWT得到[ DP [2, 0, 2, 0] ]对 g 做 FWT得到[ G [2, -2, 0, 0] ]逐点相乘[ DP \cdot G [4, 0, 0, 0] ]逆 FWT 之后得到[ [1, 1, 1, 1] ]和我们手推的结果一致。这个过程虽然简单但已经把一个普通的 DP 模拟题成功转化成了 FWT 的板子。5. 完整代码与容易踩的细节下面这份 C 代码是我比较习惯的写法按前面说的流程实现。输入格式不做死板假设大致就是先读元素个数 n、异或常数个数 m、训练轮数 K再读 n 个初始值然后读 m 个转移常数。实际做题时按题面微调输入部分就行。#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 998244353; ll mod_pow(ll a, ll e) { ll r 1; while (e 0) { if (e 1) r r * a % MOD; a a * a % MOD; e 1; } return r; } void fwt(vectorll a, int inv) { int n a.size(); 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 x a[i j]; ll y a[i j len]; a[i j] (x y) % MOD; a[i j len] (x - y MOD) % MOD; } } } if (inv) { ll inv_n mod_pow(n, MOD - 2); for (int i 0; i n; i) a[i] a[i] * inv_n % MOD; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; ll K; cin n m K; int maxv 0; vectorll init(n); for (int i 0; i n; i) { cin init[i]; maxv max(maxv, (int)init[i]); } vectorll op(m); for (int i 0; i m; i) { cin op[i]; maxv max(maxv, (int)op[i]); } int L 0; while ((1 L) maxv) L; int len 1 L; vectorll dp(len, 0), g(len, 0); for (ll x : init) dp[x] (dp[x] 1) % MOD; g[0] 1; for (ll x : op) g[x] (g[x] 1) % MOD; fwt(dp, 0); fwt(g, 0); for (int i 0; i len; i) { dp[i] dp[i] * mod_pow(g[i], K) % MOD; } fwt(dp, 1); for (int i 0; i len; i) { cout dp[i] \n; } return 0; }这个代码里我觉得最需要提醒的有四个地方每一个我都实际踩过。第一个坑是 g[0] 容易漏。如果你只把 B_j 的位置设成 1忘了“保持不动”这个转移那一轮训练之后的总方案数会从原来翻倍变成只增加 m 个位置显然不对。g[0] 就是那个保持转移的计数别漏。第二个坑是 FWT 逆变换里的除法。很多模板用除以 n 表示但这里 n 是 2 的幂在模 998244353 意义下需要求逆元用模意义下的逆而不是直接用整数去除。费马小定理在这里很合适因为 998244353 是质数。如果你写成每次蝴蝶操作都除以 2也可能对但效率会差而且容易把模数搞混。第三个坑是负值取模。FWT 过程中会出现减法比如 (x - y) % MOD 在 C 里可能得到负数。虽然数学上负数取模也合法但后续乘法可能会出问题。稳妥的做法是统一写成(x - y MOD) % MOD只加一次 MOD 就够了因为 x 和 y 都已经被约束在 [0, MOD) 内减完一定大于 -MOD。第四个坑是值域长度。不要只根据 init 的最大值去定 L还要看操作数 op 里的最大值。因为异或运算可能把值提升到和 op 同级别的位如果 op 里有更大的二进制位而数组长度没开够访问就会越界或者丢方案。稳妥起见计算 L 的时候把初始值和操作数全部扫一遍取 max。除了这四点还有一个细节是 K 为 0 的情况。K0 表示没有训练答案应该就是初始分布。上面的代码里 mod_pow(g[i], 0) 会返回 1乘完之后 dp 不变所以也能正确处理不需要额外特判。6. 把套路抽出来异或卷积幂还能用在哪些地方算力训练这题做完之后我自己最大的收获并不是“会写 FWT 板子”而是建立了一种识别问题模型的直觉只要看到 DP 转移是“x 可以变成 x xor B”这种形式并且要统计方案数十有八九是异或卷积如果再配上“操作重复 K 轮”这个条件那就是异或卷积幂也就是 FWT 加快速幂。沿着这个想法很多变体就都能看穿了。比如说每轮训练不是只能选一个异或常数而是允许从一组常数里自由选那只需要把 g 里对应位置多加几个 1。如果说每个转移还有不同权重那就在 g 里对应位置加权本质完全不变。如果说转移不只是异或还有按位与或者按位或那就可以用另外两种 FWT 变体来处理逻辑上是同一套“变换后点值相乘”的框架。我还想提一个比较常见的扩展方向如果把 K 轮改成一棵树上从根到叶子的路径询问每轮允许的转移集合不同那就不能用快速幂了而是要把每一步的 g 分别做 FWT然后利用线段树维护区间乘积。也就是说FWT 点值域里的“乘法”和普通线段树维护的信息可以无缝结合。这类题目通常会把数据范围设计成“总轮数很多但每轮独立”这时候不要傻乎乎一轮一轮乘回去要想办法批量处理。最后分享一点个人心得。我学 FWT 的时候曾经一直死记那个蝴蝶变换的加减顺序后来才发现最好的记忆方式就是回到二维小例子长度为 2 时变换矩阵就是 [[1, 1], [1, -1]]因为异或只有 0 和 1 两个值符号因子恰好能构成这个矩阵。更大的长度只是不断对每个二进制维度递归套用这个二维变换理解了这一点代码里的三层循环就再也不会写错了。如果你也是第一次接触这种题建议把题目中的小数据手动模拟一遍再用代码对拍。尤其是那种 K 很小、值域也很小的测试点手推一遍再跑一遍程序比单纯看十篇题解都管用。FWT 本身不难写难的是想通“为什么重复卷积可以放进点值域做快速幂”这一步想通了算力训练这类题的题眼就算彻底抓住了。