企业官网建设流程全解析

最近刷题的时候碰到一道很有意思的题，题目叫《算力训练》，出处是某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比较小，比如m=10，状态数是1024，暴力卷积一次需要1024^2 = 约100万次运算，K次就要100万×K。K如果到1e9，直接爆炸。如果m到17，状态数是131072，暴力卷积一次就要1.7e10次运算，连一次都跑不动。所以必须使用快速变换。

这里其实还有其他路，比如把状态转移看成循环矩阵，然后做矩阵快速幂。但循环矩阵乘法本质还是卷积，你仍然需要NTT或者FWT。因为本题的合并运算是异或，而不是模加法，所以FFT/NTT那一套行不通，得用FWT。

2. FWT原理与前置知识

2.1 异或卷积的定义

先明确一下异或卷积的定义。给定两个长度都为n=2^m的数组a和b，异或卷积的结果c定义为：

c[k] = Σ_{i xor j = k} a[i] * b[j]

如果直接用双重循环，复杂度O(n^2)。但别忘了，i xor j = k这个条件在二进制下是按位独立决定的，所以存在快速算法。它和普通卷积的区别只在于“合并规则”：普通卷积是i+j=k，这里是i xor j=k。

这里可以打个比方。假设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搞混，这里做一个对比表方便参考。

选型依据只有一个：题目里的“合并运算”到底是什么。如果是加法，用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再取模，否则出来负数，大数据直接错。

注意：如果想验证模板，可以拿n=4的随机数组，先正变换再逆变换，看是否还原。如果输出是全0或全变成n倍，基本能锁定是变换或除法的问题。

3.3 快速幂与整体流程

有了模板之后，主流程非常短：

int main() { int n, m, K; scanf("%d%d%d", &n, &m, &K); int N = 1 << m; vector<ll> 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 几个容易忽略的边界

第一个是K=0。从语义上讲，一次都不训练，答案应该就是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 << m，vector内存没问题；但读入别用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)。

本题做了两次FWT（f和g）、一次IFWT（f），加上O(n log K)的逐点快速幂。总复杂度：

O(n log n + n log K + n log n) = O(n (m + log K))

以m=17为例：n = 131072，n log n约2.2e6，n log K约3.9e6（K到1e9），合计约6e6次运算，C++轻松跑进1秒。对比暴力卷积一次n^2约1.7e10，K次根本不可行。FWT在这里不是锦上添花，而是唯一出路。

4.2 常数与取模优化

模运算比较贵，可以做几件事：

• 加法合并：u+v最多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手算只需几分钟，能省几小时。以n=4举例，设输入为[a0, a1, a2, a3]，FWT后的四个值分别是：

• a0 + a1 + a2 + a3
• a0 - a1 + a2 - a3
• a0 + a1 - a2 - a3
• a0 - a1 - a2 + a3

用这个公式验证自己的模板，如果输出不对，说明某一层写错了。

5.3 减法取模的坑

很多模板写(u - v + MOD) % MOD，在u-v为正时多一次无用模运算，不影响正确性。但如果偷懒写(u - v) % MOD，u-v为负时结果是负数，后面累加直接爆炸。我初学犯过一次，后来养成习惯：减法取模一律先加MOD。

5.4 建模阶段的隐藏坑

这道题表面上FWT，真正决定AC的往往是“建模”而不是“变换”。我最开始直接把f和g丢进卷积，样例过不了。后来发现题目要求的是“多重集”上的计数，而f数组只统计了每个值的数量，却没处理元素顺序带来的组合系数。

解决方法：如果一次训练选的c有重复，g累计；如果多重集中相同值的元素会被区分为不同方案，f[x]初始时不能只记数量，要考虑阶乘逆元等组合系数。如果完全不区分元素顺序，f初始值就是普通计数，卷积结果再乘阶乘即可。

换句话说，FWT只是锤子，建模决定你钉的是钉子还是螺丝。我在这题卡了一晚上，最后发现不是FWT的问题，而是把“元素数量”和“方案数”搞混了。

5.5 对拍建议

确保模板无误的方式：写一个暴力异或卷积，在n=4或8的随机数据上对拍。

vector<ll> brute_conv(vector<ll> a, vector<ll> b) { int n = a.size(); vector<ll> 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模板本身是“背下来就能用”级别的，真正值钱的是理解它为什么能把卷积变成点乘。如果你正在准备竞赛，我建议不要急着背代码，先手推一次n=4的Hadamard矩阵乘法，再自己写一遍暴力卷积，最后再上模板。这个过程虽然多花一个小时，但之后遇到任何异或卷积的题目，你都不会再慌。至于这道题，它的建模部分如果读题不仔细，哪怕FWT写得飞起也会被卡住。所以下次看到标签上只写了“FWT”的题，记得多留个心眼：锤子只是工具，能不能钉好钉子，看的是你对题目的理解。