代码

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

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

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

void dft(comp *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 wn(cos(pi / l), sin(pi / l) * f);
		static comp 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 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;
	scanf("%d%d", &n, &m);
	++n, ++m;
	for(int i = 0; i < n; i++)
		scanf("%lf", &A[i].x);
	for(int i = 0; i < m; i++)
		scanf("%lf", &B[i].x);
	int L, k;
	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(A, L, 1), dft(B, L, 1);
	for(int i = 0; i < L; i++)
		A[i] = A[i] * B[i];
	dft(A, L, -1);
	for(int i = 0; i < n + m - 1; i++)
		printf("%d ", (int) (A[i].x + 0.5));
	return 0;
}

评测结果