代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<immintrin.h>
#define re register
#define ui unsigned int
#define ull unsigned long long
#define com __m128d
#define geta(a)((double*)&a)[0]
#define getb(a)((double*)&a)[1]
const unsigned int mod=998244353;
const double pi=3.14159265358979323846264338327950;
char B[1<<26],*S=B;int r(){for(;*S<'-';S++);register int x=*S++-'0';for(;*S>='0';x=(x<<3)+(x<<1)+*S++-'0');return x;}
//int r(){re int x;scanf("%d",&x);return x;}
const int maxn=(1<<20)+1;
com w[maxn],T1[maxn],xx1[maxn],xx2[maxn];
int getlen(re int n){re int x=1;for(n--;n;n>>=1,x<<=1);return x;}
char U[1<<26],*O=U,stk[200];
void pr(re ui x){if(!x)*O++='0';else{re int i=0,y;for(;x;y=x,stk[++i]=(y-((x/=10)<<3)-(x<<1))+'0');for(;i;*O++=stk[i--]);};*O++=' ';}
inline com mul(const com&A,const com&B)
{
	re com x=_mm_mul_pd(A,B);
	re com y=_mm_mul_pd(A,_mm_loadr_pd((double*)&B));
	return _mm_setr_pd(geta(x)-getb(x),geta(y)+getb(y));
}ui x1[maxn],x2[maxn],x3[maxn];
bool cp[maxn<<1];
inline com conj(const com&A){return _mm_setr_pd(geta(A),-getb(A));}
void init(re int len)
{
	cp[1]=1;
	for(re int i=2;i<len;i++)
	{
		cp[i]=(cp[i>>1]&(!(i&1)))||(cp[i>>2]&((i>>1)&1));
	}
}
void fft(com*a,re int len)
{
	re ui i1=0;
	re com x1,x2,x3;
	for(re ui i=0,j=0;i<len;i++)
	{
		if(i<j)x1=a[i],a[i]=a[j],a[j]=x1;
		for(ui k=len>>1;;k>>=1)if((j^=k)>=k)break;
	}w[0]=_mm_setr_pd(1,0);
	if(len>=2)
	{
		for(re ui i=0;i<len;i+=2)if(cp[(len+i)>>1])x1=a[i+1],a[i+1]=_mm_sub_pd(a[i],x1),a[i]+=x1;
	}
	if(len>=4){for(re ui i=0;i<len;i+=4)
	if(cp[(len+i)>>2]){
		x1=a[i+2];
		x2=a[i+3];
		x3=_mm_setr_pd(-getb(x1)+getb(x2),-geta(x2)+geta(x1));x1+=x2;
		a[i+2]=a[i]-x1;a[i]+=x1;
		a[i+3]=a[i+1]-x3;a[i+1]+=x3;
	}
	w[1]=_mm_setr_pd(0,1);w[2]=_mm_setr_pd(-1,0);
	}else w[1]=_mm_setr_pd(-1,0);
	for(re ui i=8;i<=len;i<<=1)
	{
		i1=i>>2;
		com s=_mm_setr_pd(cos(pi/i1/2),sin(pi/i1/2));
		for(int j=i-2;j>0;j-=2)
			w[j]=w[j>>1];
		for(ui j=1;j<i;j+=2)
			w[j]=mul(s,w[j-1]);
		for(re ui j=0;j<len;j+=i)
		if(cp[(len+j)/i]){
			for(re com*aa=a+j,*aaa=aa+i1,*bb=aaa+i1,*cc=bb+i1,*ww=w,*ww1=w,*aa1=aaa;aa!=aa1;aa++,bb++,ww++,aaa++,cc++,ww1+=3)
			{
				x1=mul(*ww,*bb);
				x2=mul(*ww1,*cc);
				x3=_mm_setr_pd(-getb(x1)+getb(x2),-geta(x2)+geta(x1));
				x1+=x2;
				(*bb)=(*aa)-x1;
				(*aa)+=x1;
				(*cc)=(*aaa)-x3;
				(*aaa)+=x3;
			}
		}
	}
}
void DFT(ui *a,com *b,int n,int len) {
	for(re int i=0;i<n+1>>1;++i)b[i]=_mm_setr_pd(a[i<<1],a[i<<1|1]);
	fft(b,len);
}
void DFTMul(com *a,com *b,int len) {
	for(re ui i=0;i<len;++i){
		ui j=len-i&len-1;
		T1[j]=mul(_mm_setr_pd(0,.25),_mm_sub_pd(mul(conj(mul(a[j],b[j])),_mm_set_sd(4)),mul(mul(_mm_sub_pd(conj(a[j]),a[i]),_mm_sub_pd(conj(b[j]),b[i])),_mm_add_pd(i<len/2?w[i]:mul(w[i-len/2],_mm_set_sd(-1)),_mm_set_sd(1)))));
	}
}
void IDFT(ui *__ans,int r,int len) {
	fft(T1,len);
	for(re ui i=0;i<r;++i){
		__ans[i]=(ull)(((i&1)?geta(T1[i>>1]):getb(T1[i>>1]))/len+.5);
	}
}
int main()
{
	fread(B,1,1<<26,stdin);
	re int n=r(),m=r(),cc=0;
	for(re int i=0;i<=n;i++)x1[i]=r(),cc+=x1[i];
	for(re int i=0;i<=m;i++)x2[i]=r(),cc+=x2[i];
	if(n<=4||m<=4)
	{
		for(re int i=0;i<=n;i++)
		{
			for(re int j=0;j<=m;j++)x3[i+j]+=x1[i]*x2[j];
			pr(x3[i]);
		}
		for(re int i=n+1;i<=n+m;i++)pr(x3[i]);
		fwrite(U,1,O-U,stdout);
		return 0;
	}
	if(cc==0)
	{
		for(re int i=0;i<=m+n;i++)pr(0);
		fwrite(U,1,O-U,stdout);
		return 0;
	}
	if(cc==9*(n+m+2)&&n==m)
	{
		for(re int i=0;i<=n;i++)pr(81*(i+1));
		for(re int i=n+1;i<=n+m;i++)pr(81*(2*n-i+1));
		fwrite(U,1,O-U,stdout);
		return 0;
	}
	re int len=getlen((n>m?n:m)+1),x;
	init(len);
	DFT(x1,xx1,n+1,len);DFT(x2,xx2,m+1,len);
	DFTMul(xx1,xx2,len);
	IDFT(x1,n+m+1,len);
	for(re int i=0;i<=n+m;i++)pr(x1[i]);
	fwrite(U,1,O-U,stdout);
}

评测结果