企业官网建设流程全解析

昨天在整理旧题单的时候又翻到了这道题，顺手把当时的笔记重写了一遍。提到“2019集训队互测 Day 2”这个标签，很多人第一反应是：互测题，肯定难到劝退。但实际做完会发现，这题真正卡人的不是思维有多绕，而是能不能在一堆位运算限制里认出“卷积”的结构，然后果断掏出 FWT（快速沃尔什变换）来压复杂度。这道题的题目名就叫“序列”，题面非常干净，专治那些只会套板子、不理解 FWT 到底在干嘛的选手。

这篇文章适合已经会一点 DP、想看 FWT 怎么在真实计数题里下场的读者。我会从题面还原开始，把暴力 DP 怎么挂的讲清楚，再一步步推出 FWT 的变换规则，最后给出完整实现思路和踩坑记录。你不需要提前熟背 FWT 模板，跟着走一遍，以后看到“位运算限制 + 序列计数”的组合，就知道该往哪个方向想。

1. 从题面到模型：这题到底让 FWT 来干什么

1.1 题面还原

原题并不长，大意是这样的：有一个长度为 n 的序列，每一个元素 a_i 都是从 [0, 2^m - 1] 这个值域里选的整数。现在给出 q 组限制，每组限制形如：

• a_u ⊕ a_v = c，即某两个位置的异或值必须等于给定常数；
• 或者要求整个序列满足：所有数按位与的结果在某个集合 S 内，所有数按位或的结果在另一个集合 T 内；
• 最后统计满足全部条件的序列个数。

n 和 q 都可以很大，但 m 一般不会超过 17 或者 18，也就是说值域 2^m 是我们可以承受的“状态空间”。数据范围一摆出来，思路其实就清晰了：值域小、序列长、限制全是位运算关系，这种题十有八九要把每个位置的取值情况编码成多项式，然后用位运算卷积把多个“来源”合并起来。

先别急着写代码，我们得先回答一个问题：FWT 在这道题里到底承担了什么角色？答案是它承担“合并”的角色。你有一个位置的取值集合，另一个位置也有自己的取值集合，当你想知道合并后异或和等于多少的方案数时，这不就是异或卷积吗？所有限制都只是在这个卷积结果上做筛选。

1.2 为什么答案是若干多项式的卷积

我们把每个位置 i 看成一个多项式 P_i(x)，其中 x 的指数表示这个位置的取值，系数表示取到这个值的方案数。如果第 i 个位置能取的值是集合 S_i，那么：

• 当 v ∈ S_i 时，P_i 中指数为 v 的系数为 1；
• 当 v ∉ S_i 时，系数为 0。

现在假设只有两个位置，它们的异或和等于 k 的方案数怎么算？枚举第一个位置取 x，第二个位置取 y，要求 x ⊕ y = k，那么贡献就是 P_1 中 x 的系数乘 P_2 中 y 的系数，再累加到指数 k 上。这就是典型的：

C[k] = Σ_{x ⊕ y = k} A[x] · B[y]

这个式子，数学上就叫异或卷积。你把所有 P_i 不停地做异或卷积，最终得到的长度为 2^m 的数组里，下标 k 就代表整个序列异或和为 k 的方案数。

同理，如果限制是按位与为某个值，那就是与卷积；按位或为某个值，就是或卷积。三个卷积长得像一家人，只是运算符号从 ⊕ 换成了 & 和 |。暴力计算两个长度 2^m 数组的异或卷积是 O(4^m)，m=17 的时候 4^17 ≈ 1.7×10^10，直接原地爆炸。FWT 的存在，就是把这个复杂度变成 O(m·2^m)，本质思路和 FFT 让多项式乘法从 O(n^2) 降到 O(n log n) 完全一致——先在变换域里点乘，再逆变换回来。

2. 三种位运算卷积：一张表理清 FWT 的全部套路

2.1 目标和变换的定义

FFT 能加速卷积，靠的是把时域信号变换到频域，让卷积变成点乘。FWT 干的也是同一件事：我们要找一个线性变换 T，使得对于任意数组 A 和 B，都有：

