代码

#include<bits/stdc++.h>
using namespace std; 
#include <sys/mman.h>
struct _io {
    char* s;
    _io() : s((char*)mmap(0, 1 << 28, PROT_READ, MAP_PRIVATE, fileno(stdin), 0)) {}
    operator int() {
        int x = 0;
        while (*s > 32) x = x * 10 + ((*s++) & 15);
        s++;
        s = (*s > 32 ? s : ++s);
        return x;
    }
} it;
const int N=21e5+3;
const double P=acos(-1);
struct C{
	double x,y;
	C operator+(C a)const{return{x+a.x,y+a.y};}
	C operator-(C a)const{return{x-a.x,y-a.y};}
	C operator*(C a)const{return{x*a.x-y*a.y,x*a.y+y*a.x};}
}a[N],b[N],g[N];
int n,r[N];
void pre(int m){
	int i,j;
	for(n=1;n<=m;n<<=1);
	for(i=0,g[j=n>>1]={1,0};i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)?j:0);
	C w={cos(2*P/n),sin(2*P/n)};
	for(i=j+1;i<n;++i)g[i]=g[i-1]*w;
	for(i=j-1;i>0;--i)g[i]=g[i<<1];
}
void fft(C*a,bool b=0){
	int i,j,k;
	C *w,*u,*v,x;
	for(i=0;i<n;++i)if(i<r[i])x=a[i],a[i]=a[r[i]],a[r[i]]=x;
	for(i=1;i<n;i<<=1)for(j=0;j<n;j+=i<<1)for(k=0,w=g+i,u=a+j,v=u+i;k<i;++k)
	x=w[k]*v[k],v[k]=u[k]-x,u[k]=u[k]+x;
}
char buf[999999],*p1,*p2;
#define G (p1==p2?(p2=(p1=buf)+fread(buf,1,999991,stdin),*p1++):*p1++)
void in(int&x){char c=G;for(x=0;c<'0'||c>'9';c=G);for(;c>='0'&&c<='9';c=G)x=x*10+c-48;}
char c2[999999],st[13],*k3=c2,*k4;
void out(int x){
	if(!x){
		*k3++=48,*k3++=' ';
		return;
	}
	for(k4=st+1,*k4=' ';x;*++k4=x%10+48,x/=10);
	for(;k4!=st;*k3++=*k4--);
}
int main(){
	int m,i,j;
	n=it,m=it;
	for(i=0;i<=n;++i)a[i].x=it;
	for(i=0;i<=m;++i)a[i].y=it;
	pre(m+=n),fft(a);
	for(i=0;i<n;++i)a[i]=a[i]*a[i];
	fft(a,1),a[n]=a[0];
	for(i=0;i<=m;++i)out(int(a[n-i].y/n/2+0.5));
	fwrite(c2,1,k3-c2,stdout);
	return 0;
}

评测结果