整理的演算法模板合集： ACM模板

點我看演算法全家桶系列！！！

實際上是一個全新的精煉模板整合計劃

---

前置知識：FFT

開始的開始，我們先來復習一下卷積的相關概念（注：0x00 卷積的部分內容（0x02、0x03、0x04）摘自 @wangrx，他寫的太好了 %%%，略作修改完善，侵刪）之后本文中所有的符號也都參照他的形式書寫，以及本文中所有的多項式的系數 n n n 均為 2 2 2 的整數冪的形式（學過 FFT 的都懂hhh不然就沒法分治了）

自認為本文是最為清晰完整的 FWT 講解博客，含有全套完整清晰的證明，相信小學生都能看懂 ~

前排規定本文所用符號：

多項式 / 序列卷積： ? \otimes ?

多項式 / 序列對應系數相乘 / 普通的乘法： × \times ×

多項式 / 序列第 k k k 項系數： ( f ) k (f)_k (f)k? ， ( f ? g ) k (f\otimes g)_k (f?g)k? ， ( A ) [ i ] (A)[i] (A)[i]

多項式 / 序列加法： ⊕ \oplus ⊕

多項式 / 序列減法： ? \ominus ?

多項式 / 序列 or \text {or} or 卷積（ |，或）： ? or \otimes_{\text{or}} ?or?

多項式 / 序列 and \text {and} and 卷積（ &，或）： ? and \otimes_{\text{and}} ?and?

多項式 / 序列 xor \text {xor} xor 卷積（ ^，或）： ? xor \otimes_{\text{xor}} ?xor?

0x00 卷積

0x01 多項式

我們知道對于一個普通的多項式可以表示為系數表示： f ( x ) = a 0 x 0 + a 1 x 1 + ? ? ? + a n ? 1 x n ? 1 f(x)=a_0x^0+a_1x^1+···+a_{n-1}x^{n-1} f(x)=a0?x0+a1?x1+???+an?1?xn?1

規定 f = a 0 x 0 + a 1 x 1 + ? ? ? + a n ? 1 x n ? 1 f=a_0x^0+a_1x^1+···+a_{n-1}x^{n-1} f=a0?x0+a1?x1+???+an?1?xn?1， g = b 0 x 0 + b 1 x 1 + ? ? ? + b n ? 1 x n ? 1 g=b_0x^0+b_1x^1+···+b_{n-1}x^{n-1} g=b0?x0+b1?x1+???+bn?1?xn?1

則可將多項式的系數表示簡化為： f = ( a 0 , a 1 , a 2 ? ? ? a n ? 1 ) f=(a_0,a_1,a_2···a_{n-1}) f=(a0?,a1?,a2????an?1?)， g = ( b 0 , b 1 , b 2 ? ? ? b n ? 1 ) g=(b_0,b_1,b_2···b_{n-1}) g=(b0?,b1?,b2????bn?1?)

---

定義多項式加減法： ⊕ , ? \oplus,\ominus ⊕,?
H = f ⊕ g = ( a 0 , a 1 , a 2 ? ? ? a n ? 1 ) ⊕ ( b 0 , b 1 , b 2 ? ? ? b n ? 1 ) = ( a 0 + b 0 , a 1 + b 1 , a 2 + b 2 ? ? ? a n ? 1 + b n ? 1 ) \begin{aligned} H&=f\oplus g\\& =(a_0,a_1,a_2???a_{n?1})\oplus (b_0,b_1,b_2???b_{n?1})\\&=(a_0+b_0,a_1+b_1,a_2+b_2???a_{n?1}+b_{n?1}) \end{aligned} H?=f⊕g=(a0?,a1?,a2????an?1?)⊕(b0?,b1?,b2????bn?1?)=(a0?+b0?,a1?+b1?,a2?+b2????an?1?+bn?1?)?

H = f ? g = ( a 0 , a 1 , a 2 ? ? ? a n ? 1 ) ⊕ ( b 0 , b 1 , b 2 ? ? ? b n ? 1 ) = ( a 0 ? b 0 , a 1 ? b 1 , a 2 ? b 2 ? ? ? a n ? 1 ? b n ? 1 ) \begin{aligned} H&=f\ominus g\\& =(a_0,a_1,a_2???a_{n?1})\oplus (b_0,b_1,b_2???b_{n?1})\\&=(a_0-b_0,a_1-b_1,a_2-b_2???a_{n?1}-b_{n?1}) \end{aligned} H?=f?g=(a0?,a1?,a2????an?1?)⊕(b0?,b1?,b2????bn?1?)=(a0??b0?,a1??b1?,a2??b2????an?1??bn?1?)?

其中多項式加減的第 k k k 項系數：

( f ⊕ g ) k = a k f k + b k g k (f\oplus g)_k=a_kf_k+b_kg_k (f⊕g)k?=ak?fk?+bk?gk?

( f ? g ) k = a k f k ? b k g k (f\ominus g)_k=a_kf_k-b_kg_k (f?g)k?=ak?fk??bk?gk?

---