T(C)[x] = T(A)[x] · T(B)[x]

其中 C 是 A 和 B 的某种位运算卷积结果。只要能构造出这样的 T，那么“卷积”就能分三步走：先分别变换 A 和 B，然后逐点相乘，最后逆变换回去。

那么 T 长什么样？这就要按运算类型分别推导了。你不需要从零发明这些变换，但至少要知道它们为什么成立，否则考场上稍微变形就认不出来。

2.2 OR、AND、XOR 三套变换规则

先说或卷积。定义：

C[k] = Σ_{i | j = k} A[i] · B[j]

构造变换 T_OR(A)[x] = Σ_{i ⊆ x} A[i]，也就是对下标做子集和。为什么这样能行？因为当 i | j ⊆ x 时，等价于 i ⊆ x 且 j ⊆ x。于是：

T_OR(C)[x] = Σ_{k ⊆ x} C[k] = Σ_{k ⊆ x} Σ_{i | j = k} A[i]·B[j] = Σ_{i ⊆ x} Σ_{j ⊆ x} A[i]·B[j] = T_OR(A)[x] · T_OR(B)[x]

完美吻合。所以或卷积的 FWT 就是“子集和”，逆变换是“子集差分”。

再说与卷积。定义：

C[k] = Σ_{i & j = k} A[i] · B[j]

构造变换 T_AND(A)[x] = Σ_{i ⊇ x} A[i]，也就是超集和。理由完全对称：i & j ⊇ x 等价于 i ⊇ x 且 j ⊇ x。所以：

T_AND(C)[x] = T_AND(A)[x] · T_AND(B)[x]

与卷积的 FWT 是“超集和”，逆变换是“超集差分”。

最后是异或卷积，也是最常考的。定义：

C[k] = Σ_{i ⊕ j = k} A[i] · B[j]

变换要复杂一点。取：

T_XOR(A)[x] = Σ_{i} (-1)^{popcount(i & x)} · A[i]

这里 popcount 是二进制里 1 的个数。验证也很漂亮：因为 (i ⊕ j) & x 的 1 的奇偶性，等于 i & x 和 j & x 的 1 的奇偶性之和的奇偶性，所以有：

(-1)^{popcount((i⊕j)&x)} = (-1)^{popcount(i&x)} · (-1)^{popcount(j&x)}

代入卷积定义，两边拆开就得到点乘关系。异或卷积的核心就是带上正负号求和。

我把三条规则整理成一个表，方便对照：

2.3 逆变换的系数学问

初学者最容易在这里栽跟头：或卷积和与卷积的逆变换是纯差分，不需要乘任何系数；但异或卷积的逆变换需要再执行一次同样的正负变换，然后整体除以 2^m。原因是异或变换矩阵 H 满足 H·H = 2^m·I，也就是说自己做两次等于乘了一个 2^m。

所以写异或 FWT 时，逆变换千万不要忘了最后的除法。模意义下就是乘 2^m 的逆元。或卷积、与卷积做逆变换时别画蛇添足去乘逆元，一乘答案就错了。我见过不下五个选手在同一题上因为这个挂了，后面第五部分还会细说。

3. 板子的分工：OR、AND、XOR 的代码为什么长得不一样

3.1 分治合并的顺序

FWT 的实现靠的是分治，长度必须补成 2 的幂。以或卷积为例，变换 T_OR 求子集和，可以这样想：先把所有下标按最高位分成两半，前半部分最高位是 0，后半部分是 1。子集和的贡献分两类：

• 只来自前半部分的贡献；
• 来自后半部分、但“去掉最高位后”对应前半部分某个下标的贡献。

所以每一层合并时，只需要做一次对应区间的加法：把a[i+j]累加到a[i+j+len]上。从最高位到最低位做 len=1,2,4,… 的倍增合并，一次变换就完成了。

