代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <algorithm>
#define N 4001000
typedef long long ll;
template <typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) { if (c == '-')	flag = true; c = getchar(); }
	while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
const int P = 998244353;
const int G = 3;
const int Gi = (P + 1) / G;
int n, m;
ll A[N], B[N];
int limi = 1, r[N], L;
inline ll quickpow(ll x, int k) {
	ll res = 1;
	while (k) {
		if (k & 1)	res = res * x % P;
		x = x * x % P;
		k >>= 1;
	}
	return res;
}
inline void ntt(ll *a, int type) {
	for (register int i = 1; i < limi; ++i)
		if (i < r[i])	swap(a[i], a[r[i]]);
	for (register int i = 1; i < limi; i <<= 1) {//?
		ll T = quickpow(type == 1 ? G : Gi, (P - 1) / (i << 1));//Attention!!
		for (register int j = 0; j < limi; j += (i << 1)) {
			ll t = 1;
			for (register int k = 0; k < i; ++k, t = t * T % P) {//Attention!! : % P
				ll nx = a[j + k], ny = a[j + k + i] * t % P;
				a[j + k] = (nx + ny) % P;
				a[j + k + i] = (nx - ny + P) % P;
			}
		}
	}
	if (type == -1) {
		ll inv = quickpow(limi, P - 2);
		for (register int i = 0; i < limi; ++i)
			a[i] = a[i] * inv % P;
	}
}
inline void mul(ll *a, ll *b, int n, int m) {
	while (limi <= (n + m))	limi <<= 1, ++L;
	for (register int i = 1; i < limi; ++i)
		r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
	ntt(a, 1), ntt(b, 1);
	for (register int i = 0; i < limi; ++i)	a[i] = a[i] * b[i] % P;
	ntt(a, -1);
}
int main() {
	read(n), read(m);
	for (register int i = 0; i <= n; ++i)	read(A[i]);
	for (register int j = 0; j <= m; ++j)	read(B[j]);
	mul(A, B, n, m);
	for (register int i = 0; i <= n + m; ++i) {
		printf("%lld ", A[i]);
	}
	return 0;
}

/*
1 2
1 2
1 2 1
//1 4 5 2
*/

评测结果