某知名选手：出多项式题的人就像在贩毒，做多项式的人就像在嗑药。
一直就想写关于嗑药的内容了，但是由于嗑药所需要的时间很久，而且我没有大块的时间来写一篇真正入门的东西，所以一直咕咕咕。
直到现在，为了自我复习整理一遍思路，写了一篇真正入门的FFT教程。
话不多说，直接进入正题。
一.所需前置芝士
1.多项式是啥？
形如$f(x)=ax^4+bx^3+cx^2+dx+e$这样的式子，即：$\sum_{i=0}^{n}a_ix^i$叫做多项式。
定义：最高次项为n的多项式叫做n次多项式。
推论：由于常数项的存在，n次多项式最多有(n+1)项。
2.复数是啥？
正常高中所有的知识都是在实数的基础下尽心运算，但在算法中仅靠实数这些数远远不够。无法达到算法的目的。因此引入数域最大的复数。（注意，复数就是所说的虚数）。
复数的例子：实数中无法表示$\sqrt{-1}$，而这个数在复数中是真实存在的。记作$i$；即：$i^2=-1$
设a,b是实数，那么形如$a+ib$的数叫复数。其中$i$被称为虚数单位，复数域是目前已知最大的域。
在复平面中，x代表实数，y轴（除原点外的点）代表虚数，从原点(0,0)到(a,b)的向量表示复数$a+bi$
模长：从原点(0,0)到点(a,b)的距离，即$\sqrt{a^2+b^2}$
原文：https://www.cnblogs.com/kamimxr/p/12667301.html