定義多項式對應系數相乘 （一定注意這里不是卷積 ? \otimes ?）
H = f × g = ( a 0 , a 1 , a 2 ? ? ? a n ? 1 ) × ( b 0 , b 1 , b 2 ? ? ? b n ? 1 ) = ( a 0 × b 0 , a 1 × b 1 , a 2 × b 2 ? ? ? a n ? 1 × b n ? 1 ) \begin{aligned} H&=f\times g\\& =(a_0,a_1,a_2???a_{n?1})\times (b_0,b_1,b_2???b_{n?1})\\&=(a_0\times b_0,a_1\times b_1,a_2\times b_2???a_{n?1}\times b_{n?1}) \end{aligned} H?=f×g=(a0?,a1?,a2????an?1?)×(b0?,b1?,b2????bn?1?)=(a0?×b0?,a1?×b1?,a2?×b2????an?1?×bn?1?)?

其中多項式對應系數相乘的第 k k k 項系數：

( f ? g ) k = a k f k × b k g k (f\otimes g)_k=a_kf_k\times b_kg_k (f?g)k?=ak?fk?×bk?gk?

---

0x02 卷積的定義

對于一個序列，將其中元素一一映射到一個多項式函式的系數上， 這個多項式函式便叫做該序列的生成函式，

形式化地講，對于序列 f 0 , f 1 , ? ? , f n ? 1 f_0,f_1,\cdots,f_{n-1} f0?,f1?,?,fn?1? ， f ( x ) = ∑ k = 0 n ? 1 f k x k f(x)=\displaystyle\sum_{k=0}^{n-1}f_kx^k f(x)=k=0∑n?1?fk?xk 為其生成函式，

卷積即為生成函式的乘積在對應序列的變換上的的抽象，“卷”即為其作用效果，“積”即為其本質，

對于序列 f , g f,g f,g ，其卷積序列 f ? g f\otimes g f?g 滿足 ( f ? g ) k = ∑ i = 0 k f i × g k ? i = ∑ i , j i + j = k f i × g j (f\otimes g)_k=\displaystyle\sum\limits_{i=0}^kf_i\times g_{k-i}=\sum\limits_{i,j}^{i+j=k}f_i\times g_j (f?g)k?=i=0∑k?fi?×gk?i?=i,j∑i+j=k?fi?×gj?

對于多項式 f , g f,g f,g，其多項式的卷積為： f ? g = ∑ k = 0 n ( ∑ i , j i + j = k a i × b j ) x k f\otimes g=\sum\limits_{k=0}^{n}(\sum\limits_{i,j}^{i+j=k}a_i\times b_j)x^k f?g=k=0∑n?(i,j∑i+j=k?ai?×bj?)xk

而我們所熟知的 FFT 計算的是回圈卷積，也即 ( f ? g ) k = ∑ i + j ≡ k ( m o d n ) f i × g j (f\otimes g)_k=\displaystyle\sum_{i+j\equiv k\pmod n}f_i\times g_j (f?g)k?=i+j≡k(modn)∑?fi?×gj? ， n n n 為序列長度，

0x03 卷積的基本性質

這里的卷積均為序列的卷積，因此證明時我們使用數學歸納法，即證明第 k k k 項成立，則整個序列均成立，由于多項式實際上就是序列的生成函式，所以性質同樣成立，

• f ? g = g ? f f\otimes g=g\otimes f f?g=g?f（交換律）

  我們使用定義 ( f ? g ) k = ∑ i + j = k f i × g j (f\otimes g)_k=\displaystyle\sum_{i+j=k}f_i\times g_j (f?g)k?=i+j=k∑?fi?×gj? ，以及乘法交換律 a × b = b × a a\times b=b\times a a×b=b×a 即可證明，因為 i + j = k i+j=k i+j=k 的 i i i 和 j j j 是一一對應的，

• ( f ? g ) ? h = f ? ( g ? h ) (f\otimes g)\otimes h=f\otimes(g \otimes h) (f?g)?h=f?(g?h) （結合律）
  證明：
  [ f ? ( g ? h ) ] n = ∑ i = 0 n f n ? i × ( g ? h ) i = ∑ i = 0 n f n ? i ∑ j = 0 i g j h i ? j = ∑ i = 0 n ∑ j = 0 i f n ? i g j h i ? j = ∑ i + j + k = n f i g j h k \begin{aligned} {[f\otimes(g\otimes h)]_n} & =\displaystyle\sum_{i=0}^nf_{n-i}\times(g\otimes h)_i & \\& =\sum_{i=0}^nf_{n-i}\sum_{j=0}^ig_jh_{i-j}\\& =\sum_{i=0}^n\sum_{j=0}^if_{n-i}g_jh_{i-j}\\& =\sum_{i+j+k=n}f_ig_jh_k\end{aligned} [f?(g?h)]n??=i=0∑n?fn?i?×(g?h)i?=i=0∑n?fn?i?j=0∑i?gj?hi?j?=i=0∑n?j=0∑i?fn?i?gj?hi?j?=i+j+k=n∑?fi?gj?hk??

交換順序后反向推導即可得證，

• ( f ⊕ g ) ? h = ( f ? h ) ⊕ ( g ? h ) (f\oplus g)\otimes h=(f\otimes h)\oplus(g\otimes h) (f⊕g)?h=(f?h)⊕(g?h) （分配律）
  其中 ( f ⊕ g ) k = a f k + b g k (f\oplus g)_k=af_k+bg_k (f⊕g)k?=afk?+bgk? ，即序列 f , g f,g f,g 的加法， a , b a,b a,b 為常數，

