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的基函数必须从布尔函数的真值表里亲手推出来否则永远只能当黑盒调用。我们从最简单的n1开始。定义域是{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)ˣ即x0时为1x1时为-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)ˣ就是n1的沃尔什基。它物理意义是什么是奇偶校验当x0偶数个1输出1x1奇数个1输出-1。推广到n位φₛ(x) (-1)^{s·x}其中s·x是s和x的按位与再求和即汉明权重模2。例如n2s01二进制x11则s·x 0·1 1·1 1φₛ(x) (-1)¹ -1。现在看n2的完整沃尔什矩阵W₂。行索引s00,01,10,11列索引x00,01,10,11s\x00011011001111011-11-11011-1-1111-1-11发现规律了吗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₁)这就是“蝴蝶操作”。n3时总共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⊕bc”能变成“FWT(a)[i] × FWT(b)[i] FWT(c)[i]”异或卷积定义为c[k] ∑_{i⊕jk} a[i] × b[j]。朴素实现要枚举所有i,jO(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在φₛ方向上的投影强度。举个n2实例。设a[1,2,3,4]索引00,01,10,11b[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。但用FWTFWT(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⊕jk} a[i]b[j]。k00时i⊕j00即ij所以c[00]a[00]b[00]a[01]b[01]a[10]b[10]a[11]b[11]1×12×03×04×15。但FWT给出c[00]6。错在b的索引理解b[1,0,0,1]对应b[00]1, b[01]0, b[10]0, b[11]1。i⊕j00的(i,j)对有(00,00),(01,01),(10,10),(11,11)没错。但FWT计算无误说明手动算错了重算a[00]1,b[00]1→1a[01]2,b[01]0→0a[10]3,b[10]0→0a[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]IFWTc[00](2000-4)/416/44还是不对。算FWT(b)b[1,0,0,1]s00: (-1)⁰×1 (-1)⁰×0 (-1)⁰×0 (-1)⁰×1 2s01: (-1)⁰×1 (-1)¹×0 (-1)⁰×0 (-1)¹×1 1-10s10: (-1)⁰×1 (-1)⁰×0 (-1)¹×0 (-1)¹×1 1-10s11: (-1)⁰×1 (-1)¹×0 (-1)¹×0 (-1)⁰×1 112。所以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⊕j00的对(00,00):1×11, (01,01):2×00, (10,10):3×00, (11,11):4×14总和5。但FWT给出4。除非……b[11]不是1b[1,0,0,1]第4个是b[11]1没错。真相是异或卷积的定义中索引i,j,k是整数但运算i⊕jk在二进制下成立。当n2k00即0i⊕j0意味着ij没错。但FWT结果c[4,?, ?, ?]c[00]4说明要么手动计算漏项要么FWT实现有误。检查FWT(a)a[1,2,3,4]第一层按bit1分A₀[1,2], A₁[3,4]FWT(A₀): [12, 1-2] [3,-1]FWT(A₁): [34, 3-4] [7,-1]合并B₀ [37, -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](20000)/45。完美匹配。这个小错误恰恰说明FWT代码里蝶形运算的符号和顺序极易写反。很多人的FWT模板第一版都WA就是因为合并时用了A₀-A₁当B₀或搞混了A₀/A₁的切分方向。我的教训是写完必须用n1,2的手动案例验证宁可多花5分钟别让TLE浪费1小时。4. 或卷积与与卷积不是FWT的变种而是zeta变换的孪生兄弟看到“FWT”就默认是异或卷积大错特错。竞赛题里“子集卷积”“超集求和”“掩码DP”全靠或/与卷积撑腰而它们和异或卷积的数学基因完全不同——异或卷积基于群表示论Z₂ⁿ加法群或/与卷积基于偏序集上的zeta变换subset lattice。先看或卷积c[k] ∑_{i∣jk} a[i] × b[j]即所有满足i或j等于k的(i,j)对求和。注意是i∣jk不是i∣j⊆k。这意味着i和j的并集必须恰好是k不能少也不能多。例如k101₂则i,j只能是000,001,100,101的子集且i∣j必须101。这比异或卷积更“稀疏”。或卷积的变换叫快速zeta变换FZT。它的基函数是φₛ(x) [s⊆x]艾弗森括号s是x的子集。变换矩阵是下三角的行s列x若s⊆x则为1否则0。例如n2s\x00011011001111010101100011110001这个矩阵的逆是莫比乌斯变换μ(s,x) (-1)^{|x|-|s|} [s⊆x]。所以zeta变换的正向是求和逆向是容斥。FZT算法是经典的“子集求和”对每个i枚举i的每一位若该位为0则把a[i]加到a[i|bit]上。代码极简for(int i 0; i (1n); i) for(int j 0; j n; j) if(!(i (1j))) a[i | (1j)] a[i];这就是或卷积的“FWT”。它时间复杂度O(n·2ⁿ)比异或卷积的O(n·2ⁿ)多一个常数但思想更直观从小集合往大集合“推”。与卷积c[k] ∑_{ijk} a[i] × b[j]即i和j的交集恰好是k。变换是超集zeta变换φₛ(x) [s⊇x]s包含x。算法是对每位若该位为1则把a[i]加到a[i~bit]上for(int i 0; i (1n); i) for(int j 0; j n; j) if(i (1j)) a[i ^ (1j)] 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⊕jk} a[i] × b[j]模10⁹7。n≤20。” 这是FWT裸题但AC率常低于50%——不是不会是细节掉链子。下面还原我从读题到AC的完整链路。Step 1确认变换类型题干明确“i⊕jk”锁定异或卷积。排除或/与。Step 2选模数下的运算安全模数10⁹7是质数且2在模意义下有逆元inv2 (10⁹71)/2 500000004。FWT需要除2ⁿ所以IFWT时要乘inv2ⁿ。不能直接用浮点除必须用快速幂算inv2ⁿ mod MOD。Step 3手写FWT拒绝模板我坚持手写因为模板常有边界错误。核心函数void fwt(vectorll 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[ij], v a[ijlen]; a[ij] (u v) % MOD; a[ijlen] (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直到lenn内层i步长是len1即2len保证不重叠a[ijlen] (u - v MOD) % MOD中的MOD防负数C取模负数会出负值inv参数控制是否做IFWT统一处理比写两个函数更不易错。Step 4验证小样例n1a[1,2], b[3,4]。手动c[0]1×32×411, c[1]1×42×310。FWT(a): [3, -1], FWT(b): [7, -1], 乘积[21,1], IFWT: [11,10]。正确。Step 5内存与常数优化n20数组长2²⁰≈1e6三数组a,b,c各占8MB总24MB内存够。但常数要注意避免vector的push_back预分配大小用long long存中间值防溢出a[i]最大1e9乘后可能1e18long long安全循环展开没必要现代编译器自动优化。Step 6提交前终极检查模数用#define MOD 1000000007别手误写成1e97C里1e9是doublepow_mod的指数是MOD-2不是nIFWT的invn是n的逆元n1n不是n本身数组索引从0开始别用1-based。提交AC。耗时124ms内存15MB。比朴素O(2²ⁿ)快10⁶倍。但这只是开始。真正的挑战是变形题比如“c[k] ∑_{i⊕jk} a[i] × b[j] × (ij0)”即要求i,j无公共位。这时不能直接FWT因为多了约束。解法是先对a,b做子集卷积用zetaFWT莫比乌斯或用容斥原理令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位。验证它们是否功能等价即对所有输入xf(x)g(x)。朴素方法枚举2ⁿ输入n32时不可行。FWT提供代数方法计算f和g的沃尔什谱若谱完全相同则函数等价。因为沃尔什谱唯一确定布尔函数。实际中用随机采样谱稀疏性多数电路谱能量集中在低频FWT能在O(n·2ᵏ)内验证kn比形式验证快百倍。场景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训练需要GPUFWT纯CPU即可更重要的是FWT的结果可解释——每个谱系数对应一个特定比特模式的贡献度这在可解释AI中是稀缺资源。所以别只把它当竞赛技巧它是连接离散数学与工程落地的坚实桥梁。