代码

#include <bits/stdc++.h>
using namespace std;

namespace io
{
	const int SIZE = 1 << 22 | 1;
	char iBuf[SIZE], *iS, *iT, c;
	char oBuf[SIZE], *oS = oBuf, *oT = oBuf + SIZE;
	#define gc() (iS == iT ? iT = iBuf + fread(iS = iBuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++) : *iS++)
	inline void flush()
	{
		fwrite(oBuf, 1, oS - oBuf, stdout);
		oS = oBuf;
	}
	inline void putc(char x)
	{
		*oS++ = c;
		if(oS == oT) flush();
	}
	template<class I> void gi(I &x)
	{
		for(c = gc(); c < '0' || c > '9'; c = gc());
		for(x = 0; c >= '0' && c <= '9'; c = gc())
			x = (x << 3) + (x << 1) + (c & 15);
	}
	template<class I> void print(I x)
	{
		char qu[21], *tail = qu;
		do *tail++ = x; while(x /= 10);
		while(qu != tail) putc(*--tail); 
	}
	struct flusher{ ~flusher() { flush(); } } _;
}

using io::gi;
using io::putc;
using io::print;

#define ull unsigned long long

const int MaxN(300003);
const int Mod(998244353);
const int g(3), invg(332748118);

int rev[MaxN];

int fexp(int x, int k)
{
	int res = 1;
	for(; k; k >>= 1, x = (ull) x * x % Mod)
		if(k & 1) res = (ull) res * x % Mod;
	return res;
}

void dft(int *a, int n, int f)
{
	for(int i = 1; i < n; i++)
		if(i < rev[i]) swap(a[i], a[rev[i]]);
	for(int l = 1; l < n; l <<= 1)
	{
		static int w[MaxN];
		int wn = fexp(f == 1 ? g : invg, (Mod - 1) / (l << 1));
		for(int i = w[0] = 1; i < l; i++)
			w[i] = (ull) w[i - 1] * wn % Mod;
		for(int i = 0; i < n; i += l << 1)
			for(int j = 0; j < l; j++)
			{
				int x = a[i + j], y = (ull) w[j] * a[i + j + l] % Mod;
				a[i + j] = (x + y) % Mod;
				a[i + j + l] = (Mod + x - y) % Mod;
			}
	}
	if(f == -1)
	{
		int invn = fexp(n, Mod - 2);
		for(int i = 0; i < n; i++)
			a[i] = (ull) a[i] * invn % Mod;
	}
}

int a[MaxN], b[MaxN];

int main()
{
	int n, m, L, k;
	freopen("fft.in", "r", stdin);
	freopen("fft.out", "w", stdout);
	gi(n), gi(m), ++n, ++m;
	for(int i = 0; i < n; i++) gi(a[i]);
	for(int i = 0; i < m; i++) gi(b[i]);
	for(L = 1, k = -1; L < n + m; L <<= 1, ++k);
	for(int i = 1; i < L; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k);
	dft(a, L, 1), dft(b, L, 1);
	for(int i = 0; i < L; i++)
		a[i] = (ull) a[i] * b[i] % Mod;
	dft(a, L, -1);
	for(int i = 0; i < n + m - 1; i++)
		printf("%d%c", a[i], " \n" [i == n + m - 2]);
	return 0;
}

评测结果