多项式学习笔记

做多项式题就像嗑药，出多项式题就像贩毒。——FJOI某知名选手

（这也是我选择这张头图的一个原因）

参考资料 ：

mertrshower_y’s blog

快速傅里叶变换(Fast Fourier Transform)

快速傅里叶变换，指利用计算机高效地计算离散傅里叶变换的方法，简称FFT。

离散傅里叶变换(Discrete Fourier Transform)

这是一种时间复杂度为 $O(n \log n)$ 的多项式系数表示法转点值表示法的方法，简称 $DFT$。

我们有这个多项式 ：

$$A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots +a_nx^n$$

然后我们按照奇偶性质，以上边那个多项式为原型得到一下两个多项式 ：

$$A_1(x) = a_0 + a_2x + a_4x^2 + \cdots + a_nx^{ \frac{n}{2}}$$ $$A_2(x) = a_1 + a_3x + a_5x^2 + \cdots + a_n-1x^{\frac{n}{2}-1}$$

于是我们显然可以使用 $A_1$ 和 $A_2$ 来表示 $A$ ：

$$A(x) = A_1(x^2) + xA_2(x^2)$$

我们引入 单位根 的概念　：　

满足 $x^n = 1$ 的 $x$ 在 复数域 上的 $n$ 个解，记为 $w_n$ ，称为单位根。

• $w_n^1$ 称作 $n$ 次单位根
• $w_n^k = (w_n^1)^k$
• $w_n^k = e^{\frac{2 \pi ki}{n}} = \cos \frac{2k\pi}{n} + \sin \frac{2k\pi}{n}i $ （欧拉公式）

于是单位根有许多便于运算的性质 ：

• $w_n^k = w_{tn}^{tk} $
• $w_n^k = w_n^{k \% n} $
• $w_n^{k + \frac{n}{2}} = -w_n^k $

（）