FFT简介用于求卷积（\(a,b\)已知）：\[\sum_{i=0}^na_ib_{n-i}\]或者多项式乘法（\(A(x),B(x)\)已知）：\[C(x)=A(x)B(x)\]\(A(x)=\sum_{i=0}^{n}a_ix^i\\B(x)=\sum_{i=0}^{m}b_ix^i\)可见\(C(x)\)是\(n+m\)次多项式。如果我们把卷积的\(a_i,b_i\)看成多项式的系数，卷积