与卷积是超集和，方向反过来，每一层把 a[i+j+len] 累加到 a[i+j] 上。异或卷积是正负号的蝴蝶变换，每一层把区间拆成两半，对每个对应位置计算 x+y 和 x-y。代码结构其实就是个三重循环：外层枚举块长度，中层枚举块起点，内层枚举块内位置。只要你理解了每一层在做“把两块信息合并成一块”，模板背起来就顺理成章了。

3.2 代码模板

现在给出我常用的一组模板。为了通用，我封装成函数的形式，type=1 表示正变换，type=-1 表示逆变换，全程在模 MOD 下运行。

以或卷积为例：

void fwt_or(vector<int>& a, int type) { int n = (int)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++) { if (type == 1) { a[i + j + len] = (a[i + j + len] + a[i + j]) % MOD; } else { a[i + j + len] = (a[i + j + len] - a[i + j] + MOD) % MOD; } } } } }

与卷积模板：

void fwt_and(vector<int>& a, int type) { int n = (int)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++) { if (type == 1) { a[i + j] = (a[i + j] + a[i + j + len]) % MOD; } else { a[i + j] = (a[i + j] - a[i + j + len] + MOD) % MOD; } } } } }

异或卷积模板：

void fwt_xor(vector<int>& a, int type) { int n = (int)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++) { int x = a[i + j]; int y = a[i + j + len]; a[i + j] = (x + y) % MOD; a[i + j + len] = (x - y + MOD) % MOD; } } } if (type == -1) { int invn = mod_inv(n); for (int i = 0; i < n; i++) { a[i] = (int)(1LL * a[i] * invn % MOD); } } }

三个模板的核心差别就在于内层循环里两个元素是“谁加谁”以及“正号还是负号”。你不需要死记硬背，只需要在脑子里想清楚当前这一层在合并哪一位的信息。比如或卷积，下标 i+j 的二进制最高位是 0，i+j+len 的最高位是 1，子集和中，“高位为1”的子集可以来自“高位为0”的子集，所以后者累加前者。

3.3 对拍：验证模板的最快方式

模板写完别急着直接用到题目里，先写个暴力对拍函数验证正确性。比如验证或卷积：

vector<int> brute_or(const vector<int>& A, const vector<int>& B) { int n = (int)A.size(); vector<int> C(n, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { C[i | j] = (C[i | j] + (int)(1LL * A[i] * B[j] % MOD)) % MOD; } } return C; }

再用随机生成的 A、B 跑一遍 fwt，比对结果。另外还有一个非常廉价但有效的自测：构造 B 为只有下标 0 是 1、其余全是 0 的数组，任何卷积做完都应该等于 A 本身。如果逆变换后不是 A，说明除 n 那一步有问题。这个小实验快得惊人，我每次换平台或者换模数之后都会先跑一遍，能挡住九成以上的低级错误。

4. 回到原题：怎么把多个限制打包成一次点乘

4.1 从单一异或和为零开始

现在回到“序列”这道题。最简单的情况：每个位置 i 给定可取值集合 S_i，求整个序列异或和为 0 的方案数。

这一步只要把每个位置的指示多项式 P_i 都做一遍 FWT_XOR，然后逐点相乘，最后逆变换回来，取下标 0 的系数就是答案。为什么可以这样做？因为异或卷积的变换满足：

FWT(A⊗B) = FWT(A) · FWT(B)

这里的乘法是逐点相乘。多个多项式连续卷积，就是各自变换之后逐点乘起来，最后逆变换一次。这样做的好处是：多个位置的合并复杂度不是乘法叠加，而是加法叠加。假设有 n 个位置，每个位置的多项式长度都是 2^m：

• 暴力做 n-1 次卷积，每次 O(m·2^m)，总共 O(n·m·2^m)；
• 先各自变换再点乘，FWT 要做 n 次（或者可以合在一起做矩阵批量变换），每次 O(m·2^m)，点乘 O(n·2^m)，同样的复杂度量级，但常数更小。

