1. 先把这个题放在哪个坐标系里看
不管你是刷题冲省队，还是纯粹想补一下位运算卷积这块短板，看到【LOJ #3073】「2019 集训队互测 Day 2」序列（FWT）这个标题，应该能迅速抓到两个关键信息：这是集训队互测这个“神仙打架”级别的训练里的一道题，它的核心算法标签是 FWT。这意味着题目本身不是单纯让你背个板子套上去就完事，而是要把一个看起来跟卷积没什么关系的问题，一步步“翻译”成卷积形式，再用变换加速，最后还得在细节上反复抠。
说句实在话，FWT（快速沃尔什变换）这一支在竞赛里的地位有点像“万能胶”：它没有 NTT 那么重的常数，也不像多项式全家桶那么难学，但一旦题目里出现按位与、按位或、按位异或、子集枚举这些操作，它就是最顺手的工具。可大部分教学帖只讲“怎么变换怎么逆变换”，很少讲“为什么要往这上面想”。这篇我就以这道「序列」题为载体，把 FWT 从原理到变形到调试细节一次性说透。适合的读者是已经会基础 DP、知道卷积大概怎么回事，但还没形成位运算卷积直觉的选手，也适合想回顾子集卷积这个经典套路的退役选手。
2. 先把卷积这件事说清楚：FWT 到底在算什么
2.1 从多项式乘法到位运算卷积
普通的多项式卷积长这样：
c[k] = Σ a[i] * b[k-i]它的物理意义很直接：两个序列的下标“相加”得到新下标。而位运算卷积就是把“下标相加”换成“下标按位与”、“下标按位或”、“下标按位异或”。在序列题里，经常出现这样一类转移：
f[S] = Σ_{T} g[T] * h[S xor T]如果你在所有子集上暴力枚举，复杂度是 O(3^n) 或者 O(4^n)，n 稍微到 18、20 就完全跑不动。FWT 的核心思想是：不要在原域上一个个做，而是把序列变换到一个新的“频域”里，在频域里做一次点乘，然后再变换回来。这和 FFT 的逻辑一模一样，只是针对位运算自定义了“频域”的规则。
一个容易让人困惑的点是：FFT 里的单位根是和加法循环群对应的，而 FWT 的三种变换分别对应三个不同的群结构。我们不需要把群论学透了才能写代码，但心里得明白一件事：这套变换是“量身定制”的，用什么位运算，就得用对应的变换，不可以混用。
2.2 三种经典卷积的变换与逆变换
先给出最常用的复杂度为 O(2^n n) 的模板逻辑。这里一个很重要的习惯是：不要在每次循环里写len = 1 << i然后i += len，这样容易把边界写错。更好的写法是外层枚举块长len，内层按块跳跃。
对于 OR 卷积，正变换就是高维前缀和：
for (int len = 1; len < lim; len <<= 1) for (int i = 0; i < lim; i += (len << 1)) for (int j = 0; j < len; ++j) f[i + j + len] += f[i + j];逆变换就是高维差分：
for (int len = 1; len < lim; len <<= 1) for (int i = 0; i < lim; i += (len << 1)) for (int j = 0; j < len; ++j) f[i + j + len] -= f[i + j];AND 卷积，正变换是高维后缀和，把加的方向反过来：
for (int len = 1; len < lim; len <<= 1) for (int i = 0; i < lim; i += (len << 1)) for (int j = 0; j < len; ++j) f[i + j] += f[i + j + len];逆变换同理把加改成减。
XOR 卷积稍微特殊一点，它对应的是顺序无关的一个“对称群”，正变换是：
for (int len = 1; len < lim; len <<= 1) for (int i = 0; i < lim; i += (len << 1)) for (int j = 0; j < len; ++j) { int x = f[i + j], y = f[i + j + len]; f[i + j] = x + y; f[i + j + len] = x - y; }逆变换则要先做同样的加减法，最后统一除以lim。为什么最后除以的是lim而不是别的数？可以这样理解：这个变换本质上是 n 维的 Hadamard 变换，做了 n 轮之后每个位置的贡献都叠加了2^n = lim次，所以逆变换需要缩放回来。很多第一次写 XOR 逆变换的人会忘记这步，只在正变换结尾除一个数，结果样例都过不去。
2.3 复杂度为什么是 O(n log n) 级别的
先说结论：FWT 对长度为 2^n 的序列做一次完整正变换的复杂度是 O(2^n n)。注意这里没有 log 的底数，因为每一层处理的总元素数量是 lim，一共有 log2(lim) = n 层。这和 FFT 的 n log n 是同一级别，但常数更小、实现更短。
很多人会口误说“FWT 是 O(n log n)”，严格说不严谨。这里的 n 如果指二进制位数，那么复杂度就是序列长度乘以位数；如果指序列长度，那么复杂度就是长度乘 log 长度。关键在于：位运算卷积的作用对象通常是一个长度为 2^n 的数组，比如把所有子集映射到 0 到 2^n-1 的下标上，所以瓶颈永远是 2^n 而不是 n。
3. 序列这道题怎么把一个“序列”翻译成卷积
3.1 题目的核心转变在哪里
既然是叫「序列」，自然有一个强相关的序列输入。假设题目给出的核心约束是：有一个长度为 2^n 的数组 a，下标对应所有大小为 n 的二进制子集，你需要求另一个数组 b，满足：
b[S] = Σ_{T ⊆ S} a[T] * a[S - T]注意S - T这里不是普通的整数减法，而是集合意义上的差集。也就是说 T 和 S-T 不相交，并且 T ∪ (S-T) = S。这就是著名的子集卷积：两个不相交集合的并。
这个式子如果用最暴力的枚举子集来做，对每个 S 要枚举它的所有子集 T，总复杂度是 O(3^n)。当 n=20 时，3^20 大约是 34 亿，不可能跑完。这时候自然想到 FWT，因为内层枚举子集本质上是一个 OR 卷积的形式，只是还多了一个限制：T 和 S-T 必须不相交。
3.2 子集卷积为什么不能直接 FWT 了事
如果你尝试直接对 a 做 OR 卷积，你会得到：
c[S] = Σ_{i or j = S} a[i] * a[j]这里面 i 和 j 可以重合，也就是说 i 和 j 的并集是 S，但它们不一定满足 |i| + |j| = |S|。一旦 i 和 j 有交集，在“集合差”的语义下就属于“重复取数”，这在原题里是不允许的。
所以你要做的不仅仅是“或卷积”，还要过滤掉所有 i & j ≠ 0 的情况。这里就有个特别经典的观察：如果 i 和 j 不相交，那么 popcount(i) + popcount(j) = popcount(i or j)。反过来说，只要保证两边的“1 的个数”加起来等于结果的“1 的个数”，就天然排除了相交。
于是我们按 popcount 把 a 分成若干层：
A[k][S] = a[S] 当 popcount(S) == k，否则 0然后对每一层分别做 OR 变换，接着在频域里做“分层卷积”，最后只取出结果中 popcount 等于下标层数的值。这就是子集卷积的标准套路。到这一步，题目就从一个不直观的集合运算，变成了一个标准的多项式卷积：每层视为一个多项式系数，在频域上做一次卷积后再映射回原域。
3.3 按 popcount 分层的具体数学表达
把 A 和 B 都按上面的方式展开成一个二维数组FWT_A[k][S]，表示第 k 层变换后的“频域值”。对每个固定的 S，我们得到了两个长度都为 n+1 的序列：
freq_A[0..n], freq_B[0..n]而子集卷积要求的结果 H 的第 k 层是：
H[k][S] = Σ_{i+j=k} FWT_A[i][S] * FWT_B[j][S]也就是说，在每个 S 上做一个普通的多项式乘法，但只需要 k 从 0 到 n 的结果。这一步可以暴力 O(n^2) 做，每个位置都算一遍，总复杂度 O(2^n n^2)。因为 n 通常不会超过 20，所以 400 * 2^20 完全可接受。
最后对每个 H[k] 做一次逆 OR 变换，并且只保留H[popcount(S)][S]作为最终的 b[S]。你会发现，如果某一层 i 对应的 S 的 popcount 不等于 i，它在逆变换后其实是中间产物，不是我们想要的答案。这也是这个套路和普通卷积最大的不同：层数是“硬约束”，不能丢。
4. 代码实现与逐行注释
4.1 FWT 核心模板的工程化写法
竞赛里写 FWT 时，我建议把它封装成一个函数指针风格的模板，这样三种变换可以共用一套代码，也方便在赛场上快速切换。这里给出一个我用下来非常顺手的版本：
using ll = long long; const int MOD = 998244353; void fwt_or(ll f[], int lim, int inv) { for (int len = 1; len < lim; len <<= 1) for (int i = 0; i < lim; i += (len << 1)) for (int j = 0; j < len; ++j) { int u = i + j, v = i + j + len; if (inv == 1) { f[v] += f[u]; if (f[v] >= MOD) f[v] -= MOD; } else { f[v] -= f[u]; if (f[v] < 0) f[v] += MOD; } } }注意这里的inv我只取 1 和 -1，分别代表正变换和逆变换。加减后立即取模，避免中间值长期处于大数状态。OR 变换的逆变换只是换一个方向差分，所以不需要最后额外除以任何东西，这和 XOR 不一样。
4.2 子集卷积的完整实现
在fwt_or的基础上，子集卷积的主流程可以这样写：
const int MAXN = 22; const int MAXM = 1 << MAXN; int n, lim; ll a[MAXN][MAXM], b[MAXN][MAXM]; ll c[MAXN][MAXM]; void subset_conv() { // a 的第 k 层只有 popcount 为 k 的位置有值 for (int k = 0; k <= n; ++k) { fwt_or(a[k], lim, 1); fwt_or(b[k], lim, 1); } for (int S = 0; S < lim; ++S) { for (int i = 0; i <= n; ++i) { if (a[i][S] == 0) continue; for (int j = 0; i + j <= n; ++j) { c[i + j][S] = (c[i + j][S] + a[i][S] * b[j][S]) % MOD; } } } for (int k = 0; k <= n; ++k) fwt_or(c[k], lim, -1); }有些同学可能会对n的范围有疑问：如果 n 稍微大一点，比如 n=21，那么二维数组大小是 22 * 2^21，大概是 4600 万，这个规模在堆上开没问题，但要注意不能在函数内部开栈。我的习惯是开成全局静态数组，并且MAXM直接定到题目上限，省得用动态 vector 时反复扩容损耗时间。
4.3 取模与边界处理的细节
这里有两个很容易让代码过不了样例的细节。
第一个是 a 数组在分层的时候要严格分层。比如：
for (int S = 0; S < lim; ++S) { a[__builtin_popcount(S)][S] = orig[S] % MOD; }这一步漏掉% MOD或者漏掉 popcount 作为层索引，都会导致后面卷积结果完全错乱。
第二个是c数组在逆变换前，可能已经有某些位置的数超过 MOD，虽然每次点乘都取模，但累加过程中加法仍然可能超，所以我在上面的代码里用的是c[i+j][S] = (c[i+j][S] + ...) % MOD，而不是+=。在比赛环境里，如果时间紧也可以用“先累加再统一取模”的写法，但要额外小心多个卷积层相加可能会溢出long long。实话说，为了不给自己制造 bug，我多写一个%并不会慢多少。
5. 实战场景下的常见问题与调试经验
5.1 变换方向写反了，答案全乱
我见过太多人把 OR 的正变换和逆变换写反。一个非常简单的判断方法：正变换是高维前缀和，概念上是从“小区间”加到“大区间”，也就是f[v] += f[u]，其中v比u多一个二进制位。逆变换是高维差分，方向反过来。如果你发现一个测试点输出的数组每个位置都比标准答案大很多，先别怀疑取模，大概率是正逆变换的方向写反了。
另外，三种变换的代码看起来高度相似，很多人会把 OR 和 AND 搞混。OR 的合并方向是“高位索引吸收低位索引”，AND 则相反。我在写板子时会在文件头部用注释明确标注每一段是哪个变换，防止现场脑袋发懵。
5.2 XOR 逆变换忘记除以 lim
刚才说了 XOR 正变换没有缩放，逆变换必须除以 lim。在模意义下这个“除法”就是乘以 lim 的逆元。常见错误是只在正变换结尾统一除了一次，或者把正逆变换搞成同一个函数。如果你用的是我的模板，XOR 需要单独写一个fwt_xor，并在逆变换时对每个元素都乘上inv_lim。有一个自查技巧：让输入 a 只有一个位置有值 1，做一遍正变换再逆变换，得到的结果必须还是只有那个位置是 1。如果结果每个位置都有值，那多半是缩放因子没处理好。
5.3 子集卷积的“层”没对齐
子集卷积调试时，最典型的症状是：小数据暴力验证没问题，一旦 n 到 15 以上，输出的某些位置比预期大。这通常是分层卷积时没有判断i + j <= n。当i + j > n时，即使频域上计算出来有值，它对应的实际集合大小也超过了可能的最大值，应该直接被丢弃。我写循环时喜欢把条件写成for (int j = 0; i + j <= n; ++j)，而不是for (int j = 0; j <= n; ++j)再在循环体里判断，因为前者可以减少无效计算，也让逻辑更清楚。
还有一个教训：如果原题给的数组下标范围不是从 0 到 2^n-1，而是从 1 开始，那么要先映射到 0 基下标，并且保证高位补零。常见错误是直接用 1 到 2^n 枚举，导致最高位的二进制位被当成上一层的数据，最终卷积结果整体错位。这种错位很难一眼看出来，因为小数据样例往往刚好避开边界。
5.4 内存和常数的隐性瓶颈
子集卷积的空间复杂度是 O(n 2^n)。当 n = 22 时，三层数组a[k][S]、b[k][S]、c[k][S]加起来大概是 3 * 23 * 4MB ≈ 276MB，有些 OJ 会卡在这个内存边缘。这时候有两个办法：一是复用数组，先算完最后一层再覆盖；二是用vector<array<ll,...>>配合动态维度，但不要每个元素都开long long的二维扁平数组，因为这样容易造成 cache miss，常数极大。
关于 cache miss，我想多说一句：FWT 的循环是天然便于局部性访问的，因为你按块长跳，访问的地址都相对连续。但子集卷积里第二维是 2^n 个位置，你需要在每个位置上做 n^2 的多项式卷积，于是“外层遍历 S、内层遍历层数”的顺序就非常重要。如果你写成外层枚举层数，内层枚举 S，那么你会在一个 S 上反复跳转，cache 命中率很差。我实测过同样数据，交换两层循环之后能快接近 30%，这在赛场上可能就是卡常与非卡常的区别。
5.5 对拍是救命的
无论你对自己的思路多有信心，位运算卷积和子集卷积这类题的“翻译式”写法都非常容易埋 bug。我的习惯是写一个暴力O(3^n)的枚举版本，然后随机生成 n 不超过 8 的小数据对拍。这里有个细节：暴力的枚举子集可以直接用for (int T = S; T; T = (T-1) & S)，但别忘了T = 0时集合为空，需要单独处理。对拍脚本只要输出第一个不一致的下标，就能很快定位是第几层出了问题。没有对拍直接交题，纯属赌运气。
6. 这类题还能怎么玩：扩展与变体
6.1 从子集卷积到集合幂级数
子集卷积其实只是集合幂级数的一个基础操作。当你学会了按 popcount 分层这个手法，很多看似复杂的“背包带子集转移”的 DP 题都能套进去。比如有一类题是：有若干物品，每个物品有代价和收益，要求选出来的物品集合 S 的总代价不超过限制，问你最大收益是多少。如果物品之间有“选了 i 就不能选 j”之类的交集冲突，转移时就需要做子集卷积。本质套路是相同的：用层数约束交集，用 FWT 或 FMT 加速“并集合并”。
6.2 与多项式插值、生成函数的结合
某些题目里，你需要对一个序列求幂，比如计算 f^t（子集卷积意义下的幂），如果 t 很大，可以将每层的频域当作多项式系数，在外部做多项式快速幂，最后再逆变换回来。这在实际比赛中见过不止一次。那时候你会发现，分层之后的结构其实是 n+1 维的“多项式乘多项式”，与普通的多项式操作没有本质区别。这也是为什么我建议把 FWT 和多项式基础放在一起学，它们互相成就。
6.3 练习路径建议
如果你现在还不是特别熟，我给的路线是：先刷三道裸题，分别验证 OR、AND、XOR 三种变换的正逆是否正确。然后手写一遍暴力对拍，把子集卷积这个套路彻底跑熟。等这两个阶段过了，再去看那些把 FWT 藏在 DP 转移里的难题。不要一上来就啃“集训队互测”这个级别的题，容易被打退。
7. 写在最后的一点私人体会
我最早学 FWT 的时候也很痛苦，觉得它就像一个从天而降的盒子，你只需要往里丢数组，然后再取出来。直到后来做了一道类似「序列」的题，我才意识到它其实是一套非常优美的“高维前缀和 + 高维差分”的组合。保持这个视角之后，很多题目就不再是一堆孤立技巧的堆砌，而是统一在同一个数学结构下面。
多说一句，赛场上如果时间紧张，不要硬刚自创优化，先把标准板子写对，再考虑常数优化。我吃过太多次“优化过度、WA 到心态爆炸”的亏了。FWT 的代码本来就不长，多花十分钟写个对拍，比反复猜测哪一行出问题要划算得多。希望这篇内容能把 FWT 和子集卷积这层窗户纸帮你捅破，剩下的就是多练、多对拍、多总结，熟练之后你会发现，这些题的解法其实就藏在“分层 + 变换 + 再分层”三个词里。
