\(Fast Fourier Transform(FFT)\) 在 oi 中的主要作用是用来求“卷积”（多项式乘法）。
可将时间复杂度降为 \(O(n \log_2n)\)
3步快速求出多项式乘积：
- 由系数表示法转换成点值表示法。
- 求两个多项式的乘积。
- 将点值表示法转换成系数表示法。
假设A的点值表达式为\({(x_0,y_0),(x_1,y_1),(x_2,y_2)...}\)
假设B的点值表达式为\({(x_0,y_0^1),(x_1,y_1^1),(x_2,y_2^1)...}\)
那么C的点值表达式为\({(x_0,y_0y_0^1),(x_1,y_1y_1^1),(x_2,y_2y_2^1)...}\)
接下来分析1.
将一个 \(n\) 次项的多项式分成奇函数，偶函数两个部分。
接下来考虑如何选点获得点值。
对于一个奇函数，求出一组 \((x,y)\) 的值，同时可得到 \((-x,-y)\)
对于一个偶函数，求出一组 \((x,y)\) 的值，同时可得到 \((-x,y)\)
所以我们可以通过函数的性质，求出一个点的坐标就能得到两个点的坐标。一个 \(d\) 阶的多项式需要 \(d+1\) 个点，所以只需要求 \((d+1)/2\) 次点即可。