代码

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

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

const int maxn = 1 << 18;
const int mod = 998244353, g = 3;

int qp(int x, int n) { return !n ? 1 : 1LL * qp(1LL * x * x % mod, n >> 1) * (n & 1 ? x : 1) % mod; }
int inv(int a) { return qp(a, mod - 2); }

int r[maxn], w[20][maxn];

void init_FFT(int n) {
	for (int i = 1; i < n - 1; ++ i) r[i] = r[i >> 1] >> 1 | ((i & 1) * (n >> 1));
	for (int x = 2, i = 1; x <= n; x <<= 1, ++ i) {
		int wn = qp(g, (mod - 1) / x); w[i][0] = 1;
		rep(j, x / 2) w[i][j + 1] = 1LL * w[i][j] * wn % mod;
	}
}

inline void FFT(int *a, int n, int f) {
	for (int i = 1; i < n - 1; ++ i)
		if (i < r[i]) swap(a[i], a[r[i]]);
	for (int h = 2, x = 1; h <= n; h <<= 1, ++ x) {
		for (int i = 0; i < n; i += h) {
			int *wn = w[x], *p = a + i, *q = a + i + h / 2;
			for (int j = 0; j < h / 2; ++ j, ++ p, ++ q, ++ wn) {
				int u = (*p), v = 1LL * (*q) * (*wn) % mod;
				(*p) = u + v >= mod ? u + v - mod : u + v;
				(*q) = u - v < 0 ? u - v + mod : u - v;
			}
		}
	}
	if (!~f) {
		reverse(a + 1, a + n);
		int r = inv(n);
		rep(i, n) a[i] = 1LL * a[i] * r % mod;
	}
}

struct poly : vector <int> {
	poly(int len, int x = 0) { resize(len); rep(i, len) at(i) = x; }
	poly(const vector <int> &v) { *this = v; }
	friend inline poly operator + (const poly &a, const poly &b) {
		poly c(max(a.size(), b.size()));
		rep(i, a.size()) c[i] = (c[i] + a[i]) % mod;
		rep(i, b.size()) c[i] = (c[i] + b[i]) % mod;
		return c;
	}
	friend inline poly operator - (const poly &a, const poly &b) {
		poly c(max(a.size(), b.size()));
		rep(i, a.size()) c[i] = (c[i] + a[i]) % mod;
		rep(i, b.size()) c[i] = (c[i] + mod - b[i]) % mod;
		return c;
	}
	friend inline poly operator * (int c, const poly &a) {
		poly b(a.size());
		rep(i, a.size()) b[i] = 1LL * c * a[i] % mod;
		return b;
	}
	friend inline poly operator * (const poly &a, const poly &b) {
		static int A[maxn], B[maxn];
		int n = a.size() + b.size() - 1;
		int sz = 1; while (sz < n) sz <<= 1;
		init_FFT(sz);
		rep(i, sz) A[i] = i < (int)a.size() ? a[i] : 0;
		rep(i, sz) B[i] = i < (int)b.size() ? b[i] : 0;
		FFT(A, sz, 1); FFT(B, sz, 1);
		rep(i, sz) A[i] = 1LL * A[i] * B[i] % mod;
		FFT(A, sz, -1);
		poly c(n); rep(i, n) c[i] = A[i];
		return c;
	}
	friend poly deri(const poly &a) {
		poly b(a.size());
		rep(i, a.size()) if (i) b[i - 1] = 1LL * a[i] * i % mod;
		return b;
	}
	friend poly inte(const poly &a) {
		poly b(a.size() + 1);
		rep(i, b.size()) if (i) b[i] = 1LL * a[i - 1] * inv(i) % mod;
		return b;
	}
	friend poly inv(const poly &a) {
		if (a.size() == 1) return poly(1, inv(a[0]));
		int n0 = (a.size() + 1) >> 1;
		poly a0(n0); rep(i, n0) a0[i] = a[i]; a0 = inv(a0);
		poly res = a0 * (poly(1, 2) - a0 * a); res.resize(a.size());
		return res;
	}
	friend poly sqrt(const poly &a) {
		if (a.size() == 1) return poly(1, 1);
		int n0 = (a.size() + 1) >> 1;
		poly a0(n0); rep(i, n0) a0[i] = a[i]; a0 = sqrt(a0);
		poly a1(a.size()); rep(i, n0) a1[i] = a0[i];
		poly res = ((mod + 1) / 2) * (a0 + a * inv(a1)); res.resize(a.size());
		return res;
	}
	friend poly ln(const poly &a) {
		return inte(deri(a) * inv(a));
	}
	friend poly exp(const poly &a) {
		if (a.size() == 1) return poly(1, 1);
		int n0 = (a.size() + 1) >> 1;
		poly a0(n0); rep(i, n0) a0[i] = a[i]; a0 = exp(a0);
		poly a1(a.size()); rep(i, n0) a1[i] = a0[i];
		poly res = a0 * (poly(1, 1) - ln(a1) + a); res.resize(a.size());
		return res;
	}
	friend ostream& operator << (ostream &out, const poly &a) {
		out << "{";
		rep(i, a.size()) out << a[i] << ",}"[i + 1 == (int)a.size()];
		return out;
	}
};

int main() {
	int n; scanf("%d", &n); ++ n;
	int m; scanf("%d", &m); ++ m;
	poly a(n), b(m);
	rep(i, n) scanf("%d", &a[i]);
	rep(i, m) scanf("%d", &b[i]);
	poly c = a * b;
	rep(i, n + m - 1) printf("%d%c", c[i], " \n"[i + 1 == n + m - 1]);
	return 0;
}

评测结果