给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$。求出 $F(x)$ 和 $G(x)$ 的卷积。
通过 DFT 和 IDFT 两个过程，实现多项式由系数表示法 → 点值表示法 → 系数表示法。利用单位根的性质实现奇偶分治过程，时间复杂度 $O(n\log n)$。其中递归的分治过程时空消耗较大，通过蝴蝶变换找到各项系数（点值）分治后的位置，直接往上迭代，实现优化。
FFT 模板题
P1919 【模板】A*B Problem升级版（FFT快速傅里叶）
给定正整数 $a,b$，求 $a\times b$，（$1\le a,b\le 10^{1000000}$）
任一 $n$ 位十进制正整数 $k$ 可以用多项式形式表示 $k=\overline{a_{n-1}a_{n-2}\cdots a_2a_1a_0}=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}(x=10)$，这样一来，两数相乘即可转化为多项式相乘的问题，套用 FFT 模板即可，时间复杂度 $O(n\log n)$（$n$ 为位数）。
FFT 模板题
给出 $n$ 个数 $q_1,q_2,\cdots,q_n$，定义 $$ F_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i\times q_j}{(i-j)^2}\\ E_i=\frac{F_i}{q_i} $$ 对 $1\le i\le n$，求 $E_i$ 的值。
对题目式子进行化简，可得 $$ E_j=\sum_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i}{(i-j)^2} $$ 令 $a_i=q_i,b_i=\frac{1}{i^2},a_0=b_0=0,$ $$ E_j=\sum_{i=0}^{j}a[i]b[j-i]-\sum_{i=j}^{n}a[i]b[i-j] $$ 注意到左边已化成卷积形式，现对右边进行转化， $$ \sum_{i=j}^{n}a[i]b[i-j]=\sum_{i=0}^{n-j}a[i+j]b[i] $$ 令 $c[i]=a[n-i]$ （翻转变换），得 $$ \sum_{i=0}^{n-j}c[n-i-j]b[i] $$ 令 $t=n-j$，得 $$ \sum_{i=0}^{t}c[t-i]b[i] $$ 至此，右边也化为了卷积形式。
令 $f(x)=\sum_{i=0}^na_ix^i,g(x)=\sum_{i=0}^nb_ix^i,h(x)=\sum_{i=0}^nc_ix^i$，答案即为 $E_j=[x^j](f(x)g(x))-[x^{n-j}](g(x)h(x))$。
用 FFT 做多项式乘法即可，时间复杂度 $O(n\log n)$
主要考察推式子能力，将式子转化为卷积形式，再套用 FFT 加速多项式乘法。