代码

#include<bits/stdc++.h>
#include<sys/mman.h>
using namespace std;
#define re register
#define ui unsigned int
#define ull unsigned long long
const double pi=acos(-1);
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;}
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++=' ';}
const int maxn=(1<<20)+1;
struct com
{
	double a,b;
	inline com operator +(const com&A){return(com){a+A.a,b+A.b};}
	inline void operator +=(const com&A){a+=A.a,b+=A.b;}
	inline com operator -(const com&A){return(com){a-A.a,b-A.b};}
	inline com operator *(const com&A){return(com){a*A.a-b*A.b,a*A.b+b*A.a};}
	inline com operator *(re const double &o) {return (com){a*o,b*o};}
	inline com operator /(const int&A){return(com){a/A,b/A};}
	inline com operator !(){return(com){a,-b};}
	inline bool operator !=(const com&A){return a!=A.a||b!=A.b;}
};
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;}
ui x1[maxn],x2[maxn],x3[maxn];
bool cp[maxn<<1];
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)swap(a[i],a[j]);
		for(ui k=len>>1;;k>>=1)if((j^=k)>=k)break;
	}w[0]=(com){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]=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=(com){-x1.b+x2.b,-x2.a+x1.a};x1+=x2;
			a[i+2]=a[i]-x1;a[i]+=x1;
			a[i+3]=a[i+1]-x3;a[i+1]+=x3;
		}
	w[1]=(com){0,1};w[2]=(com){-1,0};
	for(re ui i=8,i2=3;i<=len;i<<=1,i2++)
	{
		i1=i>>2;
		com s=(com){cos(pi/i1/2),sin(pi/i1/2)};
		for(re ui j=3*i1-2;j>0;j-=2)
			w[j]=w[j>>1];
		for(re ui j=1;j<3*i1;j+=2)
			w[j]=s*w[j-1];
		for(re ui j=0;j<len;j+=i)
		if(cp[(len+j)>>i2]){re com*aa=a+j,*aaa=aa+i1,*bb=aaa+i1,*cc=bb+i1;
			for(re int k=0;k<i1;k++)
			{
				x1=w[k]*bb[k];
				x2=w[k*3]*cc[k];
				x3=(com){-x1.b+x2.b,-x2.a+x1.a};
				cc[k]=aaa[k]-x3;
				aaa[k]+=x3;
				x1+=x2;
				bb[k]=aa[k]-x1;
				aa[k]+=x1;
			}
		}
	}
}
void DFT(ui *a,com *a1,int n,int len)
{
	for(re int i=0;i<n+1>>1;++i)a1[i]=(com){a[i<<1],a[i<<1|1]};
	fft(a1,len);
}
void DFTMul(com *a1,com *b1,int len)
{
	for(re int i=0;i<len;++i)
	{
		re int j=len-1&len-i;
		com tmp=(i&len>>1)?(com){1,0}-w[i^len>>1]:w[i]+(com){1,0};
		t1[j]=b1[i]*a1[i]-(b1[i]-!b1[j])*(a1[i]-!a1[j])*tmp*0.25;
	}
}
void IDFT(ui *__ans,int r,int len)
{
	fft(t1,len);
	for(re int i=0;i<r;++i) __ans[i]=(i&1)?(ull)(t1[i>>1].b/len+0.5):(ull)(t1[i>>1].a/len+0.5);
}
int main()
{
	fread(B,1,1<<26,stdin);
	re int n=r(),m=r();
	for(re int i=0;i<=n;i++)x1[i]=r();
	for(re int i=0;i<=m;i++)x2[i]=r();
	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;
	}
	re int len=getlen((n>m?n:m)+1),x;
	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);
}

评测结果