代码

#pragma GCC optimize("Ofast")
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1<<17;
typedef double flo;
typedef long long ll;
const flo pi=acos(-1.);
struct vec{
	flo x,y;
	vec(){}
	vec(flo x,flo y=0):x(x),y(y){}
};
vec operator+(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator-(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator*(vec a,vec b){return vec(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
vec conj(vec a){return vec(a.x,-a.y);}
vec w[N];
void initw(int n){
	w[1]=vec(1,0);
	for(int i=2;i<n;i<<=1){
		flo t=pi/i;
		vec u(cos(t),sin(t));
		for(int j=0;j<i/2;j++)
			w[i+j*2+1]=(w[i+j*2]=w[i/2+j])*u;
	}
}
vec*getw(int n){
	return w+n/2;
}
void fft(vec*a,int n){
	for(int i=0,j=0;i<n;++i){
		if(i<j)
			swap(a[i],a[j]);
		for(int k=n>>1;;k>>=1)
			if((j^=k)>=k)break;
	}
	for(int i=1;i<n;i<<=1){
		vec*w=getw(i<<1);
		for(int j=0;j<n;j+=i<<1){
			vec*b=a+j,*c=b+i;
			for(int k=0;k<i;++k){
				vec v=w[k]*c[k];
				c[k]=b[k]-v,b[k]=b[k]+v;
			}
		}
	}
}
struct buf{
	char a[1<<25],*s;
	char b[1<<25],*t;
	buf():s(a),t(b){
		a[fread(a,1,sizeof a,stdin)]=0;
	}
	~buf(){fwrite(b,1,t-b,stdout);}
	operator int(){
		int x=0;
		while(*s<48)++s;
		while(*s>32)
			x=x*10+*s++-48;
		return x;
	}
	void out(int x){
		static char c[12];
		char*i=c;
		if(!x)*t++=48;
		else{
			while(x){
				int y=x/10;
				*i++=x-y*10+48,x=y;
			}
			while(i!=c)*t++=*--i;
		}
		*t++=32;
	}
}it;
int main(){
	static ll a[N],b[N],c[N];
	int n=it,m=it,n2=(n+1)/2,m2=m/2,u=m-m/2;
	const int L=23;
	for(int i=0;i<=n;++i)
		a[i]=it;
	for(int i=0;i<=n2;++i)
		a[i]=a[i*2+1]<<L|a[i*2];
	for(int i=n2+1;i<=n;++i)
		a[i]=0;
	for(int i=0;i<=m;++i)
		b[i]=it;
	for(int i=0;i<=u;++i)
		c[i]=b[i*2+1];
	for(int i=0;i<=m2;++i)
		b[i]=b[i*2];
	for(int i=m2+1;i<=m;++i)
		b[i]=0;
	if(n==0&&m==0)return it.out(a[0]*b[0]),0;
	int l=2<<__lg(n2+u+1)-1;
	
	static vec sa[N/2],sb[N/2],sc[N/2],sd[N/2],se[N/2];
	for(int i=0;i<l;++i){
		sa[i]=vec(a[i*2],a[i*2+1]);
		sb[i]=vec(b[i*2],b[i*2+1]);
		sc[i]=vec(c[i*2],c[i*2+1]);
	}
	initw(l);
	fft(sa,l),fft(sb,l),fft(sc,l);
	vec*w=getw(l);
	#define tmul(a,b,c) c[j]=(conj(a[j]*b[j])*4-(conj(a[j])-a[i])*(conj(b[j])-b[i])*((i<l/2?w[i]:w[i-l/2]*-1)+1))*vec(0,.25);
	for(int i=0;i<l;++i){
		int j=l-i&l-1;
		tmul(sa,sb,sd);
	}
	for(int i=0;i<l;++i){
		int j=l-i&l-1;
		tmul(sa,sc,se);
	}
	fft(sd,l);
	fft(se,l);
	for(int i=0;i<l;++i)
		a[i*2]=sd[i].y/l+.5,a[i*2+1]=sd[i].x/l+.5,
		b[i*2]=se[i].y/l+.5,b[i*2+1]=se[i].x/l+.5;
	u=(n+m-1)/2;
	for(int i=0;i<=u;++i)
	{
		b[i]+=a[i]>>23;
		it.out(a[i]&0x7fffff);
		a[i+1]+=b[i]>>23;
		it.out(b[i]&0x7fffff);
	}
	if(!(n+m&1))it.out(a[u+1]&0x7fffff);
}

评测结果