既然是第一篇题解,那一定就要足够的炫酷。。。
FFT(Fast Fourier Transformation),中文名快速傅里叶变换,是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。
朴素高精度乘法的时间为O(n^2),但FFT只需O(nlog^2n)
核心在于系数与点值的转换。
接下来就是模板了。
最好手写complex…
#include<cstdio>
#include<cstring>
#include<cmath>
#include<...