在这个模型里，若每个位置的取值集合大小不大，构造指示多项式只需要 O(Σ|S_i|)，整体完全可以跑进时限。如果某个位置的取值集合是一个完整区间，甚至可以直接用前缀和快速构造出它变换后的结果，连枚举都不用。

4.2 AND/OR 限制：用第二层 FWT 做容斥

原题还有按位与、按位或的全局限制，这才是互测题的“互测”味道。如果直接枚举最终 AND 结果和 OR 结果，状态数是 2^m × 2^m，指数级爆炸。这里需要把 AND 和 OR 的约束转换成另一种卷积上的筛选。

套路是：按位或的结果必须满足某些位为 0，等价于“所有数的这些位都是 0”，所以可以直接把这些位从值域里抠掉。按位或的结果必须满足某些位为 1，就需要容斥了——枚举哪些位没有被任何数覆盖，这就是一个子集容斥。按位与的条件同理，要求某些位为 1，等价于“每个数在这些位都为 1”，可以先行与一个“强制 mask”再进入后续过程。

具体到实现，可以把整道题拆成“预处理每个位置的取值集合受限后的指示多项式”，对它做 FWT_AND、FWT_OR 以及 FWT_XOR 中的一种，然后把三者要求的筛选结果在变换域里直接合并。因为 FWT 是线性变换，多个约束的“同时满足”在变换域里并不会破坏点乘结构——至少在同一种卷积下不会。混用三种卷积时，需要先想清楚限制是加在哪一层，再做一次变换复合。

这里我给一个通用经验：当题目里同时出现多种位运算限制，优先考虑把能合并的合并掉，比如某一位必须全为 0，就直接从所有集合中删除这个位；某一位必须全为 1，就先把这个位从所有取值中“固定”为 1，再在方案数最后乘上必要的倍数。剩下的无法直接压缩的限制，再用对应卷积的容斥来解决。这道题的主流做法正是把 AND、OR 限制通过若干次容斥化成若干个纯 XOR 限制，然后用同一套 FWT 批量处理。

4.3 复杂度与优化思路

整体复杂度大概是这样：长度 L=2^m，总位置数 n，限制组数 q。预处理位置多项式 O(Σ|S_i|)，FWT 部分 O((n + q)·m·L)，点乘部分 O(n·L)，逆变换 O(m·L)。m=17 时 L=131072，m·L≈2.2×10^6，乘上几千个位置也就是亿级运算，在竞赛环境下如果常数优化到位是可以接受的。

几位选手卡常的方法是：

• 用 int 数组而不是 vector 嵌套，缓存友好；
• 把 n 个位置的多项式并排存成二维数组，按列做变换，避免多次函数调用开销；
• 点乘时用循环展开，或者直接乘完就放到下一个矩阵里；
• 模数用常见的 1e9+7，只要逆元提前算好，除法只在最后逆变换时出现一次。

5. 做这类题最容易翻车的三个地方

5.1 逆变换除 n 的时机

异或卷积逆变换需要除以长度 L，这一点前面强调过。但实践中翻车的方式往往不是“忘了除”，而是“除多了”。比如你在中间某一步做了一次 FWT 又立刻逆变换，结果没注意那个 inverse，后面又做了一次逆变换，最后答案全部乘上了 L 的幂次。更隐蔽的是：对多个多项式连续做异或卷积时，有人习惯每乘完一个就逆变换一次，导致要么除多了要么除少了。

我的建议是：在连续合并的整个大过程中，不要做任何中间逆变换。所有多项式先各自 FWT，逐点乘完，最后统一逆变换一次。中间需要看某个中间状态的系数时，单独开一个副本验证即可，不要污染主流程。

5.2 点乘顺序与多卷积混合

如果一道题里同时用了 OR、AND、XOR，那就必须非常小心变换域的“兼容性”。请记住：点乘只能在同一种变换域里进行。你不能把一个 FWT_OR 的结果和一个 FWT_XOR 的结果逐点相乘，那是数学上没定义的操作。跨卷积类型的合并，必须回到原数组域（时域）再重新变换。

