代码

#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() getchar() //(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 operator /= (const double &T)
	{
		x /= T, y /= T;
		return *this;
	}
	inline comp_t conj()
	{ return comp_t(x, -y); }
}A[MaxN], w[MaxN];

void dft(comp_t *a, int n)
{
	for(int i = 1; i < n; i++)
		if(i < rev[i])
			swap(a[i], a[rev[i]]);
	for(int i = 2, base = n >> 1; i <= n; i <<= 1, base >>= 1)
		for(int j = 0; j < n; j += i)
		{
			comp_t *l = a + j, *r = a + j + (i >> 1), *p = w;
			for(int k = 0; k < (i >> 1); ++k, ++l, ++r, p += base)
			{
				comp_t tmp = *r * *p;
				*r = *l - tmp, *l = *l + tmp;
			}
		}
}

int main()
{
	int n, m, L, k;
	gi(n), gi(m);
	for(int i = 0; i <= n; i++)
		gi(A[i].x);
	for(int i = 0; i <= m; i++)
		gi(A[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);
	for(int i = 0; i < L; i++)
		w[i] = comp_t(cos(2 * pi * i / L), sin(2 * pi * i / L));
	dft(A, L);
	A[L] = A[0];
	for(int i = 0; i <= L - i; i++)
	{
		comp_t t1 = (A[i] + A[L - i].conj()) * comp_t(0, 1) * (A[i] - A[L - i].conj());
		comp_t t2 = (A[L - i] + A[i].conj()) * comp_t(0, 1) * (A[L - i] - A[i].conj());
		t1 /= 4, t2 /= 4;
		A[L - i] = t1, A[i] = t2;
	}
	dft(A, L);
	for(int i = 0; i <= n + m; i++)
		print((int) (-A[i].x / L + 0.5)), pc(' ');
	return 0;
}

评测结果