代码

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

namespace fastIO {
    const int SZ = 1 << 25;
    char ibuf[SZ], *p0 = ibuf, *p1 = ibuf;
    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;
    void putchar(char char_write) { *p++ = char_write; }
    void write(auto val) { if(val >= 10) write(val / 10); putchar(val % 10 + '0'); }
    void write(auto a[], int sz) { for(int i = 0; i < sz; ++i) write(a[i].val), putchar(' '); putchar('\n'); }
    void output(void) { fwrite(obuf, p - obuf, 1, stdout);}
};

const int N =     1 << 21;
const int p =    81 << 21 | 1;
const int g =  1167 << 12 | 1;
const int h = 11443 << 12 | 1;

struct RING {
	int val;
	RING operator + (const RING r) const { return (RING){ val + r.val < p ? val + r.val : val + r.val - p }; }
	RING operator - (const RING r) const { return (RING){ val - r.val < 0 ? val - r.val + p : val - r.val }; }
	RING operator * (const RING r) const { return (RING){ (long long)val * r.val % p }; }
	RING operator * (const int  w) const { return (RING){ (long long)val * w     % p }; }
};

int pow_modp(int a, int b) { int x = 1; for(; b; a = (long long)a * a % p, b >>= 1) if(b & 1) x = (long long)x * a % p; return x; }

RING ntt_sup[N];
void ntt(auto a[], int n, const int g) {
	auto b = ntt_sup, j = a, _j = a + n; int i, k, _k, w, _w;
	for(i = 1, w = pow_modp(g, (p - 1) / n); i < n; i <<= 1, w = (long long)w * w % p, std :: swap(a, b))
		for(k = 0, j = a, _j = a + (n >> 1), _w = 1; k != n; k += i << 1, _w = (long long)_w * w % p)
			for(int _k = k; _k != k + i; ++_k, ++j, ++_j)
				b[_k] = *j + *_j, b[_k + i] = (*j - *_j) * _w;
	if(b != ntt_sup) std :: copy(a, a + n, b);
}
void poly_mul(auto a[], auto b[], int n) {
	ntt(a, n, g), ntt(b, n, g);     for(int i = 0; i < n; ++i) a[i] = a[i] * b[i]; ntt(a, n, h);
	int inv_n = pow_modp(n, p - 2); for(int i = 0; i < n; ++i) a[i] = a[i] * inv_n;
}

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

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

评测结果