一个蒟蒻对FFT的理解（蒟蒻也能看懂的FFT）

建议同学们先自学一下“复数（虚数）”的性质、运算等知识，不然看这篇文章有很大概率看不懂。

---

 前言

作为一个典型的蒟蒻，别人的博客都看不懂，只好自己写一篇了。

膜拜机房大佬 HY

---

 一. FFT是蛤？？

FFT (快速傅里叶变换) 的作用时再 O(nlogn) 时间算出多项式乘法的一个特别神奇的算法。

大家平时码的多项式乘法都是 O(n^2) 的吧

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int n,m,a[10005],b[10005],c[20005];
 6 
 7 int main(){
 8     scanf("%d%d",&n,&m);
 9     for(int i=0;i<n;i++)scanf("%d",a+i);
10     for(int i=0;i<m;i++)scanf("%d",b+i);
11     for(int i=0;i<n;i++)
12     for(int j=0;j<m;j++)c[i+j]+=a[i]*b[j];
13     for(int i=0;i<n+m-1;i++)
14         printf("%d ",c[i]);
15 }

 但这个算法并不能解决什么问题。

n<=100000 恭喜你，你成功TLE了，这是就要用到FFT了！！（是不是很激动？）

---

 二. 算法思想

相信大家十分想知道这神奇的算法是怎么工作的。我们平时表达多项式的方法是系数表示法，而我们要把这个多项式换成另一个神奇的表达方法——点值表示法。这种神奇的表示法可以在 O(n) 的时间内算出多项式乘法，可是很遗憾，要想让这两种表示法互相转化任是需要 O(n^2) 的时间，而FFT的核心就是在 O(nlogn) 的时间内实现转换。

---

 三. 系数表示法和点值表示法

系数表示法

就是用一个多项式的各个项的系数表示这个多项式，也就是我们平时所用的表示法。例如，我们可以这样表示：

f(x)=a₀+a₁x₁+a₂x₂+..+a_nx_n⇔f(x)={a₀,a₁,a₂,..,a_n}

这就像是我们用数组存一个多项式一样

 点值表示法

就是把这个多项式理解成一个函数，用这个函数上的若干个点的坐标来描述这个多项式。（两点确定一条直线，三点确定一条抛物线…同理n+1个点确定一个n次函数）

因此表示成这样：（注意：x[0]->x[n]是n+1个点）

f(x)=a0+a1x+a2x2+..+anxn⇔f(x)={(x0,y0),(x1,y1),(x2,y2),..,(xn,yn)}

 为什么n+1个确定的点能确定一个唯一的多项式呢？你可以尝试着把这n+1个点的值分别代入多项式中：

 如图，我们把相应的 x 与 y 的值代入，就能的到n+1个方程，也就能解出n+1个位置数，即数组 a，这样也就确定了一个多项式。

---

 四. 点值表达式的乘法

现在，考虑这样一个问题，如果我有两个用点值表示的多项式，如何表示它们两个多项式的乘积呢？

我们令这两个点值表达式的 x 值相等，则会有一组唯一确定的 y 值。

f(x)={(x0,f(x0)),(x1,f(x1)),(x2,f(x2)),..,(xn,f(xn))}

g(x)={(x0,g(x0)),(x1,g(x1)),(x2,g(x2)),..,(xn,g(xn))}

F(x)={(x0,f(x1)*g(x0)),(x1,f(x1)*g(x1)),(x2,f(x2)*g(x2)),..,(xn,f(xn)*g(xn))}

结果F(x)=f(x)×g(x)，那么就有F(x0)=f(x0)∗g(x0)（x0x0为任意数）。

思考一下，很容易得出，如果 x 的取值相同，结果多项式的值就是两个因式的值的乘积

也就是说，如果我把两个函数的点值表示法中的 x 值相同的点的 y 值乘在一起就是它们的乘积（新函数）的点值表示。 

这就可以O(n)计算多项式乘法。

---

五. 复数

我们把形如a+bi（a,b均为实数）的数称为复数，其中a称为实部，b称为虚部，i称为虚数单位。当虚部等于零时，这个复数可以视为实数；当z的虚部不等于零时，实部等于零时，常称z为纯虚数。　　　————百度百科