證明：
[ ( f ⊕ g ) ? h ] k = ∑ i = 0 k ( f ⊕ g ) i h k ? i = ∑ i = 0 k ( a f i + b g i ) h k ? i = ∑ i = 0 k ( a f i h k ? i + b g i h k ? i ) = a ∑ i = 0 k f i h k ? i + b ∑ i = 0 k g i h k ? i = a ( f ? h ) k + b ( g ? h ) k = [ ( f ? h ) ⊕ ( g ? h ) ] k \begin{aligned} {[(f\oplus g)\otimes h]_k} &=\displaystyle\sum_{i=0}^k(f\oplus g)_ih_{k-i}\\ & =\sum_{i=0}^k (af_i+bg_i)h_{k-i} \\ &=\sum_{i=0}^k(af_ih_{k-i}+bg_ih_{k-i})\\ &=a\sum_{i=0}^kf_ih_{k-i}+b\sum_{i=0}^kg_ih_{k-i}\\&=a(f\otimes h)_k+b(g\otimes h)_k=[(f\otimes h)\oplus(g\otimes h)]_k \end{aligned} [(f⊕g)?h]k??=i=0∑k?(f⊕g)i?hk?i?=i=0∑k?(afi?+bgi?)hk?i?=i=0∑k?(afi?hk?i?+bgi?hk?i?)=ai=0∑k?fi?hk?i?+bi=0∑k?gi?hk?i?=a(f?h)k?+b(g?h)k?=[(f?h)⊕(g?h)]k??

0x04 位運算卷積定義及其性質

一般的卷積滿足 i + j = k i+j=k i+j=k ，又稱為加法卷積，

類似的，對于序列 f = { f 0 , f 1 , ? ? , f 2 n ? 1 } , g = { g 0 , g 1 , ? ? , g 2 n ? 1 } f=\{f_0,f_1,\cdots,f_{2^n-1}\},g=\{g_0,g_1,\cdots,g_{2^n-1}\} f={f0?,f1?,?,f2n?1?},g={g0?,g1?,?,g2n?1?} ，
可以定義位運算卷積 ( f ? ⊙ g ) k = ∑ i ⊙ j = k f i × g j \displaystyle(f\otimes_\odot g)_k=\sum_{i\odot j=k}f_i\times g_j (f?⊙?g)k?=i⊙j=k∑?fi?×gj? ，其中 ⊙ = and , or , xor \odot=\text{and},\text{or},\text{xor} ⊙=and,or,xor ，
還有 max ? \max max 卷積，這里不再拓展， 讀者自行查找相關資料，現在著重討論 ? xor \otimes_\text{xor} ?xor?

• f ? xor g = g ? xor \displaystyle f\otimes_\text{xor} g=g\otimes_\text{xor} f?xor?g=g?xor? （交換律）
  由于 a xor ? b = b xor ? a\operatorname{xor}b=b\operatorname{xor} axorb=bxor ，根據定義顯然成立，
  and ? , or ? a n d , o r \operatorname{and},\operatorname{or}and,or and,orand,or 同樣滿足此性質，原因同上，
• ( f ? xor g ) ? xor h = f ? xor ( g ? xor h ) (f\otimes_\text{xor} g)\otimes_\text{xor} h=f\otimes_\text{xor}(g \otimes_\text{xor} h) (f?xor?g)?xor?h=f?xor?(g?xor?h) （結合律）
  證明： 根據定義，有 ( f ? xor g ) k = ∑ i xor ? j = k f i × g j = ∑ i = 0 2 n ? 1 f i × g k xor ? i (f\otimes_\text{xor} g)_k=\displaystyle\sum_{i\operatorname{xor}j=k}f_i\times g_j=\sum\limits_{i=0}^{2^n-1}f_i\times g_{k\operatorname{xor}i} (f?xor?g)k?=ixorj=k∑?fi?×gj?=i=0∑2n?1?fi?×gkxori? ，則

[ f ? xor ( g ? xor h ) ] m = ∑ i = 0 2 n ? 1 f m xor ? i × ( g ? xor h ) i = ∑ i = 0 2 n ? 1 f m xor ? i ∑ j = 0 2 n ? 1 g j h i xor ? j = ∑ i = 0 2 n ? 1 ∑ j = 0 2 n ? 1 f m xor ? i g j h i xor ? j = ∑ i xor ? j xor ? k = m f i g j h k \begin{aligned} {[f\otimes_\text{xor}(g\otimes_\text{xor}h)]_m} & =\sum_{i=0}^{2^n-1}f_{m\operatorname{xor}i}\times(g\otimes_\text{xor}h)_i \\&=\sum_{i=0}^{2^n-1}f_{m\operatorname{xor}i}\sum_{j=0}^{2^n-1}g_jh_{i\operatorname{xor}j}\\&=\sum_{i=0}^{2^n-1}\sum_{j=0}^{2^n-1}f_{m\operatorname{xor}i}g_jh_{i\operatorname{xor}j}\\& =\sum_{i\operatorname{xor}j\operatorname{xor}k=m}f_ig_jh_k\end{aligned} [f?xor?(g?xor?h)]m??=i=0∑2n?1?fmxori?×(g?xor?h)i?=i=0∑2n?1?fmxori?j=0∑2n?1?gj?hixorj?=i=0∑2n?1?j=0∑2n?1?fmxori?gj?hixorj?=ixorjxork=m∑?fi?gj?hk??

