代码

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

namespace fastIO {
    const int SZ = 1 << 25;
    char ibuf[SZ], *p0 = ibuf, *p1 = ibuf;
    inline char getchar(void) { return p0 == p1 && (p1 = (p0 = ibuf) + fread(ibuf, 1, SZ, stdin), p0 == p1) ? EOF : *p0++; }
    char char_read; void read(auto &val) {
		val = 0; do char_read = getchar(); while(!isdigit(char_read));
		do val = val * 10 + char_read - '0'; while(isdigit(char_read = getchar()));
    }
    char obuf[SZ], *p = obuf;
    inline void putchar(char char_write) { *p++ = char_write; }
    void write(auto val) { if(val >= 10) write(val / 10); putchar(val % 10 + '0'); }
    inline void write(auto a[], int sz) { for(int i = 0; i < sz; ++i) write(a[i]), putchar(' '); putchar('\n'); }
    void output(void) { fwrite(obuf, p - obuf, 1, stdout);}
};

const int N =     1 << 21;
const float PI = acos(-1);

struct CMPLX {
	double a, b; // a + bi
	CMPLX operator + (CMPLX z)  const { return (CMPLX){ a + z.a, b + z.b}; }
	CMPLX operator - (CMPLX z)  const { return (CMPLX){ a - z.a, b - z.b}; }
	CMPLX operator * (CMPLX z)  const { return (CMPLX){ a * z.a - b * z.b, a * z.b + b * z.a}; }
} c[N];

CMPLX w[N + 1];

CMPLX fft_sup[N];
inline void fft(auto a[], int n) {
	auto b = fft_sup, j = a, _j = a; int i, k, _k; auto _w = w;
	for(i = 1; i < n; i <<= 1, std :: swap(a, b))
		for(k = 0, j = a, _j = a + (n >> 1), _w = w; k != n; k += i, _w += i)
			for(_k = k, k += i; _k != k; ++j, ++_j, ++_k)
				b[_k] = *j + *_j,
				b[_k + i] = (*j - *_j) * *_w;
	if(b != fft_sup) std :: copy(a, a + n, b);
}
inline void ifft(auto a[], int n) {
	auto b = fft_sup, j = a, _j = a; int i, k, _k; auto _w = w;
	for(i = 1; i < n; i <<= 1, std :: swap(a, b))
		for(k = 0, j = a, _j = a + (n >> 1), _w = w + n; k != n; k += i, _w -= i)
			for(_k = k, k += i; _k != k; ++j, ++_j, ++_k)
				b[_k] = *j + *_j,
				b[_k + i] = (*j - *_j) * *_w;
	if(b != fft_sup) std :: copy(a, a + n, b);
}
inline void poly_mul(auto a[], auto b[], int n) {
	CMPLX _w = (CMPLX){ cos(PI / n * 2), sin(PI / n * 2)};
	w[0].a = 1; for(int i = 1; i <= n; ++i) w[i] = w[i - 1] * _w;
	for(int i = 0; i < n; ++i) c[i].a = a[i], c[i].b = b[i]; fft(c, n);
	for(int i = 0; i < n; ++i) c[i] = c[i] * c[i]; ifft(c, n);
	float _n = 0.5 / n; for(int i = 0; i < n; ++i) a[i] = c[i].b * _n + 0.123;
}

int n, n_a, n_b;
int a[N], b[N];

int main(void) {
	fastIO :: read(n_a), fastIO :: read(n_b); for(n = 1; n <= n_a + n_b; n <<= 1);
	for(int i = 0; i <= n_a; ++i) fastIO :: read(a[i]);
	for(int i = 0; i <= n_b; ++i) fastIO :: read(b[i]);
	poly_mul(a, b, n);
	fastIO :: write(a, n_a + n_b + 1), fastIO :: output();
	return 0;
}

评测结果