▎前言
小编相当的菜，这篇博客难度稍高，所以有些可能不会带有证明，博客中更多的是定义。
我们将要学到的东西：
- 复数
- 暴力多项式乘法
- DFT
当然，小编之前就已经写过一篇博客了，主要讲的就是基础多项式，如果你已经会了下面的内容就无需学了，否则请进入传送门。
- 环和域
- 多项式
- 卷积
- 多项式乘法
- 多项式点值表示
- 多项式的根
- 单位根
▎复数
☞『引入』
其实小编早就应该讲复数了，但是上次忘了讲，那么这次一定要补上，好了，切入正题：
如果你信誓旦旦的在初中卷子上不判断根号下（√）的数是否是负数，那么你极有可能会被老师扇两巴掌，因为这是初中要注意的一大重点。
那么问题来了，究竟有没有诸如√-1这种数呢？其实是有的，初中阶段只会告诉你实数是什么，却不会告诉你还有诸如√-1这样的虚数（顾名思义，不存在的数）。
如果你是第一次见复数，那么你可能先想到的是单数和复数，其实不是这样的。
☞『定义』
我们把形如z=a+bi（a,b均为实数）的数称为复数，其中a称为实部，b称为虚部，i称为虚数单位。当z的虚部等于零时，常称z为实数；当z的虚部不等于零时，实部等于零时，常称z为纯虚数。复数域是实数域的代数闭包，即任何复系数多项式在复数域中总有根。 复数是由意大利米兰学者卡当在十六世纪首次引入，经过达朗贝尔、棣莫弗、欧拉、高斯等人的工作，此概念逐渐为数学家所接受。（copy自百度）
其实就是实数与虚数的统称啦。
☞『表示』
复数的表示字母是z，那么一个复数z可以表示为z=ai+b，其中a，b属于实数，i属于虚数，那么a称为虚部，b称为实部，i称为虚数单位。
例如i可以满足i2=1。
☞『运算』
复数和向量不同。
复数的运算和实数几乎一样，支持四则运算。
▎暴力多项式乘法
☞『算法』
在之前，我们已经知道了系数表示法和点值表示法的区别，假设有两个多项式分别长这样：
那么这两个多项式乘起来看着就心烦，那么怎么办呢？再看看点值表示法怎么样吧：
f(x)={(x0,f(x0),(x1,f(x1),(x2,f(x2),(x3,f(x3),…}
g(x)={(x0,g(x0),(x1,g(x1),(x2,g(x2),(x3,g(x3),…}
那么积是多少？
h(x)={(x0,f(x0)•g(x0),(x1,f(x1)•g(x1),(x2,f(x2)•g(x2),(x3,f(x3)•g(x3),…}
怎么样，点值表示法干题是不是爽到爆呢？
但是问题是：系数表示法如何变成点值表示法？
我们其实只需要n个数当做x带入得到f/g值即可。但是这样的做法无疑是O(n2)级别的，有时满足不了我们的需求，所以就要用到离散傅里叶变换了。
▎DFT
☞『引入』
这个算法有点不太对劲，百度介绍的好难呀。
我现在在质疑这个算法是不是处理物理的。
☞『定义』
离散傅里叶变换（DFT），是傅里叶变换在时域和频域上都呈现离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再作变换。在实际应用中通常采用快速傅里叶变换以高效计算DFT。
我猜你也看不懂，其实就是快速系数转点值表示法呗。
☞『算法核心』
在之前，我们说的n个数带入转点值中的n个数是随便找的，所以出现一些棘手的问题很正常，就比如说当遇到高次的项时总会很难算。
所以我们如果能刻意的找到一些好算的x，那么就不难算出f/g的值了。
如果我们能找到一些x满足xk=1，那么就不必每个次方都算了。
想一想1和-1绝对是，考虑虚数的话i和-i也算。
那么我们可以画上这样一个平面直角坐标系：
可是单单这么四个点显然是不够的，比如说n=8,傅里叶表示应该将这个圆平分成八份，取这样的八个点：
从（0,1）依次标号k：
那么只要求出这八个点表示的复数即可，我们记标号k的点表示的复数为ωnk，那么就有：
这里面的东西都可以算出来的。