在寫FFT的時候，經常會遇到和生成函數的結合
一開始不是能明白，結果突然有一天頓悟了
下面就xue微談一下生成函數，卷積和FFT的關系吧
生成函數
我們經常用生成函數解決以下問題：
設 hn h n 為方程： 3∗e1+4∗e2+2∗e3+5∗e4=n 3 ∗ e 1 + 4 ∗ e 2 + 2 ∗ e 3 + 5 ∗ e 4 = n 的非負整數解得個數。
求 h0，h1，…，hn，… h 0 ， h 1 ， … ， h n ， … 的生成函數 g(x) g ( x )
解：
f1=3∗e1,f2=4∗e2,f3=2∗e3,f4=5∗e4 f 1 = 3 ∗ e 1 , f 2 = 4 ∗ e 2 , f 3 = 2 ∗ e 3 , f 4 = 5 ∗ e 4
那麼 f1 f 1 是3的倍數， f2 f 2 是4的倍數， f3 f 3 是2的倍數， f4 f 4 是5的倍數
g(x)=(1+x3+x6+...)(1+x4+x8+...)(1+x2+x4+...)(1+x5+x10+...) g ( x ) = ( 1 + x 3 + x 6 + . . . ) ( 1 + x 4 + x 8 + . . . ) ( 1 + x 2 + x 4 + . . . ) ( 1 + x 5 + x 1 0 + . . . )
這樣我們就可以畫柿子直接計算答案了
但是如果我們從題面中提取不到元素的資訊，隻能通過輸入得到而不能直接畫柿子
這種情況下我們隻能計算若幹個多項式的乘法
那麼我們怎麼計算多項式乘法呢？ 繼續往下看↓
卷積
之前在淺談數論中簡單的提到了卷積中的一類：狄利克雷卷積
實際上，普通的卷積是這樣的：
Cn=∑ni=1aibn−i C n = ∑ i = 1 n a i b n − i
這就有點像豎式乘法：
a:
b:
//----------------------------------
*4 *3 *2 *1
*4 *3 *2 *1
*4 *3 *2 *1
c: *4 *3 *2 *1
用心感受一下
狄利克雷卷積：
Cn=∑d|nadbnd C n = ∑ d | n a d b n d
上式多用于莫比烏斯反演
觀察一下，可以得到一個小規律：
a,b a , b 下标之和等于 c c 的下标
而多項式乘法也是遵循豎式乘法原則的：
A(x)=x4+3x2+2xA(x)=x4+3x2+2x
B(x)=x3+4x2+1 B ( x ) = x 3 + 4 x 2 + 1
A(x)∗B(x)=x7+4x6+3x5+15x4+8x3+3x2+2x A ( x ) ∗ B ( x ) = x 7 + 4 x 6 + 3 x 5 + 15 x 4 + 8 x 3 + 3 x 2 + 2 x
A:
B:
*1 *0 *3 *2 *0
*1 *0 *3 *2 *0
*1 *0 *3 *2 *0
A*B:
實際上，多項式乘法就是兩個函數的卷積
C(x)=A(x)∗B(x) C ( x ) = A ( x ) ∗ B ( x )
Cn=∑ni=1AiBn−i C n = ∑ i = 1 n A i B n − i
我們要是按照上面的式子計算，會有多次的乘法和加法，非常慢
是以我們要引入一個快速計算多項式乘法（即卷積）的方法
FFT
FFT，說白了就是用來快速計算卷積的
首先，想明白FFT，就需要知道多項式的表示方法
多項式還有什麼表示方法呢？
上文提到的多項式都是系數表達，然而還有一種方法點值表達
形象點來說，就是畫出多項式的圖像，用圖像上的點表示多項式
對于一個n次多項式，我們需要 n+1 n + 1 個點來确定多項式
因為一共有 n+1 n + 1 個待定的系數 (a0,a1,a2,a3...,an) ( a 0 , a 1 , a 2 , a 3 . . . , a n ) ，需要 n+1 n + 1 個方程
為了發現點值表達的性質，我們先看一個小例子：
A(x)=x2+2x−1 A ( x ) = x 2 + 2 x − 1
B(x)=x2−x+2 B ( x ) = x 2 − x + 2
C(x)=A(x)+B(x) C ( x ) = A ( x ) + B ( x )
D(x)=A(x)B(x) D ( x ) = A ( x ) B ( x )
可以發現，當x坐标相等的時候，A和B的y坐标相乘就是D的y坐标
那麼如果我們能把多項式變成點值表達，就可以用n次乘法完成卷積
然而，FFT就可以完成多項式在系數表達和點值表達之間的轉化
學妹的FFT簡單講解，感覺還不錯，dada們就當看着玩吧
假設我們都會了FFT，得到了A和B的點值表達，那麼答案就是：
for (int i=;i<=fn;i++)
A[i]=A[i]*B[i];
但是我們在答案輸出的時候，是不接受點值表達的，我們還要把點值表達轉換成系數表達
這就是FFT的逆操作：IDFT
在FFT中，我們有一個主n次機關根： ωn ω n
ωkn=e2πkin=(cos(2πkn),sin(2πkn)i) ω n k = e 2 π k i n = ( c o s ( 2 π k n ) , s i n ( 2 π k n ) i )
我們直接把A乘上 ωn ω n 的逆矩陣 ω−1nn ω n − 1 n 即可
而 ω−1n ω n − 1 就是 ωn ω n 的共轭複數
共轭複數：實數部分相等，虛數部分相反
ωn=(cos(2πn),sin(2πn)i) ω n = ( c o s ( 2 π n ) , s i n ( 2 π n ) i )
ω−1n=(cos(2πn),−sin(2πn)i) ω n − 1 = ( c o s ( 2 π n ) , − s i n ( 2 π n ) i )
以上就是生成函數，卷積和FFT的關系啦