代码

#include<bits/stdc++.h>
#define db(x) cerr<<#x<<" = "<<x<<endl;
using namespace std;
const int InputBufferSize = 1000000;
const int OutputBufferSize = 1000000;
namespace input {
	char buffer[InputBufferSize],*s,*eof;
	inline void init() {
		assert(stdin!=NULL);
		s=buffer;
		eof=s+fread(buffer,1,InputBufferSize,stdin);
	}
	inline bool read(int &x) {
		x=0;
		int flag=1;
		while(!isdigit(*s)&&*s!='-')s++;
		if(eof<=s)return false;
		if(*s=='-')flag=-1,s++;
		while(isdigit(*s))x=x*10+*s++-'0';
		x*=flag;
		return true;
	}
	inline bool read(char* str) {
		*str=0;
		while(isspace(*s))s++;
		if(eof<s)return false;
		while(!isspace(*s))*str=0,*str=*s,str++,s++;
		*str=0;
		return true;
	}
}
namespace output {
	char buffer[OutputBufferSize];
	char *s=buffer;
	inline void flush() {
		assert(stdout!=NULL);
		fwrite(buffer,1,s-buffer,stdout);
		s=buffer;
		fflush(stdout);
	}
	inline void print(const char ch) {
		if(s-buffer>OutputBufferSize-2)flush();
		*s++=ch;
	}
	inline void print(char* str) {
		while(*str!=0)print(char(*str++));
	}
	inline void print(int x) {
		char buf[25]= {0},*p=buf;
		if(x<0)print('-'),x=-x;
		if(x==0)print('0');
		while(x)*(++p)=x%10,x/=10;
		while(p!=buf)print(char(*(p--)+'0'));
	}
}
using namespace input;
using namespace output;
const int N = 262233;
const double pi = acos(-1);
struct comp {
	double s,x;
	comp () {};
	comp (double S,double X):s(S),x(X) {};
	comp operator + (comp b) {
		return comp(s+b.s,x+b.x);
	}
	comp operator - (comp b) {
		return comp(s-b.s,x-b.x);
	}
	comp operator * (comp b) {
		return comp(s*b.s-x*b.x,s*b.x+x*b.s);
	}
} f[N],g[N];
int R[N],lim,l;
void FFT(comp *A,int type) {
	for(int i=0; i<lim; ++i) {
		if(i>R[i])swap(A[i],A[R[i]]);
	}
	for(int j=1; j<lim; j<<=1) {
		comp unit(cos(pi/j),sin(pi/j)*type);
		for(int i=0; i<lim; i+=(j<<1)) {
			comp w(1,0);
			for(int k=0; k<j; ++k,w=w*unit) {
				comp qwq,qaq;
				qwq=A[i+k];
				qaq=w*A[i+k+j];
				A[i+k]=qwq+qaq;
				A[i+k+j]=qwq-qaq;
			}
		}
	}
	return;
}
int main() 
{
	
	init();
	int n,m;
	read(n);
	read(m);
	for(int i=0; i<=n; ++i) {
		int tmp;
		read(tmp);
		f[i].s=tmp;
	}
	for(int i=0; i<=m; ++i) {
		int tmp;
		read(tmp);
		g[i].s=tmp;
	}
	for(lim=1,l=0; lim<=n+m; ++l,lim<<=1);
	for(int i=0; i<lim; ++i) {
		R[i]=(R[i>>1]>>1)|((i&1)<<(l-1));
	}
	FFT(f,1);
	FFT(g,1);
	for(int i=0; i<lim; ++i) {
		f[i]=f[i]*g[i];
	}
	FFT(f,-1);
	for(int i=0; i<=m+n; ++i) {
		print((int)(f[i].s/(1.0*lim)+0.5));
		print(' ');
	}
	flush();
	return 0;
}

评测结果