交換順序后反向推導即可得證，
or ? , and ? \operatorname{or},\operatorname{and} or,and 沒有對應的逆運算，因此證明相對復雜，這里不給出證明，

• ( f ⊕ g ) ? xor h = ( f ? xor h ) ⊕ ( g ? xor h ) (f\oplus g)\otimes_\text{xor} h=(f\otimes_\text{xor} h)\oplus(g\otimes_\text{xor} h) (f⊕g)?xor?h=(f?xor?h)⊕(g?xor?h) (分配律)
  證明同加法卷積， and ? , or ? \operatorname{and},\operatorname{or} and,or 同理，

0x10 FWT（快速沃爾什變換）

復習完上述基本概念以后，我們進入今天的正題，快速沃爾什變換（FWT），

我們知道 FFT 是用來在 O ( n l o g n ) \mathcal O(nlogn) O(nlogn) 的時間復雜度下利用分治求解普通序列 / 多項式的卷積：

對于序列 f , g f,g f,g ，其卷積序列 f ? g f\otimes g f?g 滿足對于 f ? g f\otimes g f?g 的第 k k k 項： ( f ? g ) k = ∑ i = 0 k f i × g k ? i = ∑ i , j i + j = k f i × g j (f\otimes g)_k=\displaystyle\sum\limits_{i=0}^kf_i\times g_{k-i}=\sum\limits_{i,j}^{i+j=k}f_i\times g_j (f?g)k?=i=0∑k?fi?×gk?i?=i,j∑i+j=k?fi?×gj?

對于多項式 f , g f,g f,g，其多項式的卷積為： f ? g = ∑ k = 0 n ( ∑ i , j i + j = k a i × b j ) x k \displaystyle f\otimes g=\sum\limits_{k=0}^{n}(\sum\limits_{i,j}^{i+j=k}a_i\times b_j)x^k f?g=k=0∑n?(i,j∑i+j=k?ai?×bj?)xk

上面定義了位運算卷積： ( f ? ⊙ g ) k = ∑ i ⊙ j = k f i × g j \displaystyle(f\otimes_\odot g)_k=\sum_{i\odot j=k}f_i\times g_j (f?⊙?g)k?=i⊙j=k∑?fi?×gj? ，其中 ⊙ = and , or , xor \odot=\text{and},\text{or},\text{xor} ⊙=and,or,xor ，并講解了一系列相關性質，那么我們如何求得位運算卷積呢？我們模仿 FFT 給出一種類似的求解演算法：快速沃爾什變換（FWT），

嚴格來講，FWT 僅為 xor \text {xor} xor 卷積，FMT 為 and \text{and} and、 or \text{or} or 卷積，這里放到一塊統稱為 FWT，（QWQ）

我們將兩個 ( n ? 1 ) (n - 1) (n?1) 次多項式 A ( x ) = ∑ i = 0 n ? 1 a i x i \displaystyle A(x)~=~\sum\limits_{i = 0}^{n - 1} a_i x^i A(x) = i=0∑n?1?ai?xi ， B ( x ) = ∑ i = 0 n ? 1 b i x i \displaystyle B(x)~=~\sum\limits_{i = 0}^{n - 1} b_i x^i B(x) = i=0∑n?1?bi?xi 的系數數列 { a i } \{a_i\} {ai?}，對其進行離散傅里葉變換（DFT）得到的兩個點值表示 { A d i } \{Ad_i\} {Adi?}， { B d i } \{Bd_i\} {Bdi?}，其中 A d k = ∑ i = 0 n ? 1 a i × ω n i k \displaystyle Ad_k~=~\sum\limits_{i = 0}^{n - 1} a_i \times \omega_n^{ik} Adk? = i=0∑n?1?ai?×ωnik?，我們使用 FFT 在 O ( n l o g n ) \mathcal O(nlogn) O(nlogn) 的時間復雜度下完成這一操作，

之后在 O ( n ) \mathcal O(n) O(n) 的時間復雜度下完成兩個點值表示的多項式的乘積 C i = A d i × B d i C_i=Ad_i\times Bd_i Ci?=Adi?×Bdi?，

最后利用結論 a k = 1 n ∑ i = 0 n ? 1 d i ω n ? k i \displaystyle a_k~=~\frac{1}{n} \sum_{i = 0}^{n - 1} d_i \omega_n^{-ki} ak? = n1?i=0∑n?1?di?ωn?ki? ，通過逆離散傅里葉變換（IDFT）還原系數數列 { c i } \{c_i\} {ci?} 得到答案，同樣使用 FFT 在 O ( n l o g n ) \mathcal O(nlogn) O(nlogn) 的時間復雜度下完成這一操作，

我們借鑒多項式乘法即普通卷積的實作 FFT 得出類似的思路 FWT：

