代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>

const int LEN = 1 << 20 | 1;
char bufin[LEN];
char bufout[LEN];
char *Rd = bufin, *Wt = bufout;
#define getchar() (*Rd++)
#define putchar(x) (*Wt++ = x)
inline int read() {
	register int ret, cc;
	while (!isdigit(cc = getchar())){}ret = cc-48;
	while ( isdigit(cc = getchar()))  ret = cc-48+ret*10;
	return ret;
}
inline void write(int x, char ch = '\n') {
	register int stk[20], tp;
	stk[tp = !x] = 0;
	while (x) stk[++tp] = x % 10, x /= 10;
	while (tp) putchar(stk[tp--] + '0');
	putchar(ch);
}

struct Complex {
	double x, y;
	Complex(double x = 0, double y = 0)
		:x(x), y(y) { }
	inline Complex operator + (const Complex& rhs) const { return Complex(x + rhs.x, y + rhs.y); }
	inline Complex operator - (const Complex& rhs) const { return Complex(x - rhs.x, y - rhs.y); }
	inline Complex operator * (const Complex& rhs) const { return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); }
	inline Complex operator - () const { return Complex(-x, -y); }
	inline Complex operator ! () const { return Complex( x, -y); }
	void print() {
		printf("(%f, %f)\n", x, y);
	}
};

const int MAXN = 131080;
const double PI = acos(-1.0);

inline void FFT(Complex*, int, int);
inline int getrev(int);

int rev[MAXN];
int N, M;
Complex A[MAXN];
Complex B[MAXN];
Complex C[MAXN];
Complex W[2][MAXN];
int tmp[MAXN];
int main() {
#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
#endif
	fread(bufin, 1, LEN, stdin);
	N = read() + 1, M = read() + 1;
	for (int i = 0; i < N; ++i) (i & 1 ? A[i >> 1].y : A[i >> 1].x) = read();
	for (int i = 0; i < M; ++i) (i & 1 ? B[i >> 1].y : B[i >> 1].x) = read();
	int len = N + M - 1, bln = getrev((len+1)>>1);
	FFT(A, bln, 0), FFT(B, bln, 0);
	for (int i = 0, j; i < bln; ++i) {
		j = (bln-i)&(bln-1);
		C[i] = A[i]*B[i]-((A[i]-!A[j])*(B[i]-!B[j])*(W[0][i]+1))*0.25;
	}
	FFT(C, bln, 1);
	for (int i = 0; i < len; ++i) write(((i & 1) ? C[i >> 1].y : C[i >> 1].x) + 0.5, ' ');
	putchar('\n');
	fwrite(bufout, 1, Wt - bufout, stdout);
}

inline int getrev(int n) {
	int bln = 1, bct = 0;
	while (bln < n) bln <<= 1, bct++;
	for (int i = 0; i < bln; ++i) 
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bct - 1));
	for (int i = 0; i < bln; ++i)
		W[0][i] = W[1][(bln-i)&(bln-1)] = Complex(cos(2*PI*i/bln), sin(2*PI*i/bln));
	return bln;
}

inline void FFT(Complex* a, int n, int opt) {
	for (int i = 0; i < n; ++i) 
		if (i < rev[i]) std::swap(a[i], a[rev[i]]);
	for (int i = 1, t = n >> 1; i < n; i <<= 1, t >>= 1) {
		for (int j = 0, p = (i << 1); j < n; j += p) {
			Complex *x = a + j, *y = a + j + i, *w = W[opt];
			for (int k = 0; k < i; ++k, ++x, ++y, w += t) {
				Complex tmp = *w * *y;
				*y = *x - tmp, *x = *x + tmp;
			}
		}
	}
	if (opt) for (int i = 0; i < n; ++i) a[i].x /= n, a[i].y /= n;
}

评测结果