这东西对初中生挺友好的。
引入
设 \(F(x)=\sum_{i=0}^n{a_ix^i},G(x)=\sum_{i=0}^m{b_i} x^i\)。显然，如果要求这两个多项式的积，需要 \(\mathcal O(n^2)\) 的复杂度。但 \(\text{FFT}\) 能通过 \(\mathcal O(n\log n)\) 的复杂度求出。
前置知识
- 复数
形如 \(z=a+bi(a,b\in \mathbb R)\) 的数为复数，其中 \(a\) 为实部，\(b\) 为虚部。如果把 \(a,b\) 分别看作平面直角坐标系中的 \(x,y\) 轴，则平面直角坐标系里的每个点都对应了一个复数，这个平面叫复平面。
- 三角函数
坐标系中任意一点 \((x,y)\) 与 \(x\) 轴所成的夹角记为 \(\theta\)。则
\[\sin \theta=\frac{y}{\sqrt{x^2+y^2}} \]\[\cos \theta=\frac{x}{\sqrt{x^2+y^2}} \]欧拉公式：\(e^{i\theta}=\cos\theta +i\sin\theta\)
- 幅角
简单来说，\(180\degree=\pi,360\degree = 2\pi\)。
- 单位根
复平面中，以原点为圆心，\(1\) 为半径的圆称为单位圆。\(n\) 阶单位根是内接单位圆的 \(n\) 边形的 \(n\) 个顶点，满足 \(n\) 边形有一个顶点为 \((1,0)\)。可以发现，这 \(n\) 个点对应的复数恰好是方程 \(z^n=1\) 的 \(n\) 个解。
由相关知识得出这 \(n\) 个单位根可以写成：\(z_k=\cos \frac{2\pi k}{n}+i\sin\)
FFT
设函数 \(F(x)=\sum_{i=0}^n{a_ix^n}\)，则这个函数可以用 \(n+1\) 个点表示出来。例如一次函数需要两个点表示，二次函数要三个。感性理解就是一个点能确定一个系数。
如果我们要求两个多项式 \(F(x)=\sum_{i=0}^n{a_ix^i},G(x)=\sum_{i=0}^m{b_i} x^i\) 的积 \(T(x)=\sum_{i=0}^{n+m}c_ix^i\)，显然用点值表示法相乘只需要 \(O(n)\) 的复杂度。所以考虑怎么取点。
标签：ix,sum,FFT,复数,平面,theta From： https://www.cnblogs.com/kbzcz/p/18077264