代码

#include<bits/stdc++.h>
using namespace std;

int get() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

const int N = 1 << 21, P = 998244353, G = 3;
typedef vector<int> poly;

int qpow(int x, int y) {
	int res = 1;
	while(y) res = 1ll * res * ((y & 1)? x : 1) % P, x = 1ll * x * x % P, y >>= 1;
	return res;
}

int Mod(int x) { return x >= P? x - P : x; }

poly r, wk;
void DFT(poly& A) {
	int lim = A.size(), l = __builtin_ctz(lim); 
	r.resize(lim), wk.resize(lim);
	for(int i = 0; i < lim; i++) {
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
		if(i < r[i]) swap(A[i], A[r[i]]);
	}
	for(int mid = 1; mid < lim; mid <<= 1) {
		int Wn = qpow(G, (P - 1) / (mid << 1));
		wk[0] = 1;
		for(int i = 1; i < mid; i++) wk[i] = 1ll * wk[i - 1] * Wn % P;
		for(int i = 0; i < lim; i += mid << 1) 
			for(int j = 0; j < mid; j++) {
				int x = A[i + j], y = 1ll * A[i + mid + j] * wk[j] % P;
				A[i + j] = Mod(x + y), A[i + mid + j] = Mod(x - y + P);
			}
	}
}

void iDFT(poly& A) {
	DFT(A);
	int inv = qpow(A.size(), P - 2);
	for(int i = 0; i < A.size(); i++) A[i] = 1ll * A[i] * inv % P;
	reverse(A.begin() + 1, A.end());
}

poly operator *(poly a, poly b) {
	poly res(a.size() + b.size() - 1);
	int lim = 1, l = 0;
	while(lim < a.size() + b.size()) lim <<= 1, ++l;
	a.resize(lim), b.resize(lim);
	DFT(a), DFT(b);
	for(int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % P;
	iDFT(a);
	for(int i = 0; i < res.size(); i++) res[i] = a[i];
	return res;
}

int n, m;
poly f, g;

int main() {
	n = get(), m = get();
	f.resize(n + 1), g.resize(m + 1);
	for(int i = 0; i <= n; i++) f[i] = get();
	for(int i = 0; i <= m; i++) g[i] = get();
	f = f * g;
	for(auto v : f) printf("%d ", v);
	return 0;
}

评测结果