代码

#include <cstdio>
#include <algorithm>

typedef unsigned long long ull;
const size_t maxL = 1 << 18 | 1;
const int Mod = 998244353;

int fexp(int base, int exp)
{
	int res = 1;
	for (; exp; exp >>= 1, base = (ull)base * base % Mod)
		if (exp & 1)
			res = (ull)res * base % Mod;
	return res;
}
inline int getinv(int x)
{
	return fexp(x, Mod - 2);
}

const int g = 3, invg = getinv(g);

int N, M;
int A[maxL], B[maxL];
int Rev[maxL];

void DFT_pre(int l, int bitcnt)
{
	for (int i = 1; i != l; ++i)
		Rev[i] = (Rev[i >> 1] >> 1) | ((i & 1) << bitcnt - 1);
}

void DFT(int *a, int n)
{
	for (int i = 1; i != n; ++i)
		if (i < Rev[i])
			std::swap(a[i], a[Rev[i]]);
	for (int l = 1; l != n; l <<= 1)
	{
		int w0 = fexp(g, (Mod - 1) / (l * 2));
		static int wn[maxL];
		wn[0] = 1;
		for (int i = 1; i != l; ++i)
			wn[i] = (ull)wn[i - 1] * w0 % Mod;
		for (int i = 0; i != n; i += l * 2)
			for (int j = 0; j != l; ++j)
			{
				int x = a[i + j], y = (ull)wn[j] * a[i + l + j] % Mod;
				a[i + j] = (x + y) % Mod;
				a[i + l + j] = (x + Mod - y) % Mod;
			}
	}
}

void iDFT(int *a, int n)
{
	for (int i = 1; i != n; ++i)
		if (i < Rev[i])
			std::swap(a[i], a[Rev[i]]);
	for (int l = 1; l != n; l <<= 1)
	{
		int w0 = fexp(invg, (Mod - 1) / (l * 2));
		static int wn[maxL];
		wn[0] = 1;
		for (int i = 1; i != l; ++i)
			wn[i] = (ull)wn[i - 1] * w0 % Mod;
		for (int i = 0; i != n; i += l * 2)
			for (int j = 0; j != l; ++j)
			{
				int x = a[i + j], y = (ull)wn[j] * a[i + l + j] % Mod;
				a[i + j] = (x + y) % Mod;
				a[i + l + j] = (x + Mod - y) % Mod;
			}
	}
	int inv = getinv(n);
	for (int i = 0; i != n; ++i)
		a[i] = (ull)a[i] * inv % Mod;
}

int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0; i <= N; ++i)
		scanf("%d", A + i);
	for (int i = 0; i <= M; ++i)
		scanf("%d", B + i);
	
	int l = 1, bitcnt = 0;
	
	while (l <= N + M)
		l <<= 1, ++bitcnt;
	
	DFT_pre(l, bitcnt);
	DFT(A, l);
	DFT(B, l);
	
	for (int i = 0; i != l; ++i)
		A[i] = (ull)A[i] * B[i] % Mod;
	
	iDFT(A, l);
	
	for (int i = 0; i <= N + M; ++i)
		printf("%d%c", A[i], " \n"[i == N + M]);

	return 0;
}

评测结果