先来一段非递归!
#include<bits/stdc++.h>
using namespace std;
#define N ((1<<18)+3)
const double eps=0.5,pi=acos(-);
struct vec{
double r,i;
vec operator +(const vec& w){return (vec){r+w.r,i+w.i};}
vec operator -(const vec& w){return (vec){r-w.r,i-w.i};}
vec operator *(const vec& w){return (vec){r*w.r-i*w.i,i*w.r+r*w.i};}
}a[N],b[N];
int n,m,len,rev[N],t;
bool che[N];
int read(){
int f=,a=getchar(),tmp=;
while(a<'' || a>'') {if(a=='-') f=-; a=getchar();}
while(a>=''&& a<='') tmp=tmp*+a-'',a=getchar();
return tmp*=f;
}
void fft(vec *x,int t){
memset(che,,sizeof(che));
for(int i=;i<len;i++) if(!che[i]) swap(x[i],x[rev[i]]),che[rev[i]]=;
for(int lnow=;lnow<=len;lnow<<=){ //从最底层开始往上推,一开始每一小坨只有2个,慢慢往上到最后达到len
vec w0=(vec){cos(t**pi/lnow),sin(t**pi/lnow)},w,t1,t2;
for(int i=;i<len;i+=lnow){ //每一坨
vec w=(vec){,};
for(int j=;j<lnow/;j++,w=w*w0){
t1=x[i+j]; t2=w*x[i+j+lnow/];
x[i+j]=t1+t2; x[i+j+lnow/]=t1-t2;
}
}
}
}
int main(){
n=read(); m=read();
for(len=;len<(n+m+);len<<=,t++); t--;
for(int i=;i<=len;i++) rev[i]=(rev[i>>]>>)|(i&?(<<t):); //二进制反转,注意之前的t--
for(int i=;i<=n;i++) a[i].r=read();
for(int i=;i<=m;i++) b[i].r=read();
fft(a,); fft(b,);
for(int i=;i<=len;i++) a[i]=a[i]*b[i];
fft(a,-);
for(int i=;i<=n+m;i++) printf("%d ",(int)(a[i].r/len+eps));
return ;
}