代码

#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)
{
	if (!x) return (void)(putchar('0')); 
	static char buf[15]; 
	static char *tail = buf; 
	for (; x; x /= 10) *++tail = x % 10 + '0'; 
	for (; tail != buf; --tail) putchar(*tail); 
}

const int MaxN = 1e6 + 5; 
const int mod = 998244353; 
//g = 3, mod = 119 * 2^23 + 1

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

inline int inc(int a, const int &b)
{
	a += b; return a >= mod ? a - mod : a; 
}

inline int dec(int a, const int &b)
{
	a -= b; return a < 0 ? a + mod : a; 
}

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, int n, const int &opt)
{
	for (int i = 0; i < n; ++i)
		if (i < rev[i]) std::swap(a[i], a[rev[i]]); 
	int g = opt == 1 ? 3 : 332748118; 
	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; 
				a[i + j] = inc(u, v), a[i + j + k] = dec(u, v); 
				x = 1LL * x * omega % mod; 
			}
		}
	}
}

int main()
{
	read(n), read(m); 
	for (int i = 0; i <= n; ++i) read(a[i]); 
	for (int i = 0; i <= m; ++i) read(b[i]); 
	
	L = 1; 
	while (n + m >= L) L <<= 1, ++K; 
	
	for (int i = 1; i <= L; ++i)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << K - 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); 
	
	int inv = qpow(L, mod - 2); 
	for (int i = 0; i <= n + m; ++i)
		putint(1LL * a[i] * inv % mod), putchar(' '); 
	
	return 0; 
}

评测结果