我們先求出多項式的另一種多項式表示 F W T ( A ) FWT(A) FWT(A) ， O ( n ) \mathcal O(n) O(n) 將對應的位置乘起來，最后復原即可，

即答案 F W T ( C ) = F W T ( A ) × F W T ( B ) \displaystyle FWT(C)=FWT(A)\times FWT(B) FWT(C)=FWT(A)×FWT(B)（其中 × \times × 是 多項式 / 序列 對應位置相乘）

看上去思路沒有什么問題，我們考慮證明，

由于位運算卷積分為三種 ⊙ = and , or , xor \odot=\text{and},\text{or},\text{xor} ⊙=and,or,xor ，所以我們分開討論，

0x11 或（ or \text{or} or）卷積

**或（ or \text{or} or ，| ） 按位或運算子， | 有 1 為 1 無 1 為 0 **

或卷積： ( f ? or g ) k = ∑ i ∣ j = k f i × g j \displaystyle(f\otimes_{\text{or}} g)_k=\sum_{i| j=k}f_i\times g_j (f?or?g)k?=i∣j=k∑?fi?×gj?

對于序列 A , B , C A,B,C A,B,C， A = { a 0 , a 1 ? ? , a n } A=\{a_0,a_1\cdots,a_{n}\} A={a0?,a1??,an?}， B = { b 0 , b 1 , ? ? , b n } B=\{b_0,b_1,\cdots,b_n\} B={b0?,b1?,?,bn?}， C = { c 0 , c 1 , ? c n } C=\{c_0,c_1,\cdots c_n\} C={c0?,c1?,?cn?} ，我們令 C C C 為或卷積的結果，

我們想要求的式子為 F W T ( C ) = F W T ( A ) × F W T ( B ) FWT(C)=FWT(A)\times FWT(B) FWT(C)=FWT(A)×FWT(B) ，即： c k = ∑ i ∣ j = k a i b j \displaystyle c_{k}=\sum_{i \mid j=k} a_{i} b_{j} ck?=i∣j=k∑?ai?bj?

顯然有 i ∣ k = k , j ∣ k = k → ( i ∣ j ) ∣ k = k i|k = k, j|k=k \to (i|j)|k=k i∣k=k,j∣k=k→(i∣j)∣k=k ，

因此我們構造快速沃爾什變換 F W T FWT FWT ： F W T ( A ) [ k ] = ∑ i ∣ k = k a i \displaystyle FWT(A)[k]=\sum_{i|k=k}a_i FWT(A)[k]=i∣k=k∑?ai?
F W T ( A ) × F W T ( B ) = ( ∑ i ∣ k = k a i ) ( ∑ j ∣ k = k b j ) = ∑ i ∣ k = k , j ∣ k = k a i b j = ∑ ( i ∣ j ) ∣ k = k a i b j = F W T ( C ) \begin{aligned}FWT(A) \times FWT(B) &=\left(\sum_{i \mid k=k} a_{i}\right)\left(\sum_{j \mid k=k} b_{j}\right) \\&=\sum_{i|k=k,\ j| k=k} a_{i} b_{j} \\&=\sum_{(i \mid j) \mid k=k} a_{i} b_{j} \\&=FWT(C)\end{aligned} FWT(A)×FWT(B)?=???i∣k=k∑?ai???????j∣k=k∑?bj????=i∣k=k, j∣k=k∑?ai?bj?=(i∣j)∣k=k∑?ai?bj?=FWT(C)?

---

性質11.1： F W T ( A ± B ) = F W T ( A ) ± F W T ( B ) FWT(A\pm B)=FWT(A)\pm FWT(B) FWT(A±B)=FWT(A)±FWT(B)

根據 F W T FWT FWT 變換的定義我們可以將其看作是一個 A A A 序列的線性組合，故其加減法滿足分配律，

由此我們可以得到 FWT 的遞推式：

