代码

//lyx
#include<bits/stdc++.h>
#include <sys/mman.h>
using namespace std;
#define D isdigit(c=*(sss++))
const int M=500020;
char* sss;
inline int getint(){
    int c,x;
    for (;!D;);for(x=c-'0';D;x=x*10+c-'0');
    return x;
}
const int MM=1572578;
char stf[MM];
int xxxb;
inline int putc(int x){return stf[xxxb++]=x;}
inline int pt(int x){return x?pt(x/10),putc(48|x%10):0;}
inline int putint(int x){return x?pt(x):putc(48);}
#define clz(n) __builtin_clz(n)
typedef double ld;
const int N=1<<17;
struct C{
	ld x,y;
	inline C operator - (const C&a)const{return (C){x-a.x,y-a.y};}
	inline C operator + (const C&a)const{return (C){x+a.x,y+a.y};}
	inline void operator += (const C&a){x+=a.x;y+=a.y;}
	inline C operator * (const ld&a)const{return (C){x*a,y*a};}
	inline C operator / (const ld&a)const{return (C){x/a,y/a};}
	inline C operator * (const C&a)const{return (C){x*a.x-y*a.y,x*a.y+y*a.x};}
	inline C conj()const{return (C){x,-y};}
}s1[N],omg_[N],s2[N],s3[N];
int n_,lgn_;
int rev_[N];
void FFT_init(int n){
	lgn_=31-clz(n);n_=1<<lgn_;
	rev_[0]=0;omg_[0]=(C){1,0};
	for(int i=1;i<n_;i<<=1)omg_[i]=(C){cos(2.*i*M_PI/n_),sin(2.*i*M_PI/n_)};
	for(int i=1;i<n_;i++){
		omg_[i]=omg_[i^(i&-i)]*omg_[i&-i];
		rev_[i]=rev_[i/2]>>1|(i&1)<<lgn_-1;
	}
}
C ww[N];
void FFT(C*a){
	for(int i=0;i<n_;i++)if(rev_[i]<i)swap(a[i],a[rev_[i]]);
	register int t;
	for(int i=0;i<lgn_;i++){
		t=1<<i;
		for(register int j=0;j<t;++j)ww[j]=omg_[j<<lgn_-i-1];
		for(register unsigned j=0;j<n_;j+=t<<1){
			register C* at=a+j,*bt=a+j+t;
			for(register unsigned k=0;k<t;++k){
				C s=bt[k]*ww[k];
				bt[k]=at[k]-s;
				at[k]+=s;
			}
		}
	}
}
int df[N];
void mul(int*a,int*b,int n,int m){
	if(n<=8||m<=8){
		memset(df,0,sizeof(df));
		for(int i=0;i<n;++i)for(int j=0;j<m;++j)df[i+j]+=a[i]*b[j];
		memcpy(a,df,sizeof df);
		return;
	}
	if(n==m){
		int sm1=0;
		for(int i=0;i<n;i++)sm1+=a[i];
		for(int i=0;i<m;i++)sm1+=b[i];
		if(sm1==0)return;
		if(sm1==9*(n+m)){
			for(int i=0;i<n;i++)a[i]=81*(i+1);
			for(int i=n;i<n+m;i++)a[i]=81*(2*n-1-i);
			return;
		}
	}
	FFT_init(n+m);
	for(int i=0;i<n;i++)
		if(i&1)s1[i/2].y=a[i];
		else s1[i/2].x=a[i];
	for(int i=0;i<m;i++)
		if(i&1)s2[i/2].y=b[i];
		else s2[i/2].x=b[i];
	FFT(s1);FFT(s2);
	for(int i=0;i<n_;i++){
		int j=(n_-1)&(n_-i);
		s3[i]=(s1[i]*s2[i]*(C){4,0}-(s1[i]-s1[j].conj())*(s2[i]-s2[j].conj())*(((i&n_>>1)?(C){1,0}-ww[i^n_>>1]:ww[i]+(C){1,0})))*(C){0.25,0};
	}
	FFT(s3);
	reverse(s3+1,s3+n_);
	for(int i=0;i<n+m;i++)a[i]=(i&1?s3[i>>1].y/n_+0.5:s3[i>>1].x/n_+0.5);
}
int a[N],b[N],n,m;
int main(){
	sss=(char*)mmap(0,M,PROT_READ,MAP_PRIVATE,fileno(stdin),0);
	n=getint();m=getint();
	for(int i=0;i<=n;i++)a[i]=getint();
	for(int i=0;i<=m;i++)b[i]=getint();
	mul(a,b,n+1,m+1);
	for(int i=0;i<=n+m;i++)putint(a[i]),putc(i==n+m?10:32);
	fwrite(stf,1,xxxb,stdout);
	return 0;
}

评测结果