给定向量： a=(a0,a1,...,an−1) ， b=(b0,b1,...,bn−1)

向量和： a+b=(a0+b0,a1+b1,...,an−1+bn−1) 数量积（内积、点积）： a⋅b=a0b0+a1b1+...+an−1bn−1 卷积： a⊗b=(c0,c1,...,c2n−2) ，其中 ck=∑i+j=k(aibj)

例如： cn−1=a0bn−1+a1bn−2+...+an−2b1+an−1b0

卷积的最典型的应用就是多项式乘法（多项式乘法就是求卷积）。以下就用多项式乘法来描述、举例卷积与DFT。

对于多项式 A(x) ，系数为 ai ,设最高非零系数为 ak ，则其次数就是 k ，记作degree(A)=k。任何大于 k 的整数都是A(x)的次数界。

多项式的系数表达方式： A(x)=a0+a1x+a2x2+...+an−1xn−1=∑n−1i=0ajxj （次数界为 n ）。 则多项式的系数向量即为a=(a0,a1,...,an−1)。 多项式的点值表达方式： {(x0,y0),(x1,y1),...,(xn−1,yn−1)} ，其中 xk 各不相同， yk=A(xk) 。

离散傅里叶变换（Discrete Fourier Transform，DFT）。在信号处理很重要的一个东西，这里物理意义以及其他应用暂不予理睬。在多项式中，DFT就是系数表式转换成点值表示的过程。

快速傅里叶变换（Fast Fourier Transformation，FFT）：快速计算DFT的算法，能够在 O(nlogn) 的时间里完成DFT。FFT只是快速的求DFT的方法罢了，不是一个新的概念。 在ACM-ICPC竞赛中, FFT算法常被用来为多项式乘法加速。FFT与其逆变换IFFT类似，稍微加几行代码。

求FFT要用到复数。一个简单的模板：

递归实现FFT模板：来源

非递归实现。模板：（来源忘了）