我在实际做题中养成了一个习惯：每一次变换之后，在注释里标明当前数组处于“时域”还是“OR 频域”“XOR 频域”。进入频域就只做点乘，离开频域就只做逆变换。这样代码虽然多了几行注释，但能省下几个小时的对拍时间。

5.3 模运算与常数优化

模运算的坑主要出现在异或变换的减法：x - y 可能是负数，必须先加 MOD 再取模。加法也要警惕溢出，两个 int 加起来的最大值可能接近 2×MOD，所以需要在每次加法后立刻取模。另一个常见问题是逆元计算：n 是 2 的幂，在模数是质数时逆元可以直接用快速幂算，但如果你使用 C++ 的 vector，注意 mod_inv(n) 的函数参数类型是 int，而 n 可能超过 2^16 但不会超过 int 范围，不要写错成 1LL 传给函数导致类型转换问题。

卡常方面，我能分享的经验是：不要让内层循环里出现取模运算的随机跳转，尽量在累加后才取模，或者用 if (x >= MOD) x -= MOD 这样的小技巧。对于 or/and 这种纯加法变换，可以用一个add函数做优化内联；异或变换里两个值的和与差要用临时变量保存。这些优化看起来琐碎，但在 n=17、要批量处理几千个数组的时候就非常关键。

6. 怎么识别将来会遇到的同类题

6.1 题面特征清单

做完这道题之后，我总结出这类“位运算卷积计数题”的常见特征。你下次看到题面，可以快速对照一下：

• 序列/集合的每个元素来自一个较大的值域 [0, 2^m-1]，m 通常不超过 20；
• 题目给出的限制是“两个位置异或等于什么”“所有值的与必须满足什么”“或必须满足什么”这类描述；
• 要求的是方案数、概率或期望，而不是具体的构造；
• n 很大，但 2^m 在可处理范围内，甚至 m 比 n 小很多。

满足三条以上，基本就可以往 FWT 方向想。但要注意，集训队互测的题往往不会直接给你一个裸卷积，它会在进入 FWT 之前先让你做一层建模，可能是带权并查集，可能是容斥，也可能是生成函数变形。

6.2 临场的做题流程

我的临场流程是这样的：

1. 先写一个最暴力的 DP，哪怕 O(n·4^m)，只要它能算小数据，就能当对拍基准。
2. 观察暴力 DP 的状态转移，尝试把转移整理成“两个数组做位运算卷积”的形式。
3. 判断是哪一种卷积：异或、按位与、还是按位或。如果是多种混合，先尝试用容斥统一成同一种。
4. 套 FWT 优化卷积部分，保持其余 DP 层不变。
5. 写一个随机数据生成器，暴力结果和 FWT 结果对拍。

这个流程看起来常规，但能避免最典型的错误：一上来就对着模板背，结果不知道要变换哪些数组、点乘哪些位置，写了半天对拍都过不了。先暴力，再卷积化，最后套模板，每一步都有明确验证物，查错会容易得多。

6.3 复盘：我在这道题上的教训

最后说点个人体会。第一次做这道题的时候，我犯了一个非常典型的错误：我把所有位置的集合都做了 FWT，然后点乘，然后马上逆变换，再把它作为新的“位置集合”参与下一层限制的处理。结果答案怎么对都不对，对拍挂了一百组数据。后来才反应过来，我过早逆变换导致整个变换域结构被破坏，后续的容斥全在时域里做，等于 FWT 白用了。

正确的做法是：约束筛选尽量留在频域里做，只有在必须切换卷积类型时才回到时域。这道题让我把 FWT 从“背模板”提升到了“理解变换域”的程度。从那以后，我再也没有搞混过三种卷积的逆变换、没有漏过异或逆变换的除法。说实话，如果你也准备往竞赛这条路走一段，这道题是绕不开的磨刀石，磨的正是“从公式到代码”的那道坎。把最常见的三个坑（逆变换时机、跨卷积操作、模运算细节）都踩一遍再爬出来，以后再看到位运算计数题就不会发怵了。