性質11.2：
F W T ( A ) = { ( F W T ( A 0 ) , F W T ( A 0 ) + F W T ( A 1 ) ) n > 1 A n = 0 FWT(A)=\begin{cases}(FWT(A_0),FWT(A_0)+FWT(A_1))& n>1\\\ A & n=0\end{cases} FWT(A)={(FWT(A0?),FWT(A0?)+FWT(A1?)) A?n>1n=0?
其中定義 A A A 為 2 k 2^k 2k 多項式， A 0 A_0 A0? 代表 A A A 的系數序列的前半部分即前 2 k ? 1 2^{k-1} 2k?1 次項， A 1 A_1 A1? 代表 A A A 的后半部分即后 2 k ? 1 2^{k-1} 2k?1 次項，也就是下標的最高位分別為 0 0 0 和 1 1 1 的兩部分，

式中的括號運算定義為： A = ( B , C ) A=(B,C) A=(B,C) ，

表示 B B B 這個多項式后面接上 C C C 等于 A A A，展開后為：
( A , B ) = ( ( a 0 , a 1 , a 2 ? a x ? 1 ) , ( b 0 , b 1 , b 2 ? b y ? 1 ) ) = ( a 0 , a 1 , a 2 ? a x ? 1 , b 0 , b 1 , b 2 ? b y ? 1 ) \begin{aligned}(A, B) &=\left(\left(a_{0}, a_{1}, a_{2} \cdots a_{x-1}\right),\left(b_{0}, b_{1}, b_{2} \cdots b_{y-1}\right)\right) \\&=\left(a_{0}, a_{1}, a_{2} \cdots a_{x-1}, b_{0}, b_{1}, b_{2} \cdots b_{y-1}\right)\end{aligned} (A,B)?=((a0?,a1?,a2??ax?1?),(b0?,b1?,b2??by?1?))=(a0?,a1?,a2??ax?1?,b0?,b1?,b2??by?1?)?
可以理解為系數直接連起來，

考慮證明：

首先 n = 0 n=0 n=0 時顯然成立，

我們知道 A 0 , A 1 A_0,A_1 A0?,A1? 實際上為下標的最高位分別為 0 0 0 和 1 1 1 的兩部分，且除了最高位不同以外，其余的所有位，對于每一個下標 A 1 A_1 A1? 都有一個 A 0 A_0 A0? 與之相對應（僅最高位一個是 1 1 1 ，一個是 0 0 0），

根據 FWT 的定義，合并之后左半部分下標的最高位仍然是 0 0 0，右半部分下標的最高位仍然是 1 1 1

首先對于左半部分：

由于 F W T ( A 1 ) FWT(A_1) FWT(A1?) 的最高位一定為 1 1 1，而此時 j ∣ i j|i j∣i 的最高位不可能為 0 0 0（1 | 0 = 1），所以右半部分在合并之后對于左半部分是沒有貢獻的，故 F W T ( A ) 0 = F W T ( A 0 ) FWT(A)_0=FWT(A_0) FWT(A)0?=FWT(A0?)，

而對于右半部分，如果左半部分的數滿足 j ∣ i = i j|i=i j∣i=i，那么在 i i i 加上最高位 1 1 1 之后， j ∣ i = i j|i=i j∣i=i 仍然成立，而此時右半部分的原來的 F W T ( A 1 ) FWT(A_1) FWT(A1?) 本來就對右半部分的數有貢獻，故 F W T ( A ) 1 = F W T ( A 0 ) + F W T ( A 1 ) FWT(A)_1=FWT(A_0)+FWT(A_1) FWT(A)1?=FWT(A0?)+FWT(A1?)

故我們將這兩部分使用括號運算合并即可得到： F W T ( A ) = ( F W T ( A 0 ) , F W T ( A 0 ) + F W T ( A 1 ) ) FWT(A)=(FWT(A_0),FWT(A_0)+FWT(A_1)) FWT(A)=(FWT(A0?),FWT(A0?)+FWT(A1?))

故 性質11.2 得證，

---

性質11.3： F W T ( A ∣ B ) = F W T ( A ) × F W T ( B ) FWT(A|B)=FWT(A)\times FWT(B) FWT(A∣B)=FWT(A)×FWT(B)

（注，這里的 × \times × 指對應系數相乘，見前排符號規定）

我們可以利用上面的 性質11.1 以及 性質11.2，使用數學歸納法證明：

F W T ( A ∣ B ) = F W T ( ( A ∣ B ) 0 , ( A ∣ B ) 1 ) = F W T ( A 0 ∣ B 0 , A 0 ∣ B 1 + A 1 ∣ B 0 + A 1 ∣ B 1 ) = ( F W T ( A 0 ∣ B 0 ) , F W T ( A 0 ∣ B 0 + A 0 ∣ B 1 + A 1 ∣ B 0 + A 1 ∣ B 1 ) ) = ( F W T ( A 0 ) × F W T ( B 0 ) , F W T ( A 0 ) × F W T ( B 0 ) + F W T ( A 0 ) × F W T ( B 1 ) + F W T ( A 1 ) × F W T ( B 0 ) + F W T ( A 1 ) × F W T ( B 1 ) ) = ( F W T ( A 0 ) × F W T ( B 0 ) , ( F W T ( A 0 ) + F W T ( A 1 ) ) × ( F W T ( B 0 ) + F W T ( B 1 ) ) ) = ( F W T ( A 0 ) , F W T ( A 0 + A 1 ) ) × ( F W T ( B 0 ) , F W T ( B 0 + B 1 ) ) = F W T ( A ) × F W T ( B ) \begin{aligned} FWT(A|B)=&FWT((A|B)_0,(A|B)_1)\\ =&FWT(A_0|B_0,A_0|B_1+A_1|B_0+A_1|B_1)\\ =&(FWT(A_0|B_0),FWT(A_0|B_0+A_0|B_1+A_1|B_0+A_1|B_1))\\ =&(FWT(A_0)\times FWT(B_0)\\&,FWT(A_0)\times FWT(B_0)+FWT(A_0)\times FWT(B_1)+FWT(A_1)\times FWT(B_0)+FWT(A_1)\times FWT(B_1))\\ =&(FWT(A_0)\times FWT(B_0),(FWT(A_0)+FWT(A_1))\times (FWT(B_0)+FWT(B_1)))\\ =&(FWT(A_0),FWT(A_0+A_1))\times (FWT(B_0),FWT(B_0+B_1))\\ =&FWT(A)\times FWT(B) \end{aligned} FWT(A∣B)=======?FWT((A∣B)0?,(A∣B)1?)FWT(A0?∣B0?,A0?∣B1?+A1?∣B0?+A1?∣B1?)(FWT(A0?∣B0?),FWT(A0?∣B0?+A0?∣B1?+A1?∣B0?+A1?∣B1?))(FWT(A0?)×FWT(B0?),FWT(A0?)×FWT(B0?)+FWT(A0?)×FWT(B1?)+FWT(A1?)×FWT(B0?)+FWT(A1?)×FWT(B1?))(FWT(A0?)×FWT(B0?),(FWT(A0?)+FWT(A1?))×(FWT(B0?)+FWT(B1?)))(FWT(A0?),FWT(A0?+A1?))×(FWT(B0?),FWT(B0?+B1?))FWT(A)×FWT(B)?

---

當然我們也可以使用定義將其展開來證明，這樣看上去會會更加的清晰一些，

其中若 i ∣ k = k , j ∣ k = k → ( i ∣ j ) ∣ k = k i|k=k,j|k=k\to (i|j)|k=k i∣k=k,j∣k=k→(i∣j)∣k=k，

F W T ( A ) × F W T ( B ) = ( ∑ i ∣ 0 = 0 a i , ∑ i ∣ 1 = 1 a i , ∑ i ∣ 2 = 2 a i ? ∑ i ∣ ( n ? 1 ) = ( n ? 1 ) a i ) × ( ∑ i ∣ 0 = 0 b i , ∑ i ∣ 1 = 1 b i , ∑ i ∣ 2 = 2 b i ? ∑ i ∣ ( n ? 1 ) = ( n ? 1 ) b i ) = ( ( ∑ i ∣ 0 = 0 a i ) × ( ∑ j ∣ 0 = 0 b j ) , ( ∑ i ∣ 1 = 1 a i ) × ( ∑ j ∣ 1 = 1 b j ) , ( ∑ i ∣ 2 = 2 a i ) × ( ∑ j ∣ 2 = 2 b j ) ? ( ∑ i ∣ ( n ? 1 ) = ( n ? 1 ) a i ) × ( ∑ j ∣ ( n ? 1 ) = ( n ? 1 ) b j ) ) = ( ∑ i ∣ j ∣ 0 = 0 a i × b j , ∑ i ∣ j ∣ 1 = 1 a i × b j , ∑ i ∣ j ∣ 2 = 2 a i × b j ? ∑ i ∣ j ∣ ( n ? 1 ) = ( n ? 1 ) a i × b j ) = ( ∑ k ∣ 0 = 0 ∑ i ∣ j = k a i × b j , ∑ k ∣ 1 = 1 ∑ i ∣ j = k a i × b j , ∑ k ∣ 2 = 2 ∑ i ∣ j = k a i × b j ? ∑ k ∣ ( n ? 1 ) = ( n ? 1 ) ∑ i ∣ j = k a i × b j ) = F W T ( A ∣ B ) \begin{aligned}FWT(A) \times F W T(B) &=\left(\sum_{i \mid 0=0} a_{i}, \sum_{i \mid 1=1} a_{i}, \sum_{i \mid 2=2} a_{i} \cdots \sum_{i \mid(n-1)=(n-1)} a_{i}\right) \times \left(\sum_{i \mid 0=0} b_{i}, \sum_{i \mid 1=1} b_{i}, \sum_{i \mid 2=2} b_{i} \cdots \sum_{i \mid(n-1)=(n-1)} b_{i}\right) \\&=\left(\left(\sum_{i \mid 0=0} a_{i}\right) \times \left(\sum_{j \mid 0=0} b_{j}\right),\left(\sum_{i \mid 1=1} a_{i}\right) \times \left(\sum_{j \mid 1=1} b_{j}\right),\left(\sum_{i \mid 2=2} a_{i}\right) \times \left(\sum_{j \mid 2=2} b_{j}\right) \cdots\left(\sum_{i \mid(n-1)=(n-1)} a_{i}\right) \times \left(\sum_{j \mid(n-1)=(n-1)} b_{j}\right)\right) \\&=\left(\sum_{i|j| 0=0} a_{i} \times b_{j}, \sum_{i|j| 1=1} a_{i}\times b_{j}, \sum_{i|j| 2=2} a_{i} \times b_{j} \cdots \sum_{i|j|(n-1)=(n-1)} a_{i} \times b_{j}\right) \\&=\left(\sum_{k \mid 0=0} \sum_{i \mid j=k} a_{i} \times b_{j}, \sum_{k \mid 1=1} \sum_{i \mid j=k} a_{i} \times b_{j}, \sum_{k \mid 2=2} \sum_{i \mid j=k} a_{i} \times b_{j} \cdots \sum_{k \mid(n-1)=(n-1)} \sum_{i \mid j=k} a_{i} \times b_{j}\right) \\&=F W T(A \mid B)\end{aligned} FWT(A)×FWT(B)?=???i∣0=0∑?ai?,i∣1=1∑?ai?,i∣2=2∑?ai??i∣(n?1)=(n?1)∑?ai????×???i∣0=0∑?bi?,i∣1=1∑?bi?,i∣2=2∑?bi??i∣(n?1)=(n?1)∑?bi????=??????i∣0=0∑?ai????×???j∣0=0∑?bj????,???i∣1=1∑?ai????×???j∣1=1∑?bj????,???i∣2=2∑?ai????×???j∣2=2∑?bj????????i∣(n?1)=(n?1)∑?ai????×???j∣(n?1)=(n?1)∑?bj???????=???i∣j∣0=0∑?ai?×bj?,i∣j∣1=1∑?ai?×bj?,i∣j∣2=2∑?ai?×bj??i∣j∣(n?1)=(n?1)∑?ai?×bj????=???k∣0=0∑?i∣j=k∑?ai?×bj?,k∣1=1∑?i∣j=k∑?ai?×bj?,k∣2=2∑?i∣j=k∑?ai?×bj??k∣(n?1)=(n?1)∑?i∣j=k∑?ai?×bj????=FWT(A∣B)?

---

至此，我們得到了與 FFT 類似的 FWT 的所有定義與性質，

根據 FFT 的流程，我們需要定義 IFWT，即逆沃爾什變換，

我們定義 I F W T ( F W T ( A ) ) = A IFWT(FWT(A))=A IFWT(FWT(A))=A，

則：
I F W T ( A ) = { ( I F W T ( A 0 ) , I F W T ( A 1 ) ? I F W T ( A 0 ) ) n > 1 A n = 0 IFWT(A)=\begin{cases}(IFWT(A_0),IFWT(A_1)-IFWT(A_0))&n>1\\\ A&n=0\end{cases} IFWT(A)={(IFWT(A0?),IFWT(A1?)?IFWT(A0?)) A?n>1n=0?
考慮證明：

根據 性質11.1
∵ F W T ( A ) 0 = F W T ( A 0 ) ∴ A 0 = IFWT ? ( F W T ( A 0 ) ) = IFWT ? ( F W T ( A ) 0 ) ∵ F W T ( A ) 1 = F W T ( A 0 ) + F W T ( A 1 ) ∴ A 1 = I F W T ( F W T ( A 1 ) ) = I F W T ( F W T ( A ) 1 ? F W T ( A ) 0 ) ∴ I F W T ( A ) = I F W T ( ( A 0 , A 1 ) ) = ( I F W T ( A 0 ) , I F W T ( A 1 ) ? I F W T ( A 0 ) ) \begin{aligned}&\\&\because F W T(A)_{0}=F W T\left(A_{0}\right)\\&\therefore A_{0}=\operatorname{IFWT}\left(F W T\left(A_{0}\right)\right)=\operatorname{IFWT}\left(F W T(A)_{0}\right)\\&\because F W T(A)_{1}=F W T\left(A_{0}\right)+F W T\left(A_{1}\right)\\&\therefore A_{1}=I FW T\left(F W T\left(A_{1}\right)\right)=I FW T\left(F W T(A)_{1}-F W T(A)_{0}\right)\\& \therefore IFWT(A)=IFWT((A_0, A_1))=(IFWT(A_0),IFWT(A_1)-IFWT(A_0))\end{aligned} ?∵FWT(A)0?=FWT(A0?)∴A0?=IFWT(FWT(A0?))=IFWT(FWT(A)0?)∵FWT(A)1?=FWT(A0?)+FWT(A1?)∴A1?=IFWT(FWT(A1?))=IFWT(FWT(A)1??FWT(A)0?)∴IFWT(A)=IFWT((A0?,A1?))=(IFWT(A0?),IFWT(A1?)?IFWT(A0?))?
其實看起來非常的形象，因為 IFWT 是 FWT 的逆運算，所以公式逆過來， + + + 變成 ? - ? 就行了，

顯然FWT與IFWT運算基本相同，實作的時候寫成一個函式即可：

inline void OR(int *f, int x = 1) {
	for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
		for (int i = 0; i < n; i += o)
			for (int j = 0; j < k; ++ j)
				f[i + j + k] += f[i + j] * x;
}

0x12 與（ and \text{and} and）卷積

同理，我們可以得到與卷積的定義式：
F W T ( A ) [ k ] = ∑ i & k = k a i FWT(A)[k]=\sum_{i\&k=k}a_i FWT(A)[k]=i&k=k∑?ai?
以及 FWT 的遞推式：
F W T ( A ) = { ( F W T ( A 0 ) + F W T ( A 1 ) , F W T ( A 1 ) ) n > 1 A n = 0 FWT(A)=\begin{cases}(FWT(A_0)+FWT(A_1),FWT(A_1))&n>1\\\ A &n=0\end{cases} FWT(A)={(FWT(A0?)+FWT(A1?),FWT(A1?)) A?n>1n=0?

證明同或卷積，序列 A A A 的右半部分任意一個下標 & \& & 左半部分即首位為 0 0 0 的數，得到的結果一定在 A A A 的左半部分，故 A 1 A_1 A1? 對 左半部分有貢獻，且一定對自己所在的右半部分有貢獻，

性質12.1： F W T ( A & B ) = F W T ( A ) × F W T ( B ) FWT(A\&B)=FWT(A)\times FWT(B) FWT

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262476.html

標籤：其他

上一篇：P7385 「EZEC-6」跳一跳 題解

下一篇：Win鍵失效解決方案+鍵盤檢測器