代码

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define DC int T = gi <int> (); while (T--)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

//const int INF = 0x3f3f3f3f, N = 1000003, M = N << 1;
const double pi = acos(-1.0);

int N, M;
int limit, b;
int rev[800003];

struct Complex
{
	double a, b;
	Complex (double x = 0, double y = 0) {a = x, b = y;}
} f[800003], g[800003], ans[800003];

Complex operator + (Complex a, Complex b) {return Complex(a.a + b.a, a.b + b.b);}
Complex operator - (Complex a, Complex b) {return Complex(a.a - b.a, a.b - b.b);}
Complex operator * (Complex a, Complex b) {return Complex(a.a * b.a - a.b * b.b, a.a * b.b + a.b * b.a);}

void FFT(Complex *a, int t)
{
	for (int i = 0; i < limit; i+=1)
		if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int m = 1; m < limit; m <<= 1)
	{
		Complex Wn = Complex(cos(pi / m), t * sin(pi / m));
		for (int n = m << 1, j = 0; j <= limit; j+=n)
		{
			Complex w = Complex(1, 0);
			for (int k = 0; k < m; k+=1, w = w * Wn)
			{
				Complex x = a[j + k], y = w * a[j + k + m];
				a[j + k] = x + y, a[j + k + m] = x - y;
			}
		}
	}
}

int main()
{
	//File("");
	N = gi <int> (), M = gi <int> ();
	for (int i = 0; i <= N; i+=1) scanf("%lf", &f[i].a);
	for (int i = 0; i <= M; i+=1) scanf("%lf", &g[i].a);
	limit = 1;
	while (limit <= N + M) limit <<= 1, ++b;
	for (int i = 0; i < limit; i+=1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (b - 1));
	FFT(f, 1); FFT(g, 1);
	for (int i = 0; i <= limit; i+=1) ans[i] = f[i] * g[i];
	FFT(ans, -1);
	for (int i = 0; i <= N + M; i+=1) printf("%d ", (int)(ans[i].a / limit + 0.5));
	return 0;
}

评测结果