多项式之 FFT
引入
给你两个多项式 \(F(x),G(x)\)，求 \(FG(x)=\sum\limits_{y=0}^{x}{F(y)G(x-y)}\) (即 \(F\times G\))。
转化
因为直接求两个多项式的乘积有一些困难，所以要考虑转化。
一个比较显然的思路是把这两个多项式看成两个函数，然后求函数的乘积 (废话)。
点值表示法
发现平时在求一次函数的时候经常使用两个点代入求值，这也就是说过这两个点的一次函数是唯一确定的。
于是我们猜想 \(n+1\) 个点可以唯一确定一个 \(n\) 次函数 证明。