代码

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
const double Pi = acos(-1.0);
const int N = 3e5+5;
int n, m, f[N], len = 1, lim;
struct Complex {
	double a, b;
	Complex (double _a = 0, double _b = 0) { a = _a, b = _b; }
} a[N], b[N], Omega[30];
Complex operator + (const Complex &x, const Complex &y) {
	return Complex(x. a + y. a, x. b + y. b); }
Complex operator - (const Complex &x, const Complex &y) {
	return Complex(x. a - y. a, x. b - y. b); }
Complex operator * (const Complex &x, const Complex &y) {
	return Complex(x. a * y. a - x. b * y. b, x. b * y. a + x. a * y. b); }
inline Complex Conj(Complex z) {
	return Complex(z. a, -z. b);
}
void FFT(Complex *a, int n, bool op) {
	for (int i=0; i<n; i++)
		if (i < f[i]) swap(a[i], a[f[i]]);
	for (int m=1, t=0; m<n; m<<=1, t++) {
		Complex omega = op ? Conj(Omega[t]) : Omega[t];
		for (int i=0; i<n; i+=m<<1) {
			Complex x = Complex(1, 0);
			for (int j=0; j<m; j++, x=x*omega) {
				Complex tmp = x * a[i + j + m];
				a[i + j + m] = a[i + j] - tmp;
				a[i + j] = a[i + j] + tmp;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i=0; i<=n; i++)
		scanf ("%lf", &a[i]. a);
	for (int i=0; i<=m; i++)
		scanf ("%lf", &b[i]. a);
	n += m;
	while (len <= n) ++lim, len <<= 1;
	Omega[lim] = Complex(cos(Pi / len), sin(Pi / len));
	for (int i=lim-1; ~i; i--)
		Omega[i] = Omega[i+1] * Omega[i+1];
/*	Omega[0] = Complex(1, 0), 
	Omega[1] = Complex(cos(2 * Pi / len), sin(2 * Pi / len));
	for (int i=2; i<len; i++)
		Omega[i] = Omega[i-1] * Omega[1]; */
	for (int i=0; i<len; i++)
		f[i] = f[i >> 1] >> 1 | (i & 1) << lim - 1;
	FFT(a, len, 0), FFT(b, len, 0);
	for (int i=0; i<len; i++)
		a[i] = a[i] * b[i];
	FFT(a, len, 1);
	for (int i=0; i<=n; i++)
		printf ("%d ", (int) (a[i]. a / len + 0.5));
	return 0;
}

评测结果