在写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的关系啦