题目链接
\(FFT\)即快速傅里叶变换，用于加速多项式乘法。
如果暴力做卷积的话就是一个多项式的每个单项式去乘另一个多项式然后加起来，时间复杂度为\(O(n^2)\)。
\(FFT\)算法基本思想是把系数表达式转换成点值表达式，求出卷积的点值表达式，再转换回系数表达式。
何为点值表达式？
把多项式看成一个函数，比如\(n\)次多项式\(F\)可以看成一个\(n\)次函数\(F(x)=a_0+a_1x+a_2x^2+\cdots +a_nx^n\)
众所周知，知道\(n\)次函数上\(n+1\)个点的坐标一定可以求出这个\(n\)次函数的解析式。
用我们学过的知识一次函数、二次函数都可以验证。
硬要扩展到任意次函数的话也好解释，可以得到\(n+1\)个方程，用高斯消元就能解出来，当然肯定不会在\(FFT\)算法里出现，因为算法的目的是加速。
系数表达式->点值表达式的过程叫\(DFT\)，点值表达式->系数表达式的过程叫\(IDFT\)。
先讲\(DFT\)。
怎么系数->点值？
代\(n\)个点是最直接的办法，但显然求一个点的值就是\(O(n)\)的，总时间复杂度为\(O(n^2)\)
这里要引入单位复数根概念。
【总结】对FFT的理解 / 【洛谷 P3803】 【模板】多项式乘法（FFT）
原文：https://www.cnblogs.com/Qihoo360/p/10364338.html