具体步骤：
1、补0：在两个多项式最前面补0，得到两个 $2n$ 次多项式，设系数向量分别为 $v_1$ 和 $v_2$。
2、求值：用FFT计算 $f_1 = DFT(v_1)$ 和 $f_2=DFT(v_2)$。这里得到的 $f_1$ 和 $f_2$ 分别是两个输入多项式在 $2n$ 次单位根处的各个取值（即点值表示）
3、乘法：把两个向量 $f_1$ 和 $f_2$ 的每一维对应相乘，得到向量 $f$。它对应输入多项式乘积的点值表示。
4、插值：用FFT计算 $v=IDFT(f)$，其实 $v$ 就是乘积的系数向量
（详细的过程可以去洛谷），直接上代码吧
给定一个n次多项式F(x)，和一个m次多项式G(x)。请求出F(x)和G(x)的卷积。
输入格式：
第一行2个正整数n,m。
接下来一行n+1个数字，从低到高表示F(x)的系数。
接下来一行m+1个数字，从低到高表示G(x))的系数。
输出格式：
一行n+m+1个数字，从低到高表示F(x)∗G(x)的系数。
#include <complex>
#include <cmath>
#include <vector>
#include<iostream>
using namespace std; const long double PI = acos(0.0) * 2.0; typedef complex<double> CD; // Cooley-Tukey的FFT算法，迭代实现。inverse = false时计算逆FFT
inline void FFT(vector<CD> &a, bool inverse) {
int n = a.size();
// 原地快速bit reversal
for(int i = , j = ; i < n; i++) {
if(j > i) swap(a[i], a[j]);
int k = n;
while(j & (k >>= )) j &= ~k;
j |= k;
} double pi = inverse ? -PI : PI;
for(int step = ; step < n; step <<= ) {
// 把每相邻两个“step点DFT”通过一系列蝴蝶操作合并为一个“2*step点DFT”
double alpha = pi / step;
// 为求高效，我们并不是依次执行各个完整的DFT合并，而是枚举下标k
// 对于一个下标k，执行所有DFT合并中该下标对应的蝴蝶操作，即通过E[k]和O[k]计算X[k]
// 蝴蝶操作参考：http://en.wikipedia.org/wiki/Butterfly_diagram
for(int k = ; k < step; k++) {
// 计算omega^k. 这个方法效率低，但如果用每次乘omega的方法递推会有精度问题。
// 有更快更精确的递推方法，为了清晰起见这里略去
CD omegak = exp(CD(, alpha*k));
for(int Ek = k; Ek < n; Ek += step << ) { // Ek是某次DFT合并中E[k]在原始序列中的下标
int Ok = Ek + step; // Ok是该DFT合并中O[k]在原始序列中的下标
CD t = omegak * a[Ok]; // 蝴蝶操作：x1 * omega^k
a[Ok] = a[Ek] - t; // 蝴蝶操作：y1 = x0 - t
a[Ek] += t; // 蝴蝶操作：y0 = x0 + t
}
}
} if(inverse)
for(int i = ; i < n; i++) a[i] /= n;
} // 用FFT实现的快速多项式乘法
inline vector<double> operator * (const vector<double>& v1, const vector<double>& v2) {
int s1 = v1.size(), s2 = v2.size(), S = ;
while(S < s1 + s2) S <<= ;
vector<CD> a(S,), b(S,); // 把FFT的输入长度补成2的幂，不小于v1和v2的长度之和
for(int i = ; i < s1; i++) a[i] = v1[i];
FFT(a, false);
for(int i = ; i < s2; i++) b[i] = v2[i];
FFT(b, false);
for(int i = ; i < S; i++) a[i] *= b[i];
FFT(a, true);
vector<double> res(s1 + s2 - );
for(int i = ; i < s1 + s2 - ; i++) res[i] = a[i].real(); // 虚部均为0
return res;
} /////////// 题目相关
#include<cstdio>
#include<cstring> vector<double>a, b, ans; int main()
{
int n, m;
scanf("%d%d", &n, &m); for(int i = ;i <= n+;i++)
{
double tmp;
scanf("%lf", &tmp);
a.push_back(tmp);
}
for(int i = ;i <= m+;i++)
{
double tmp;
scanf("%lf", &tmp);
b.push_back(tmp);
} ans = a * b;
for(int i = ;i <= n+m;i++)
printf("%d ", (int)(ans[i] + 0.5)); return ;
}
NTT算法流程与FFT几乎一样，区别在于FTT使用n次单位根插值，NTT使用原根的次方进行插值。NTT都是整数运算，速度较快，且不会出现精度不够。
原根的定义
设 $m$ 是正整数，$a$ 是整数，若 $a$ 模$m$ 的阶等于 $\phi(m)$，则称 $a$ 为模 $m$ 的一个原根
为什么可以用原根代替单位根呢？因为它具有和单位根相同的性质。
定理：若 $P$ 为素数假设 $g$ 为 $P$的原根，那么 $g^i \equiv \ P(1 < g < P, \ 0 < i < P)$ 的结果两两不同
（这是群论里面很简单的结论，不知道的自己看书去
如何求一个质数的原根呢？
可以证明满足 $g^r \equiv 1(mod \ P)$ 的最小的 $r$ 一定是 $p-1$的约数（因为群阶为 $p-1$），对于质数 $p$，质因数分解 $p-1$ ，若 $g^{\frac{p-1}{n}} \neq 1(mod \ p)$ 恒成立，则 $g$ 为 $p$ 的原根
#include<bits/stdc++.h>
#define rg register
using namespace std; typedef long long ll;
const int mod=,g=;
const int maxn = 1e6 + ; inline int qpow(int x,int k)
{
int ans=;
while(k)
{
if(k&)
ans=(ll)ans*x%mod;
x=(ll)x*x%mod,k>>=;
}
return ans;
} inline int module(int x,int y)
{
x+=y;
if(x>=mod)
x-=mod;
return x;
} int rev[*maxn];
inline void NTT(int*t,int lim,int type)
{
for(rg int i=;i<lim;++i)
if(i<rev[i])
swap(t[i],t[rev[i]]);
for(rg int i=;i<lim;i<<=)
{
int gn=qpow(g,(mod-)/(i<<));
if(type==-)
gn=qpow(gn,mod-);
for(rg int j=;j<lim;j+=(i<<))
{
int gi=;
for(rg int k=;k<i;++k,gi=(ll)gi*gn%mod)
{
int x=t[j+k],y=(ll)gi*t[j+i+k]%mod;
t[j+k]=module(x,y);
t[j+i+k]=module(x,mod-y);
}
}
}
if(type==-)
{
int inv=qpow(lim,mod-);
for(rg int i=;i<lim;++i)
t[i]=(ll)t[i]*inv%mod;
}
} int X[*maxn],Y[*maxn];
inline void mul(int*x, int*y, int n, int m)
{
memset(X,,sizeof(X));
memset(Y,,sizeof(Y));
int lim = , L = ; //L=0必须写，局部变量默认值很可能不是0
while(lim <= n + m) lim <<= , L++; //lim为大于(n+m)的2的幂，所以最多需要4倍空间
for(int i = ; i < lim; i++) rev[i] = (rev[i >> ] >> ) | ((i & ) << (L - ));
for(rg int i=;i<lim;++i) X[i]=x[i],Y[i]=y[i];
NTT(X,lim,);
NTT(Y,lim,);
for(rg int i=;i<lim;++i) X[i]=(ll)X[i]*Y[i]%mod;
NTT(X,lim,-);
for(rg int i=;i<lim;++i) x[i]=X[i];
} int n, m;
int a[*maxn], b[*maxn]; int main()
{
scanf("%d%d", &n, &m);
for(int i = ;i <= n;i++) scanf("%d", &a[i]);
for(int i = ;i <= m;i++) scanf("%d", &b[i]);
mul(a, b, n, m);
for(int i = ;i <= n+m;i++) printf("%d ", a[i]); return ;
}
FFT测评记录：
NTT测评记录：
参考链接：