本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目描述
这是一道模板题。
给你两个多项式，请输出乘起来后的多项式。
输入格式
第一行两个整数 nn 和 mm，分别表示两个多项式的次数。
第二行 n+1n+1 个整数，分别表示第一个多项式的 00 到 nn 次项前的系数。
第三行 m+1m+1 个整数，分别表示第一个多项式的 00 到 mm 次项前的系数。
输出格式
一行 n+m+1n+m+1 个整数，分别表示乘起来后的多项式的 00 到 n+mn+m 次项前的系数。
样例一
input
1 2
1 2
1 2 1
output
1 4 5 2
正解：FFT
解题报告：
FFT模板题
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
typedef complex<double> C;
const int MAXN = 270000;
const double pi = acos(-1);
int n,m;
C a[MAXN],b[MAXN];
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void fft(C *a,int n,int f){
if(n==1) return ;
C wn(cos(2.0*pi/n),sin(f*2.0*pi/n)),w(1,0),t;
C a0[n>>1],a1[n>>1];
for(int i=0;i<n>>1;i++) a0[i]=a[i<<1],a1[i]=a[i<<1|1];
fft(a0,n>>1,f); fft(a1,n>>1,f);
for(int i=0;i<n>>1;i++,w*=wn) {
t=w*a1[i];
a[i]=a0[i]+t;
a[i+(n>>1)]=a0[i]-t;
}
}
inline void work(){
n=getint(); m=getint();
for(int i=0;i<=n;i++) a[i]=getint();
for(int i=0;i<=m;i++) b[i]=getint();
m+=n; for(n=1;n<=m;n<<=1);
fft(a,n,1); fft(b,n,1);
for(int i=0;i<=n;i++) a[i]*=b[i];
fft(a,n,-1);
for(int i=0;i<=m;i++) printf("%d ",int(a[i].real()/n+0.5));
}
int main()
{
work();
return 0;
}