快速傅里叶

#include<bits/stdc++.h>
typedef long long ll;
const double pi=acos(-1);
#define FILE "read"
#define MAXN 300010
int n,m,H(0),L(1),R[MAXN];
inline int read(){
	int x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct complex{
	double r,v;
	complex(double a=0,double b=0):r(a),v(b){}
	inline complex operator+(const complex &b){return complex(r+b.r,v+b.v);}
	inline complex operator-(const complex &b){return complex(r-b.r,v-b.v);}
	inline complex operator*(const complex &b){return complex(r*b.r-v*b.v,r*b.v+v*b.r);}
}a[MAXN],b[MAXN],w[MAXN];
inline void swap(complex &a,complex &b){complex t(a);a=b;b=t;}
void FFT(complex *a,int f){
	for(int i=0;i<L;++i)  if(i<R[i])  swap(a[i],a[R[i]]);
	for(int len=2;len<=L;len<<=1){
		int l=len>>1;  
		complex wn(cos(pi/l),f*sin(pi/l));  
		for(int i=1;i<l;i++)  w[i]=w[i-1]*wn;
		for(int st=0;st<L;st+=len) for(int k=0;k<l;++k){
			complex x=a[st+k],y=w[k]*a[st+k+l];
			a[st+k]=x+y;  a[st+k+l]=x-y;
		}
	}
	if(f==-1){
		for(int i=0;i<L;i++){
			a[i].r/=L;
		}
	}
}
int main(){
	n=read()+1,m=read()+1,w[0].r=1;
	for(int i=0;i<n;++i)  a[i].r=read();
	for(int i=0;i<m;++i)  b[i].r=read();
	while(L<n+m) L<<=1,++H;
	for(int i=0;i<L;++i)  R[i]=(R[i>>1]>>1)|((i&1)<<(H-1));
	FFT(a,1);  FFT(b,1);
	for(int i=0;i<L;++i) a[i]=a[i]*b[i];
	FFT(a,-1);
	for(int i=0;i<n+m-1;++i)  printf("%d ",(int)(a[i].r+0.5));
	return 0;
}