代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)

#define Lep(i, l, r) for (int i = (l), i##_end = (r); i < i##_end; ++ i)
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)

char buf[1 << 23], *p1 = buf, *p2 = buf;
inline int getc () {
	return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 23, stdin), p1 == p2) ? EOF : *p1 ++ ;
}
char __c; bool _f2; template <class T> inline void IN (T & x) {
	_f2 = 0, x = 0; while (__c = getc (), ! isdigit (__c)) if (__c == '-') _f2 = 1;
	while (isdigit (__c)) x = x * 10 + __c - '0', __c = getc (); if (_f2) x = -x;
}

const int mod = 998244353;

inline int mul (int x, int y) { return 1ll * x * y % mod; }
inline int qpow (int x, int y, int r = 1) { for ( ; y; y >>= 1, x = mul (x, x)) if (y & 1) r = mul (r, x); return r; }

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

const int N = (1 << 21) | 5;

// {{{ poly

namespace Poly {
	const int Lim = 1 << 21;

	typedef unsigned long long ull;
	#define Lep(i, l, r) for (int i = (l), i##_end = (r); i < i##_end; ++ i)

	int w[N];
	ull _g[N];

	inline void init_w () {
		* w = 1, w[1 << 21] = qpow (3, (mod - 1) >> 23);
		rep (i, 21, 1) w[1 << i - 1] = mul (w[1 << i], w[1 << i]);
		Lep (i, 1, Lim) w[i] = mul (w[i & (i - 1)], w[i & ( - i)]);
	}

	struct poly {
		int lim;
		vector <int> a;

		inline int size () { return (int) a.size (); }
		inline int & operator [] (const int &x) { return a[x]; }
		inline void clear () { vector <int> ().swap (a); }
		inline void resize (const int &x) { a.resize (lim = x); }

		poly (int n = 0) { resize (lim = n); }
		poly (const vector <int> &o) { a = o, lim = size (); }
		poly (const poly &o) { a = o.a, lim = size (); }

				inline void dif () {
			int s, p, * tw; ull * tg, * pg;
			for (p = lim >> 1; p; p >>= 1)
				for (tg = _g, tw = w; tg != _g + lim; tg += p << 1, ++ tw)
					for (pg = tg; pg != tg + p; ++ pg)
						s = 1ll * pg[p] * * tw % mod, pg[p] = * pg + mod - s, * pg += s;
		}
		inline void dit () {
			int s, p, * tw; ull * tg, * pg;
			for (p = 1; p < lim; p <<= 1)
				for (tg = _g, tw = w; tg != _g + lim; tg += p << 1, ++ tw)
					for (pg = tg; pg != tg + p; ++ pg)
						s = pg[p] % mod, pg[p] = 1ll * ( * pg + mod - s) * * tw % mod, * pg += s;
		}

		inline void dft () {
			copy_n (a.begin (), lim, _g), dif ();
			Lep (i, 0, lim) a[i] = _g[i] % mod;
		}
		inline void idft () {
			copy_n (a.begin (), lim, _g), dit ();
			for (int iv = mod - (mod - 1) / lim, i = 0; i < lim; ++ i) a[i] = mul (_g[i] % mod, iv);
			reverse ( ++ a.begin (), a.end ());
		}

		inline poly inv () {
			poly b (1), c; b[0] = qpow (a[0], mod - 2);
			for (int i = 1; i < lim; i <<= 1) {
				c = a, c.resize (i << 1);
				c.resize (i << 2), c.dft (), b.resize (i << 2), b.dft ();
				Lep (j, 0, i << 2) b[j] = mul (b[j], dec (2, mul (b[j], c[j])));
				b.idft (), b.resize (i << 1);
			}
			return b.resize (a.size ()), b;
		}
	};
}

using Poly :: init_w;
using Poly :: poly;

// }}}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
init_w (), ++ n, ++ m;
poly f(n); Lep (i, 0, n) f[i] = a[i];
poly g(m); Lep (i, 0, m) g[i] = b[i];

int lim;
for (lim = 1; lim < n + m - 1; lim <<= 1);
f.resize (lim), f.dft (), g.resize (lim), g.dft ();
Lep (i, 0, lim) f[i] = mul (f[i], g[i]);
f.idft ();

Lep (i, 0, n + m - 1) c[i] = f[i];
}

评测结果