Description:


这是一道模板题。
给你两个多项式,请输出乘起来后的多项式。

Input:


第一行两个整数 n 和 m,分别表示两个多项式的次数。
第二行 n+1 个整数,分别表示第一个多项式的 0 到 n 次项前的系数。
第三行 m+1 个整数,分别表示第一个多项式的 0 到 m 次项前的系数。

Output:


一行 n+m+1 个整数,分别表示乘起来后的多项式的 0 到 n+m 次项前的系数。

Sample Input:


Sample Output:


Explanation:


(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3(1+2x)⋅(1+2x+x2)=1+4x+5x2+2x3。

题解:


一道FFT的模板题,刚开始学,代码有瑕疵欢迎吐槽。
推荐一篇讲FFT的好文章

递归版本:

非递归版本:


2017.06.06
补充一下NTT的做法。
\(g_n = 3^{\frac {p-1}{n}}\) 代替 \(w_n\) 就可以了。