代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define MOD 998244353
typedef long long ll;
const int N = 3e5+5;
int n, m, f[N], len = 1, lim;
ll a[N], b[N], Ilen;
inline int qpow(ll x, int y) {
	ll t = 1;
	while (y) {
		if (y & 1) t = t * x % MOD;
		x = x * x % MOD, y >>= 1;
	} return t;
}
inline int PLUS(int x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
	if (x < 0) x += MOD;
	return x;
}
void NTT(ll *a, int n, bool op) {
	for (int i=0; i<n; i++)
		if (i < f[i]) swap(a[i], a[f[i]]);
	for (int m=1; m<n; m<<=1) {
		ll omega = qpow(3, (MOD - 1) / (m << 1));
		for (int i=0; i<n; i+=m<<1) {
			ll x = 1;
			for (int j=0; j<m; j++, x=x*omega%MOD) {
				ll tmp = x * a[i + j + m] % MOD;
				a[i + j + m] = (a[i + j] - tmp + MOD) % MOD;
				a[i + j] = (a[i + j] + tmp) % MOD;
			}
		}
	}
	if (op) reverse (a+1, a+n);
}
int main() {
	cin >> n >> m;
	for (int i=0; i<=n; i++)
		scanf ("%lld", &a[i]);
	for (int i=0; i<=m; i++)
		scanf ("%lld", &b[i]);
	n += m;
	while (len <= n) ++lim, len <<= 1;
	Ilen = qpow(len, MOD - 2);
	for (int i=0; i<len; i++)
		f[i] = f[i >> 1] >> 1 | (i & 1) << lim - 1;
	NTT(a, len, 0), NTT(b, len, 0);
	for (int i=0; i<len; i++)
		a[i] = a[i] * b[i] % MOD;
	NTT(a, len, 1);
	for (int i=0; i<=n; i++)
		printf ("%lld ", a[i] * Ilen % MOD);
	return 0;
}

评测结果