傅里叶变换（FFT）初步

概述

傅里叶变换（FFT）是各种多项式模板算法的基础可以认为是重多省选内容中相对简单的一个

那么FFT是干什么的呢？

利用卷积思想求多项式的乘积时间复杂度O（nlogn）

回忆初中刚学多项式乘法时是不是感觉非常麻烦

例子
$$
(x^2+3x+6)(x^3+x^2+2)\=x^5+x^4+2x^2+3x^4+3x^3+6x+6x^3+6x^2+12\=(x^5)+(4x^4)+(9x^3)+(8x^2)+(6x)+(12)
$$
（观察第三行将不同次数的式子放在同一个括号里，这就是一种卷积）

将这个过程写作程序
$$
\sum_{i=0}^{n+m}f[i]*d[n+m-i]
$$