代码

#include <cstdio>
#include <cctype>
#include <algorithm>

typedef unsigned int uint;
typedef long long unsigned int uint64;

struct IO_Tp
{
	const static int _I_Buffer_Size = 2 << 20;
	char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;
	
	const static int _O_Buffer_Size = 2 << 20;
	char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;
	
	IO_Tp()
	{
		fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
	}
	
	~IO_Tp()
	{
		fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);
	}
	
	IO_Tp &operator>>(int &res)
	{
		while (!isdigit(*_I_pos))
			++_I_pos;
		res = *_I_pos++ & 15;
		while (isdigit(*_I_pos))
			(res *= 10) += *_I_pos++ & 15;
		return *this;
	}
	
	IO_Tp &operator>>(uint &res)
	{
		while (!isdigit(*_I_pos))
			++_I_pos;
		res = *_I_pos++ & 15;
		while (isdigit(*_I_pos))
			(res *= 10) += *_I_pos++ & 15;
		return *this;
	}
	
	IO_Tp &operator<<(uint n)
	{
		static char _buf[10];
		char* _pos = _buf;
		do
			*_pos++ = '0' + n % 10;
		while (n /= 10);
		while (_pos != _buf)
			*_O_pos++ = *--_pos;
		return *this;
	}
	
	IO_Tp &operator<<(char ch)
	{
		*_O_pos++ = ch;
		return *this;
	}
} IO;

constexpr uint Max_size = 1 << 18 | 5, Mod = 998244353;

struct Z
{
	uint v;
	Z(const uint _v = 0) : v(_v) { }
};

inline Z operator+(const Z &x1, const Z &x2) { return x1.v + x2.v < Mod ? x1.v + x2.v : x1.v + x2.v - Mod; }
inline Z operator-(const Z &x1, const Z &x2) { return x1.v >= x2.v ? x1.v - x2.v : x1.v + Mod - x2.v; }
inline Z operator*(const Z &x1, const Z &x2) { return static_cast<uint64>(x1.v) * x2.v % Mod; }
inline Z &operator*=(Z &x1, const Z &x2) { x1.v = static_cast<uint64>(x1.v) * x2.v % Mod; return x1; }

Z Power(Z Base, int Exp)
{
	Z res = 1;
	for (; Exp; Base *= Base, Exp >>= 1)
		if (Exp & 1)
			res *= Base;
	return res;
}

int size;
int bitrev[Max_size];
Z w[Max_size];

inline void init(int n)
{
	for (size = 1; size < n; size <<= 1)
		;
	for (int i = 0; i < size; ++i)
		bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) * (size >> 1));
	Z pr = Power(3, (Mod - 1) / size);
	w[size / 2] = 1;
	for (int i = 1; i < size / 2; ++i)
		w[size / 2 + i] = w[size / 2 + i - 1] * pr;
	for (int i = size / 2 - 1; i; --i)
		w[i] = w[i << 1];
}

inline void DFT(Z A[], int L)
{
	static uint64 t[Max_size];
	int shift = __builtin_ctz(size) - __builtin_ctz(L);
	for (int i = 0; i != L; ++i)
		t[bitrev[i] >> shift] = A[i].v;
	for (int d = 1; d != L; d <<= 1)
		for (int i = 0; i != L; i += d << 1)
			for (int j = 0; j != d; ++j)
			{
				uint64 tmp = t[i + d + j] * w[d + j].v % Mod;
				t[i + d + j] = t[i + j] + Mod - tmp, t[i + j] = t[i + j] + tmp;
			}
	for (int i = 0; i != L; ++i)
		A[i].v = t[i] % Mod;
}

inline void IDFT(Z A[], int L)
{
	std::reverse(A + 1, A + L);
	DFT(A, L);
	Z Inv_L = Power(L, Mod - 2);
	for (int i = 0; i != L; ++i)
		A[i] *= Inv_L;
}

int N, M, L;
Z A[Max_size], B[Max_size];

int main(int argc, char **argv)
{
	IO >> N >> M;
	for (int i = 0; i <= N; ++i)
		IO >> A[i].v;
	for (int i = 0; i <= M; ++i)
		IO >> B[i].v;
	
	for (L = 2; L <= N + M; L <<= 1)
		;
	init(L);
	
	DFT(A, L), DFT(B, L);
	for (int i = 0; i != L; ++i)
		A[i] *= B[i];
	IDFT(A, L);
	
	for (int i = 0; i <= N + M; ++i)
		IO << A[i].v << ' ';
	
	return 0;
}

评测结果