快速沃尔什变换（FWT）介绍
众所周知，FFT可以有效地解决如下的问题
A = ( a 1 , … , a n ) B = ( b 1 , . . . , b n ) C = ( c 1 , . . . , c n ) c k = ∑ i + j = k a i ∗ b j A=(a_1,\dots,a_n)\\ B=(b_1,...,b_n)\\ C=(c_1,...,c_n)\\ c_k=\sum_{i+j=k}a_i*b_j\\ A=(a1,…,an)B=(b1,...,bn)C=(c1,...,cn)ck=i+j=k∑ai∗bj
但事实上，把求和号里的条件里的“+”换成与、或、异或、同或也可以有 O ( n log n ) O(n\log n) O(nlogn)时间复杂度的计算方法，这就是快速沃尔什变换（FWT）
鉴于与和或、异或和同或的处理方式比较相似，因此这里就重点分析或、异或这两种情况，另外两种只给结论
注：这里假设序列长度都是 2 k 2^k 2k（事实上必须补成这个样子）
或卷积
对于卷积来说，我们肯定希望最后变成元素积来进行运算，那么能够进行元素积的这个状态就是我们的目标，在FFT中这个目标状态是插值，而在或卷积中，我们要的目标状态是这样的
F W T o r ( A ) [ i ] = ∑ i ∣ j = i a j ( ∗ ) FWT_{or}(A)[i]=\sum_{i|j=i}a_j\ \ (*) FWTor(A)[i]=i∣j=i∑aj (∗)
事实上就是对于i来说 F W T o r ( A ) [ i ] FWT_{or}(A)[i] FWTor(A)[i]就是i的子集的对应位置的和（请记住这一点）
很容易看出
F W T o r ( C ) [ i ] = F W T o r ( A ) [ i ] ∗ F W T o r ( B ) [ i ]
最低0.47元/天 解锁文章
1976
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
