[多项式] FFT小计

引入

给出两个多项式 \(A,B\) ，计算它们相乘的结果。

我们能轻易写出 code：

for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)C[i+j]+=A[i]*B[j];

然后超时了。
FFT 是一种将多项式乘法优化成 \(O(n\log n)\) 的神仙算法。

分析

上面的式子没有任何优化空间。
什么意思呢？就是怎么乱搞都优化不了。于是我们看看天才算法是怎么搞的。

点值表示法

我们知道 \(n\) 个点确定一条 \(n-1\) 次多项式。
所以我们把多项式转到平面上。
我们随便取 \(2n+1\) 个点，先在 \(A\) 中计算出这些点，表示成 \((x,y_A)\)，然后在 \(B\) 中计算出这些点：\((x,y_B)\) ，然后我们就能很容易计算出 \(y_C=y_A\times y_B\) 。然后我们用 \(n\) 个点确定一条多项式。

天才思路！但是是不是有什么不对的地方？
计算一个点是 \(O(n)\) 的，然后有 \(n\) 个点要计算...时间复杂度 \(O(n^2)\)。

如果只是随便取点，就是低估了傅里叶的上限了。

取点

我们想想我们有没有知道一个点 \(x_1\) 的值，就能马上另一点的值呢？
我们先来看二次函数 \(f(x)=x^2\) ：
如果知道 \(f(5)=25\)，马上就能知道 \(f(-5)=25\)。
再来看看三次函数 \(f(x)=x^3\)，和二次函数一样，但是加个负号就行，说人话就是奇偶函数。

我们推广到多项式这一般形式：
\(A(x)=16x^5+22x^4+7x^3+5x^2+13x+8\)
我们把奇偶次数分开一下：

\[p=16x^5+7x^3+13x \]

\[q=22x^4+5x^2+8 \]

假设我们算出 \(x\) 点的取值为 \(p+q\) ，那么 \(-x\) 点的取值不就是 \(q-p\) 吗！

也就是说，我们现在只需要取 \(\frac{n}{2}\) 这么多点就行了。

然后能不能继续拓展？
这个看起来能递归的样子：