企业官网建设流程全解析

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} ]

用我们刚才的例子来说，只有 B=2 时：

[ 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_{t+1} = dp_t * g ]

把两边都做 FWT 变换。设变换后的数组用大写字母表示，那么根据上一节的核心性质：

[ DP_{t+1}[S] = DP_t[S] \cdot G[S] ]

这就有意思了。原来在原数组里每一轮都要做一次完整的卷积，但变换后的域里，每一轮只是把 DP 的每一个位置都乘以 G 的对应位置。K 轮之后：

[ DP_K[S] = DP_0[S] \cdot (G[S])^K ]

所以整个算法流程非常简洁：

1. 根据初始元素构造 dp 数组；
2. 根据“保持”和“异或 B_j”构造 g 数组；
3. 分别对 dp 和 g 做 FWT；
4. 对每个位置 S，计算 (G[S]^K)，然后乘上 (DP_0[S])；
5. 对整个结果数组做逆 FWT；
6. 逐位输出答案。

这里最重要的思想就是“变换后的点值可以直接做幂运算”。因为 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]，K=1。

先对 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(vector<ll>& 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; vector<ll> init(n); for (int i = 0; i < n; ++i) { cin >> init[i]; maxv = max(maxv, (int)init[i]); } vector<ll> 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; vector<ll> 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 的情况。K=0 表示没有训练，答案应该就是初始分布。上面的代码里 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 本身不难写，难的是想通“为什么重复卷积可以放进点值域做快速幂”，这一步想通了，算力训练这类题的题眼就算彻底抓住了。