代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 1<<18;
const double Pi=acos(-1);
int n, m, l, k;
struct cp{
	double a, b;
	inline void operator +=(const cp &rhs){ a+=rhs.a, b+=rhs.b;}
	inline cp operator +(const cp &rhs)const{ return (cp){a+rhs.a, b+rhs.b};}
	inline cp operator -(const cp &rhs)const{ return (cp){a-rhs.a, b-rhs.b};}
	inline cp operator *(const cp &rhs)const{ return (cp){a*rhs.a-b*rhs.b, a*rhs.b+b*rhs.a};}
	inline cp operator *(const double rhs)const{ return (cp){a*rhs, b*rhs};}
	inline cp operator ~()const{ return (cp){a, -b};}
} a[N], b[N], f[N], g[N], w[N];
inline int Get(int n){ int p=1; while(p<=n) p<<=1; return p;}
inline void DFT(cp *f, int n){
	for(register int i=0, j=0; i<n; ++i){
		if(i>j) swap(f[i], f[j]);
		for(register int k=n>>1; (j^=k)<k; k>>=1);
	}
	for(register int i=1; i<n; i<<=1) for(register int j=0; j<n; j+=i<<1)
		for(register int k=j; k<j+i; ++k){
			cp t=w[i+k-j]*f[k+i];
			f[k+i]=f[k]-t, f[k]+=t;
		}
}
inline void IDFT(cp *f, int n){ reverse(f+1, f+n), DFT(f, n);}
int main() {
	read(n), read(m), l=Get(n+m);
	for(register int i=0, x=0; i<=n; ++i) read(x), f[i].a=x>>15, f[i].b=x&32767;
	for(register int i=0, x=0; i<=m; ++i) read(x), g[i].a=x>>15, g[i].b=x&32767;
	for(register int i=1; i<l; i<<=1){
		w[i]=(cp){1, 0};
		for(register int j=1; j<i; ++j)
			w[i+j]=((j&31)==1?(cp){cos(Pi*j/i), sin(Pi*j/i)}:w[i+j-1]*w[i+1]);
	}
	DFT(f, l), DFT(g, l);
	for(register int i=0; i<l; ++i){
		static cp q, f0, f1, g0, g1;
		q=~f[i?l-i:0], f0=(f[i]-q)*(cp){0, -.5}, f1=(f[i]+q)*.5;
		q=~g[i?l-i:0], g0=(g[i]-q)*(cp){0, -.5}, g1=(g[i]+q)*.5;
		a[i]=f1*g1, b[i]=f1*g0+f0*g1+f0*g0*(cp){0, 1};
	}
	IDFT(a, l), IDFT(b, l);
	double k=1./l;
	for(register int i=0; i<=n+m; ++i, print(' '))
		print((((ll)(a[i].a*k+.5)<<30)+((ll)(b[i].a*k+.5)<<15)+(ll)(b[i].b*k+.5)));
	return flush(), 0;
}

评测结果