代码

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

const int NR = 1e5 + 10, P = 998244353, G = 3, GI = 332748118;

int l1, l2, a[NR << 2], b[NR << 2], rev[NR << 2];
int dig = 0, lim = 1;

int qp(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1ll * ret * a % P;
		a = 1ll * a * a % P;
		b >>= 1;
	}
	return ret;
}

void NTT(int *a, int opt) {
	for (int i = 0; i < lim; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int i = 1; i < lim; i <<= 1) {
		int t = qp(opt == -1 ? GI : G, (P - 1) / (i << 1));
		for (int j = 0; j < lim; j += (i << 1)) {
			for (int k = 0, w = 1; k < i; k++, w = 1ll * w * t % P) {
				int tx = a[j + k], ty = 1ll * w * a[i + j + k] % P;
				a[j + k] = (tx + ty) % P;
				a[i + j + k] = (tx - ty + P ) % P;
			}
		}
	}
}
int main()
{
	cin >> l1 >> l2;
	for (int i = 0; i <= l1; i++) cin >> a[i];
	for (int i = 0; i <= l2; i++) cin >> b[i];
	while (lim <= l1 + l2) lim <<= 1, dig++;
	for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (dig - 1));
	
	NTT(a, 1), NTT(b, 1);
	for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % P;
	NTT(a, -1);
	int inv = qp(lim, P - 2);
	for (int i = 0; i <= l1 + l2; i++) a[i] = 1ll * a[i] * inv % P;
	
	for (int i = 0; i <= l1 + l2; i++) cout << a[i] << ' ';
	
	return 0;
}

评测结果