代码

#include <bits/stdc++.h>

template <class T>
inline void read(T &x)
{
	static char ch; 
	while (!isdigit(ch = getchar())); 
	x = ch - '0'; 
	while (isdigit(ch = getchar()))
		x = x * 10 + ch - '0'; 
}

template <class T>
inline void putint(T x)
{
	static char buf[15], *tail = buf; 
	if (!x) return (void)(putchar('0')); 
	for (; x; x /= 10) *++tail = x % 10 + '0'; 
	for (; tail != buf; --tail) putchar(*tail); 
}	

const int MaxN = 1e6 + 5; 
const int mod = 998244353; 

int n, m, rev[MaxN], a[MaxN], b[MaxN]; 
int P, L; 

inline void add(int &x, const int &y)
{
	x += y; 
	if (x >= mod) x -= mod; 
	if (x < 0) x += mod; 
}

inline void poly_init(int n)
{
	P = 0, L = 1; 
	while (L < n) L <<= 1, ++P; 
	for (int i = 1; i < L; ++i)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << P - 1); 
}

inline int qpow(int a, int b)
{
	int res = 1; 
	for (; b; b >>= 1, a = 1LL * a * a % mod)
		if (b & 1) res = 1LL * res * a % mod;
	return res;  
}

inline void DFT(int *a, const int &n, const int &opt)
{
	for (int i = 1; i < n; ++i)
		if (i < rev[i]) std::swap(a[i], a[rev[i]]); 
	
	int g = opt == 1 ? 3 : (mod + 1) / 3; 
	for (int k = 1; k < n; k <<= 1)
	{
		int omega = qpow(g, (mod - 1) / (k << 1)); 
		for (int i = 0; i < n; i += k << 1)
		{
			int x = 1; 
			for (int j = 0; j < k; ++j)
			{
				int u = a[i + j], v = 1LL * a[i + j + k] * x % mod; 
				add(a[i + j] = u, v); 
				add(a[i + j + k] = u, -v); 
				x = 1LL * x * omega % mod; 
			}
		}
	}
	
	if (opt == -1)
	{
		int inv = qpow(n, mod - 2); 
		for (int i = 0; i < n; ++i)
			a[i] = 1LL * a[i] * inv % mod; 
	}
}

int main()
{
#ifdef orzczk
	freopen("weak.in", "r", stdin); 
#endif

	read(n), read(m); ++n, ++m; 
	for (int i = 0; i < n; ++i) read(a[i]); 
	for (int i = 0; i < m; ++i) read(b[i]); 
	
	poly_init(n + m - 1); 
	DFT(a, L, 1), DFT(b, L, 1); 
	
	for (int i = 0; i < L; ++i) a[i] = 1LL * a[i] * b[i] % mod; 
	
	DFT(a, L, -1); 
	
	for (int i = 0; i < n + m - 1; ++i)
		putint(a[i]), putchar(" \n"[i == n + m - 2]); 
	
	return 0; 
}

评测结果