嗯哼。。。。好了继续
然后是一个很重要的东西
单位根
首先这是个圆（废话），它的半径是一，所以称为单位圆
复数满足称作是次单位根
如当是，w可以为：,,.
在平面上表示的话……算了吧
真香
即将圆等分成3份
n次单位根就是将单位圆等分成n份
一下记第k个n次单位根为（从1开始，逆时针第k+1个为）
单位根的特殊性质可以保证这n-1个复数各不相等
单位根还有一些性质：
(高清无码）
这两条性质带进下面的欧拉公式就可以算出来了
对了忘记说怎么算了，用我们强dark的欧拉公式可以解决：
欧拉公式：
因为c++是用弧度制所以我下面也用弧度制表示(即表示,表示)
-----------------------------------------------------------------------------------分鸽------------------------------------------------------------------------------------
现在可以开始讲了
（当当当当）
还记得这个东东吗，不过这只是多项式的一种表达方式，叫作：系数表达法
还有种表达法叫：
点值表达法
设
我们知道，n+1个互不相同的点就可以确定一个n次函数，对分别求值就可以得到,那么称为door项式的点表示法
---------------------------------------------------------------------------啦啦啦啦啦啦啦啦（还是分鸽）-----------------------------------------------------------
为蛤要用点值表示法呢？
因为我们现，系数表示法算多项式乘法的时间复杂度是,而通过点值表示法我们可以发现两个多项式,同时取点时，得到的是和,即取到的点分别为而会取到的点为（显而易见）。那么计算的点表达式的时间复杂度就是的。
我知道了o(*^▽^*)┛，就是把值直接带进去，然后就可以线性求出来了，干嘛要啊？
但是……你要带个值进去才可以弄出点表示法呀。
.........那不还是的吗，哪来的...
有办法让这个过程变成,别急，马上就要讲了。
-------------------------------------------------------------------------分鸽（下面就不解释了）------------------------------------------------------------------------
FFT就是将系数表示法转化成点值表示法相乘，再由点值表示法转化为系数表示法的过程，第一个过程叫做求值(DFT)，第二个过程叫做插值(IDFT)——摘自一位darklao的blog
首先是求值DFT
(高清无码++）
再次把单位根的性质搬出来。。
想要求出一个多项式的点值表示法，需要选出个数分别带入到多项式里面，带入一个数的复杂度是的，那么总复杂度就是的，因为单位根有上面两个优美的性质，所以我们尝试可以取次单位根组成，看看能不能加速我们的运算....
设为X的指数为偶数次的，为X的指数为奇数次的
可得
(这里n为2^k,不够就补齐，反正系数为0，不影响）
然后我们发现和是两个长度为原来一半的多项式,然后就可以分治了
把单位根带进去
由上面的性质可化简得
和递归进去算就行了，然后就先把算出来，然后k次幂就行了
儿当就不管用了，因为单位根出现了重复
先把式子列出来
用上面的性质化简一下就变成
然后就可以愉快地把系数表达式转换为点值表达式
||||||好了，求值（DFT）搞定了，下面是插值。||||||
-------------------------------------------------------------分鸽线（真香*2）--------------------------------------------------------------------
插值只要将所有的变成,就是将虚部取反，再将结果除以长度（即n），至于为甚，我们可以这样考虑。
我们可以考虑把原来的要做的操作用矩阵的形式表现出来：
这是DFT,我们要求的IDFT，我们已知了左边和右边的两个矩阵，要求中间那个，就相当于是求最左边那个矩阵的逆，然后乘右边那个矩阵。它的逆就是
这个手推一下就行了，是因为带入了n个值。然后发现IDFT和DFT差不多
(下面的推导要用到 和 )
然后就可以了。
