1. 为什么FWT不是“另一个卷积加速器”，而是离散域上的坐标系革命
你翻过《算法导论》的FFT章节，也调过PyTorch里的torch.nn.Conv2d，甚至能手写一个3×3卷积核滑窗——但当你第一次在Codeforces某道题解里看到“FWT异或卷积O(n log n)”时，大概率会愣住：卷积还能这么玩？它和CNN里那个“卷积”到底是不是同一种东西？答案是：根本不是。它们共享“卷积”这个词，就像“苹果手机”和“苹果水果”共享“苹果”——只是中文巧合。真正让FWT值得被称作“详详详解”的，不是它快，而是它彻底重构了我们看待布尔函数、子集求和、状态转移的方式。
FWT的本质，不是优化计算，而是坐标系切换。想象你在三维空间里算两个向量的点积：直接算x₁x₂ + y₁y₂ + z₁z₂很慢；但如果先把它们旋转到一组正交基（比如主轴方向）上，变成(1,0,0)和(0,1,0)，点积瞬间为0——因为新坐标系下运算被“对角化”了。FWT干的就是这事：它把定义在{0,1}ⁿ超立方体上的函数，从“标准基”（每个点独立取值）切换到“沃尔什基”（每个基函数是特定模式的奇偶校验），让原本O(2²ⁿ)的异或卷积，退化成2ⁿ个独立乘法。这不是算法技巧，是线性代数在离散域的降维打击。
这解释了为什么所有热词里混着“图卷积”“球面卷积”“空洞卷积”——它们全在连续或几何空间里折腾核函数形状；而FWT只关心“位”与“位”的逻辑关系。你用CNN处理一张猫图，像素间有空间邻接；但FWT处理的是一个长为2ⁿ的数组，索引i和j的二进制表示之间，只存在“异或”“或”“与”三种位运算关系。没有距离，没有方向，只有比特面具下的代数结构。所以别被“卷积”二字带偏：FWT的输入不是图像，是状态压缩后的DP数组；它的输出不是特征图，是满足某种位约束的计数总和。
我第一次在NOI模拟赛里用FWT解“子集异或和为k的方案数”时，写的暴力是三层for循环枚举a,b,c，时间复杂度O(8ⁿ)。交上去TLE到连错误提示都刷不出来。改成FWT后，核心代码就三行：fwt(a); fwt(b); for i: c[i]=a[i]*b[i]; ifwt(c)。运行时间从10秒压到0.03秒。那一刻我才懂：FWT不是让你“更快地做同一件事”，而是让你根本不用再做那件事——它把“枚举所有子集对”这个动作，从算法层面直接抹掉了。
提示：FWT的“快”是假象。真正快的是它背后隐藏的线性变换可逆性。只要变换矩阵U满足U⁻¹存在且易算（沃尔什矩阵就是自逆的，只差个缩放因子），那么任何在U基下可分离的运算，都能借U/U⁻¹完成“换坐标→简单运算→换回来”三步走。这才是它能通吃异或/或/与卷积的底层逻辑。
2. 沃尔什基：不是凭空造出来的，而是从真值表里长出来的
教科书常把沃尔什矩阵写成Hadamard矩阵的变体，列成一大张±1表格，然后说“记住这个变换就行”。这等于告诉你“DNA双螺旋很漂亮”，却不讲碱基配对怎么决定遗传。FWT的基函数，必须从布尔函数的真值表里亲手推出来，否则永远只能当黑盒调用。
我们从最简单的n=1开始。定义域是{0,1}，函数f(0), f(1)。想构造一组正交基φ₀(x), φ₁(x)，使得任意f(x)都能写成f(x) = a₀φ₀(x) + a₁φ₁(x)。正交要求：∑ₓ φᵢ(x)φⱼ(x) = 0 (i≠j)。试几个组合：
- 若φ₀(x)=1（常函数），φ₁(x)=(-1)ˣ（即x=0时为1，x=1时为-1），则∑ₓ φ₀φ₁ = 1·1 + 1·(-1) = 0，正交！
- 再验证完备性：解方程组 f(0)=a₀·1 + a₁·1, f(1)=a₀·1 + a₁·(-1)，得a₀=(f(0)+f(1))/2, a₁=(f(0)-f(1))/2。完美。
这个φ₁(x)=(-1)ˣ，就是n=1的沃尔什基。它物理意义是什么？是奇偶校验：当x=0（偶数个1），输出+1；x=1（奇数个1），输出-1。推广到n位：φₛ(x) = (-1)^{s·x}，其中s·x是s和x的按位与再求和（即汉明权重模2）。例如n=2，s=01（二进制），x=11，则s·x = 0·1 + 1·1 = 1，φₛ(x) = (-1)¹ = -1。
现在看n=2的完整沃尔什矩阵W₂。行索引s（00,01,10,11），列索引x（00,01,10,11）：
| s\x | 00 | 01 | 10 | 11 |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | 1 |
| 01 | 1 | -1 | 1 | -1 |
| 10 | 1 | 1 | -1 | -1 |
| 11 | 1 | -1 | -1 | 1 |
发现规律了吗？W₂ = W₁ ⊗ W₁（Kronecker积）。W₁是[[1,1],[1,-1]]，W₂就是它和自己的张量积。这就是FWT分治的基础：Wₙ = W₁^{⊗n}。所以FWT算法本质是n层蝶形运算，每层处理一对bit，和FFT一模一样——只是FFT的旋转因子e^{2πik/n}换成±1。
实操中，我们不存整个矩阵。对数组A做FWT，就是递归地：
- 把A按最高位拆成A₀（最高位0）、A₁（最高位1）
- 递归计算FWT(A₀), FWT(A₁)
- 合并：B₀ = FWT(A₀) + FWT(A₁), B₁ = FWT(A₀) - FWT(A₁)
这就是“蝴蝶操作”。n=3时，总共log₂(8)=3层，每层8次加减，总操作数24次，远低于朴素O(2⁶)=64次。
注意：这里合并公式B₀=A₀+A₁, B₁=A₀-A₁，对应的是异或卷积的FWT。但“或卷积”和“与卷积”的基函数完全不同！或卷积用的是zeta变换：φₛ(x)= [s⊆x]（s是x的子集），矩阵是下三角的；与卷积用的是莫比乌斯变换：φₛ(x)= [s⊇x]（s包含x），矩阵是上三角的。它们不能共用同一套蝶形代码——这是90%初学者栽跟头的地方。
3. 异或卷积：为什么“a⊕b=c”能变成“FWT(a)[i] × FWT(b)[i] = FWT(c)[i]”
异或卷积定义为c[k] = ∑_{i⊕j=k} a[i] × b[j]。朴素实现要枚举所有i,j，O(2²ⁿ)。FWT把它变成逐点乘法，关键在于沃尔什基的卷积定理：若c = a * b（*表示异或卷积），则FWT(c) = FWT(a) ⊙ FWT(b)，其中⊙是逐元素乘法。
证明它，只需验证基函数的性质：φₛ(i⊕j) = φₛ(i) × φₛ(j)。因为φₛ(x) = (-1)^{s·x}，所以φₛ(i⊕j) = (-1)^{s·(i⊕j)}。而s·(i⊕j) = ∑ₖ sₖ·(iₖ⊕jₖ)。注意在GF(2)上，iₖ⊕jₖ = iₖ + jₖ - 2iₖjₖ，但模2后-2iₖjₖ=0，所以iₖ⊕jₖ ≡ iₖ + jₖ (mod 2)。因此s·(i⊕j) ≡ ∑ₖ sₖ(iₖ+jₖ) ≡ s·i + s·j (mod 2)。于是(-1)^{s·(i⊕j)} = (-1)^{s·i + s·j} = (-1)^{s·i} × (-1)^{s·j} = φₛ(i)φₛ(j)。证毕。
这个等式意味着：在沃尔什基下，异或卷积运算被“对角化”了。每个频率分量s只和自己耦合，不串扰。所以FWT(a)的第s项，就是a在φₛ方向上的投影强度；乘起来，就是c在φₛ方向上的投影强度。
举个n=2实例。设a=[1,2,3,4]（索引00,01,10,11），b=[1,0,0,1]。手动算c[00] = a[00]b[00] + a[01]b[01] + a[10]b[10] + a[11]b[11] = 1×1 + 2×0 + 3×0 + 4×1 = 5。但用FWT：
- FWT(a) = [10, -2, -2, -2]（计算过程：先分[1,2]/[3,4]→[3, -1]/[7, -1]→[10, -2, -2, -2]）
- FWT(b) = [2, 0, 0, 2]（b=[1,0,0,1]，FWT后[2,0,0,2]）
- 逐点乘：[20, 0, 0, -4]
- IFWT：先[20,0]/[0,-4]→[20,20]/[4,-4]→[24,16,16,8]，再除4得c=[6,4,4,2]？等等，不对！
发现问题没？IFWT需要除以2ⁿ。上面IFWT结果[24,16,16,8]是未归一化的，除4得[6,4,4,2]。但之前手动算c[00]=5。矛盾在哪？——我漏了c[00]的完整定义：c[k] = ∑_{i⊕j=k} a[i]b[j]。k=00时，i⊕j=00即i=j，所以c[00]=a[00]b[00]+a[01]b[01]+a[10]b[10]+a[11]b[11]=1×1+2×0+3×0+4×1=5。但FWT给出c[00]=6。错在b的索引理解：b=[1,0,0,1]对应b[00]=1, b[01]=0, b[10]=0, b[11]=1。i⊕j=00的(i,j)对有(00,00),(01,01),(10,10),(11,11)，没错。但FWT计算无误，说明手动算错了？重算：a[00]=1,b[00]=1→1；a[01]=2,b[01]=0→0；a[10]=3,b[10]=0→0；a[11]=4,b[11]=1→4；总和5。FWT结果c=[6,4,4,2]，c[00]=6≠5。哪里出问题？
根源在FWT的归一化约定。不同教材对FWT定义不同：有的FWT不带归一化，IFWT除2ⁿ；有的FWT自带1/√2ⁿ，IFWT同理。上面计算用的是“FWT无归一化，IFWT除2ⁿ”，但验证时忘了FWT(a)的计算是否一致。重新规范：定义FWT(A)[s] = ∑ₓ A[x]·(-1)^{s·x}，则IFWT(A)[x] = (1/2ⁿ)∑ₛ A[s]·(-1)^{s·x}。所以FWT(a)=[10,-2,-2,-2]正确；FWT(b)=[2,0,0,2]正确；乘积[20,0,0,-4]；IFWT：c[00]=(20+0+0-4)/4=16/4=4？还是不对。
算FWT(b)：b=[1,0,0,1]，s=00: (-1)⁰×1 + (-1)⁰×0 + (-1)⁰×0 + (-1)⁰×1 = 2；s=01: (-1)⁰×1 + (-1)¹×0 + (-1)⁰×0 + (-1)¹×1 = 1-1=0；s=10: (-1)⁰×1 + (-1)⁰×0 + (-1)¹×0 + (-1)¹×1 = 1-1=0；s=11: (-1)⁰×1 + (-1)¹×0 + (-1)¹×0 + (-1)⁰×1 = 1+1=2。所以FWT(b)=[2,0,0,2]没错。乘积[20,0,0,-4]。IFWT c[00] = (20×1 + 0×1 + 0×1 + (-4)×1)/4 = 16/4 = 4。但手动是5。问题出在a的索引：a=[1,2,3,4]，若索引是00,01,10,11，则a[00]=1,a[01]=2,a[10]=3,a[11]=4。i⊕j=00的对：(00,00):1×1=1, (01,01):2×0=0, (10,10):3×0=0, (11,11):4×1=4，总和5。但FWT给出4。除非……b[11]不是1？b=[1,0,0,1]，第4个是b[11]=1，没错。
真相是：异或卷积的定义中，索引i,j,k是整数，但运算i⊕j=k在二进制下成立。当n=2，k=00即0，i⊕j=0意味着i=j，没错。但FWT结果c=[4,?, ?, ?]，c[00]=4，说明要么手动计算漏项，要么FWT实现有误。检查FWT(a)：a=[1,2,3,4]
- 第一层（按bit1分）：A₀=[1,2], A₁=[3,4]
- FWT(A₀): [1+2, 1-2] = [3,-1]
- FWT(A₁): [3+4, 3-4] = [7,-1]
- 合并：B₀ = [3+7, -1+(-1)] = [10,-2], B₁ = [3-7, -1-(-1)] = [-4,0]
哦！我之前合并错了。正确是B₀ = A₀+A₁, B₁ = A₀-A₁，所以[3,-1] + [7,-1] = [10,-2]，[3,-1] - [7,-1] = [-4,0]。所以FWT(a)=[10,-2,-4,0]，不是[10,-2,-2,-2]。之前算错了蝶形。修正后：FWT(a)=[10,-2,-4,0]，FWT(b)=[2,0,0,2]，乘积[20,0,0,0]，IFWT c[00]=(20+0+0+0)/4=5。完美匹配。
这个小错误恰恰说明：FWT代码里蝶形运算的符号和顺序极易写反。很多人的FWT模板第一版都WA，就是因为合并时用了A₀-A₁当B₀，或搞混了A₀/A₁的切分方向。我的教训是：写完必须用n=1,2的手动案例验证，宁可多花5分钟，别让TLE浪费1小时。
4. 或卷积与与卷积：不是FWT的变种，而是zeta变换的孪生兄弟
看到“FWT”就默认是异或卷积？大错特错。竞赛题里“子集卷积”“超集求和”“掩码DP”全靠或/与卷积撑腰，而它们和异或卷积的数学基因完全不同——异或卷积基于群表示论（Z₂ⁿ加法群），或/与卷积基于偏序集上的zeta变换（subset lattice）。
先看或卷积：c[k] = ∑_{i∣j=k} a[i] × b[j]，即所有满足i或j等于k的(i,j)对求和。注意是i∣j=k，不是i∣j⊆k。这意味着i和j的并集必须恰好是k，不能少也不能多。例如k=101₂，则i,j只能是000,001,100,101的子集，且i∣j必须=101。这比异或卷积更“稀疏”。
或卷积的变换叫快速zeta变换（FZT）。它的基函数是φₛ(x) = [s⊆x]（艾弗森括号，s是x的子集）。变换矩阵是下三角的：行s，列x，若s⊆x则为1，否则0。例如n=2：
| s\x | 00 | 01 | 10 | 11 |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | 1 |
| 01 | 0 | 1 | 0 | 1 |
| 10 | 0 | 0 | 1 | 1 |
| 11 | 0 | 0 | 0 | 1 |
这个矩阵的逆是莫比乌斯变换：μ(s,x) = (-1)^{|x|-|s|} [s⊆x]。所以zeta变换的正向是求和，逆向是容斥。
FZT算法是经典的“子集求和”：对每个i，枚举i的每一位，若该位为0，则把a[i]加到a[i|bit]上。代码极简：
for(int i = 0; i < (1<<n); i++) for(int j = 0; j < n; j++) if(!(i & (1<<j))) a[i | (1<<j)] += a[i];这就是或卷积的“FWT”。它时间复杂度O(n·2ⁿ)，比异或卷积的O(n·2ⁿ)多一个常数，但思想更直观：从小集合往大集合“推”。
与卷积c[k] = ∑_{i&j=k} a[i] × b[j]，即i和j的交集恰好是k。变换是超集zeta变换：φₛ(x) = [s⊇x]（s包含x）。算法是对每位，若该位为1，则把a[i]加到a[i&~bit]上：
for(int i = 0; i < (1<<n); i++) for(int j = 0; j < n; j++) if(i & (1<<j)) a[i ^ (1<<j)] += a[i];关键区别：或卷积的FZT是向上推（子集→父集），与卷积是向下推（超集→子集）。而异或卷积的FWT是对称蝶形（无方向性）。三者不能混用——曾见有人把或卷积的代码套到异或题上，结果样例都过不了。
实战中，如何选？看DP转移：
- 若状态转移是“选或不选某个元素，新状态是旧状态或上元素mask”，用或卷积（如“覆盖所有点的最小边集”）。
- 若转移是“保留某些元素，新状态是旧状态与上mask”，用与卷积（如“恰好选某些点的方案数”）。
- 若转移是“两状态异或得到新状态”，用异或卷积（如“灯开关问题”“线性基计数”）。
我去年写一个“带限制的子集和”DP，状态dp[mask]表示达成mask的方案数，转移是dp[mask] += dp[mask^sub] × val[sub]。我以为是异或卷积，写了FWT，结果WA。后来发现mask^sub不是“异或”，而是“去掉sub”，即mask & ~sub，这其实是子集卷积（需先做zeta，再逐点乘，再莫比乌斯），比单纯或卷积还多一层。这种坑，只有亲手推过真值表才会避开。
提示：zeta变换的“推”操作，本质是动态规划的拓扑序。或卷积的推序是按popcount升序（0→1→2→...→n），因为小集合影响大集合；与卷积是popcount降序。而异或卷积没有popcount依赖，所以能分治。这是三者算法结构差异的根源。
5. 从理论到AC：一个完整竞赛题的FWT实战拆解
题目：“给定长度为2ⁿ的数组a,b，求c[k] = ∑_{i⊕j=k} a[i] × b[j]，模10⁹+7。n≤20。” 这是FWT裸题，但AC率常低于50%——不是不会，是细节掉链子。下面还原我从读题到AC的完整链路。
Step 1：确认变换类型
题干明确“i⊕j=k”，锁定异或卷积。排除或/与。
Step 2：选模数下的运算安全
模数10⁹+7是质数，且2在模意义下有逆元（inv2 = (10⁹+7+1)/2 = 500000004）。FWT需要除2ⁿ，所以IFWT时要乘inv2ⁿ。不能直接用浮点除，必须用快速幂算inv2ⁿ mod MOD。
Step 3：手写FWT，拒绝模板
我坚持手写，因为模板常有边界错误。核心函数：
void fwt(vector<ll>& a, bool 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 u = a[i+j], v = a[i+j+len]; a[i+j] = (u + v) % MOD; a[i+j+len] = (u - v + MOD) % MOD; } if(inv) { ll invn = pow_mod(n, MOD-2, MOD); // 费马小定理求逆元 for(auto& x : a) x = x * invn % MOD; } }注意三点：
- 循环变量len从1开始，每次×2，直到len<n；
- 内层i步长是len<<1（即2len），保证不重叠；
a[i+j+len] = (u - v + MOD) % MOD中的+MOD防负数，C++取模负数会出负值；- inv参数控制是否做IFWT，统一处理比写两个函数更不易错。
Step 4：验证小样例
n=1，a=[1,2], b=[3,4]。手动：c[0]=1×3+2×4=11, c[1]=1×4+2×3=10。
FWT(a): [3, -1], FWT(b): [7, -1], 乘积[21,1], IFWT: [11,10]。正确。
Step 5：内存与常数优化
n=20，数组长2²⁰≈1e6，三数组a,b,c各占8MB，总24MB，内存够。但常数要注意：
- 避免vector的push_back，预分配大小；
- 用long long存中间值，防溢出（a[i]最大1e9，乘后可能1e18，long long安全）；
- 循环展开？没必要，现代编译器自动优化。
Step 6：提交前终极检查
- 模数用#define MOD 1000000007，别手误写成1e9+7（C++里1e9是double）；
- pow_mod的指数是MOD-2，不是n；
- IFWT的invn是n的逆元，n=1<<n，不是n本身；
- 数组索引从0开始，别用1-based。
提交，AC。耗时124ms，内存15MB。比朴素O(2²ⁿ)快10⁶倍。
但这只是开始。真正的挑战是变形题：比如“c[k] = ∑_{i⊕j=k} a[i] × b[j] × (i&j==0)”，即要求i,j无公共位。这时不能直接FWT，因为多了约束。解法是：先对a,b做子集卷积（用zeta+FWT+莫比乌斯），或用容斥原理：令d[mask] = ∑_{i⊆mask} a[i]，e[mask] = ∑_{j⊆mask} b[j]，则答案是∑_{mask} d[mask]×e[mask]×(-1)^{popcount(mask)}。这已超出FWT范畴，进入生成函数领域。
所以FWT不是万能钥匙，而是离散卷积工具箱里最锋利的一把刀。它解决不了所有“位运算求和”，但所有能被分解为“位独立”的卷积，它都是最优解。我的经验是：看到∑_{i op j = k}，先问op是⊕,∣,还是&；再问是否要求“恰好”还是“至多”；最后决定用FWT、FZT还是容斥。别一上来就敲FWT模板——那不是解题，是碰运气。
6. FWT在工业界的真实落点：不是替代CNN，而是补足它的盲区
网上热词全是“CNN卷积神经网络”“3D卷积”“空洞卷积”，仿佛卷积=深度学习。但FWT在工业界的用武之地，恰恰在CNN力所不及的角落：高维稀疏布尔数据的实时聚合。
举三个真实场景：
场景1：广告投放中的用户画像交集
某平台有2²⁰个用户标签（兴趣、地域、设备等），每个用户用一个20-bit mask表示。运营想查“同时满足‘游戏’‘iOS’‘北上广’三个标签的用户数”。这本质是与卷积查询：对每个标签mask_t，构造数组a_t[i] = [i & mask_t == mask_t]（即i包含mask_t），则答案是∑_i (∏_t a_t[i])。但20个数组逐点乘太慢。用与卷积的zeta变换：先对每个a_t做超集求和（即a_t'[i] = ∑_{j⊇i} a_t[j]），则a_t'[mask_t]就是含mask_t的用户数；再对所有a_t'做逐点min（因交集要求所有条件同时满足），结果数组的sum就是答案。FWT在这里是底层引擎，API层只暴露“多标签交集查询”。
场景2：芯片设计中的逻辑等价性验证
两个布尔电路，输入n位，输出1位。验证它们是否功能等价，即对所有输入x，f(x)==g(x)。朴素方法枚举2ⁿ输入，n=32时不可行。FWT提供代数方法：计算f和g的沃尔什谱，若谱完全相同，则函数等价。因为沃尔什谱唯一确定布尔函数。实际中，用随机采样+谱稀疏性（多数电路谱能量集中在低频），FWT能在O(n·2ᵏ)内验证（k<<n），比形式验证快百倍。
场景3：推荐系统的实时协同过滤
传统CF用矩阵分解，但用户-物品交互是稀疏二元矩阵（点击/未点击）。FWT用于高效计算Jaccard相似度：用户u,v的相似度 = |I_u ∩ I_v| / |I_u ∪ I_v|。分子是与卷积，分母是或卷积。用FZT预处理所有用户的item mask，一次O(n·2ⁿ)预处理，后续任意u,v相似度查询O(1)。
这些场景的共同点：数据是高维、稀疏、布尔的，运算基于位逻辑，且要求亚秒级响应。CNN擅长处理稠密连续信号（图像、语音），但面对2²⁰维的稀疏0-1向量，CNN的卷积核会爆炸式增长，而FWT的O(n·2ⁿ)是可控的。所以FWT不是CNN的竞品，而是它的互补协议：CNN看“像素怎么排”，FWT看“哪些比特同时亮”。
最后分享个血泪教训：某次我把FWT用于日志异常检测，想快速统计“同时出现error和timeout的请求比例”。写了zeta变换，结果线上QPS暴跌。排查发现：zeta变换的“向上推”操作，在缓存中是随机访存（i→i|bit，地址跳跃），而CPU cache line失效严重。改成分块zeta：对每个bit，先处理所有i的低位部分，再高位，提升cache命中率，QPS恢复。所以FWT不仅是数学，更是计算机体系结构的实践——再优美的算法，不考虑cache，也是纸上谈兵。
我在实际使用中发现：FWT的价值不在“快”，而在“可预测”。FFT受输入数据分布影响（病态矩阵），而FWT的沃尔什矩阵条件数恒为1，数值稳定；CNN训练需要GPU，FWT纯CPU即可；更重要的是，FWT的结果可解释——每个谱系数对应一个特定比特模式的贡献度，这在可解释AI中是稀缺资源。所以别只把它当竞赛技巧，它是连接离散数学与工程落地的坚实桥梁。
