代码

#include <bits/stdc++.h>
using namespace std;

namespace io 
{
	const int L = (1 << 22) + 1;
	char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, L, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	template <class I> inline void gi (I & x)
	{
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I> inline void print (I x)
	{
		if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0', x /= 10;
		while (qr) pc (qu[qr --]);
	}
	struct IOC { ~ IOC () { flush (); } } _ioc_;
}
using io :: gi;
using io :: pc;
using io :: print;

const double pi (acos(-1));
const int MaxN(500003);
int rev[MaxN];

struct comp_t
{
	double x, y;
	comp_t(double _x = 0, double _y = 0) : x(_x), y(_y) { }
	inline comp_t operator + (const comp_t &T)
	{ return comp_t(x + T.x, y + T.y); }
	inline comp_t operator - (const comp_t &T)
	{ return comp_t(x - T.x, y - T.y); }
	inline comp_t operator * (const comp_t &T)
	{ return comp_t(x * T.x - y * T.y, x * T.y + y * T.x); }
	inline comp_t conj()
	{ return comp_t(x, -y); }
}A[MaxN], F[MaxN];

void dft(comp_t *a, int n, int f)
{
	for(int i = 1; i < n; i++)
		if(i < rev[i])
			swap(a[i], a[rev[i]]);
	for(int l = 1; l < n; l <<= 1)
	{
		comp_t wn(cos(pi / l), sin(pi / l) * f);
		static comp_t w[MaxN];
		w[0] = 1.0;
		for(int i = 1; i < l; i++)
			w[i] = w[i - 1] * wn;
		for(int i = 0; i < n; i += l << 1)
			for(int j = 0; j < l; j++)
			{
				comp_t x = a[i + j], y = a[i + j + l] * w[j];
				a[i + j] = x + y, a[i + j + l] = x - y;
			}
	}
	if(f == -1)
		for(int i = 0; i < n; i++)
			a[i].x /= n;
}

int main()
{
	int n, m, L, k;
	gi(n), gi(m);
	++n, ++m;
	for(int i = 0; i < n; i++)
		gi(F[i].x);
	for(int i = 0; i < m; i++)
		gi(F[i].y);
	for(L = 1, k = -1; L < n + m; L <<= 1, ++k);
	for(int i = 1; i < L; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k);
	dft(F, L, 1);
	for(int i = 0; i < L; i++)
	{
		int j = (L - i) & (L - 1);
		A[i] = ((F[i] + F[j].conj()) * comp_t(0.5, 0)) * ((F[i] - F[j].conj()) * comp_t(0, -0.5));
	}
	dft(A, L, -1);
	for(int i = 0; i < n + m - 1; i++)
		print((int) (A[i].x + 0.5)), pc(' ');
	return 0;
}

评测结果