代码

#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 int p = (13 << 23) - 1;

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; }
struct CMPLX {
	int real, imag;
	CMPLX operator + (const CMPLX z) const { return { real + z.real < 0 ? real + z.real + p : real + z.real - p, imag + z.imag < 0 ? imag + z.imag + p : imag + z.imag - p }; }
	CMPLX operator - (const CMPLX z) const { return { real - z.real < 0 ? real - z.real + p : real - z.real - p, imag - z.imag < 0 ? imag - z.imag + p : imag - z.imag - p }; }
	CMPLX operator * (const CMPLX z) const { return { ((long long)real * z.real - (long long)imag * z.imag) % p, ((long long)real * z.imag + (long long)imag * z.real) % p }; }
};
CMPLX pow_modp(CMPLX a, int b) { CMPLX x = {1, 0}; for(; b; a = a * a, b >>= 1) if(b & 1) x = x * a; return x; }
#define w(n) pow_modp({20747, +2402}, (p + 1) / n)
#define v(n) pow_modp({20747, -2402}, (p + 1) / n)

CMPLX fft_sup[N], w[N + 1];
void fft(auto a[], int n) {
	auto fft_a = fft_sup, j = a, _j = a; int i, k, _k; auto _w = w;
	for(i = 1; i < n; i <<= 1, std :: swap(a, fft_a))
		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)
				fft_a[_k] = *j + *_j,
				fft_a[_k + i] = (*j - *_j) * *_w;
	if(fft_a != fft_sup) std :: copy(a, a + n, fft_a);
}
void ifft(auto a[], int n) {
	auto fft_a = fft_sup, j = a, _j = a; int i, k, _k; auto _w = w;
	for(i = 1; i < n; i <<= 1, std :: swap(a, fft_a))
		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)
				fft_a[_k] = *j + *_j,
				fft_a[_k + i] = (*j - *_j) * *_w;
	if(fft_a != fft_sup) std :: copy(a, a + n, fft_a);
}
void poly_mul(auto a[], auto b[], int n) {
	CMPLX _w = w(n); w[0] = {1, 0}; for(int i = 0; i < n; ++i) w[i + 1] = w[i] * _w;
	fft(a, n), fft(b, n); for(int i = 0; i < n; ++i) a[i] = a[i] * b[i]; ifft(a, n);
	int inv_n = pow_modp(n, p - 2); for(int i = 0; i < n; ++i) a[i].real = (long long)a[i].real * inv_n % p;
}

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

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

评测结果