代码

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

#include <ctime>
#include <cstdio>

#define nya(neko...) fprintf(stderr, neko)

__attribute__((destructor))
inline void ptime() {
	nya("\nTime: %.3lf(s)\n", 1. * clock() / CLOCKS_PER_SEC);
}

#include <cmath>
#include <random>
#include <vector>
#include <algorithm>

using ll = long long;
using vec = std::vector<ll>;
constexpr ll mod = 998244353, gen = 3;
constexpr ll inv2 = (mod + 1) / 2;
constexpr int maxn = 4E+6 + 5;

inline ll fsp(ll a, ll b, ll res = 1) {
	for(a %= mod; b; a = a * a % mod, b >>= 1)
		b & 1 && (res = res * a % mod); return res;
}

namespace IObuf {
	using IObuf_t = int;

	constexpr int LEN = 1 << 20;
	
	char ibuf[LEN + 5], *p1 = ibuf, *p2 = ibuf;
	char obuf[LEN + 5], *p3 = obuf;
	
	inline char get() {
#ifdef WHX1003
		return getchar();
#else
		return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, LEN, stdin), p1 == p2) ? EOF : *p1++;
#endif
	}
	
	inline IObuf_t getint(char c = get(), IObuf_t x = 0, IObuf_t op = 1) {
		while(c < '0' || c > '9') c == '-' && (op = -op), c = get();
		while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = get();
		return x * op;
	}
	
	__attribute__((destructor))
	inline char* flush() { fwrite(obuf, 1, p3 - obuf, stdout); return p3 = obuf; }
	inline void put(char c) {
#ifdef WHX1003
		putchar(c);
#else
		p3 == obuf + LEN && flush(); *p3++ = c; return;
#endif
	}
	
	inline void putint(IObuf_t x, char suf = '\n') {
		static char sta[30];
		static int top = 0;
		
		if(x < 0) put('-'), x = -x;
		if(!x) put('0');
		else {
			while(x) sta[++top] = x % 10 + 48, x /= 10;
			while(top) put(sta[top--]);
		} put(suf);
	}

	inline void putstr(const char *s, char suf = '\n') {
		while(*s != '\0') put(*s++);
		put(suf);
	}
} // IObuf
using IObuf::getint;
using IObuf::putint;
using IObuf::putstr;

inline constexpr ll Add(ll x, ll y) { return x + y >= mod ? x + y - mod : x + y; }
inline constexpr ll Sub(ll x, ll y) { return x < y ? x - y + mod : x - y; }

namespace NTT_namespace {
	#define ctz(x) __builtin_ctz(x)
	
	constexpr int rank2 = ctz(mod - 1);

	ll root[rank2 + 1];   // root[i]^(2^i) == 1
	ll iroot[rank2 + 1];  // root[i] * iroot[i] == 1
	ll rate2[rank2], irate2[rank2];
	ll rate3[rank2], irate3[rank2];

	__attribute__((constructor))
	inline void NTTpre() {
		root[rank2] = fsp(gen, mod - 1 >> rank2);
		iroot[rank2] = fsp(root[rank2], mod - 2);
		for(int i = rank2 - 1; i >= 0; --i) {
			root[i] = root[i + 1] * root[i + 1] % mod;
			iroot[i] = iroot[i + 1] * iroot[i + 1] % mod;
		}

		{
			ll prod = 1, iprod = 1;
			for (int i = 0; i <= rank2 - 2; i++) {
				rate2[i] = root[i + 2] * prod % mod;
				irate2[i] = iroot[i + 2] * iprod % mod;
				prod = prod * iroot[i + 2] % mod;
				iprod = iprod * root[i + 2] % mod;
			}
		}

		{
			ll prod = 1, iprod = 1;
			for(int i = 0; i <= rank2 - 3; i++) {
				rate3[i] = root[i + 3] * prod % mod;
				irate3[i] = iroot[i + 3] * iprod % mod;
				prod = prod * iroot[i + 3] % mod;
				iprod = iprod * root[i + 3] % mod;
			}
		}
	}
	
	inline void butterfly(ll *a, int h) {
		int len = 0;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
		while(len < h) {
			if(h - len == 1) {
				int p = 1 << (h - len - 1);
				
				ll rot = 1;
				for(int s = 0; s < (1 << len); ++s) {
					int offset = s << (h - len);
					for(int i = 0; i < p; ++i) {
						ll l = a[i + offset];
						ll r = a[i + offset + p] * rot % mod;
						a[i + offset] = Add(l, r);
						a[i + offset + p] = Sub(l, r);
					}
					if(s + 1 != (1 << len))
						rot = rot * rate2[ctz(~(unsigned int)(s))] % mod;
				}
				++len;
			} else {
				// 4-base
				int p = 1 << (h - len - 2);
				ll rot = 1, imag = root[2];
				for(int s = 0; s < (1 << len); ++s) {
					ll rot2 = rot * rot % mod;
					ll rot3 = rot2 * rot % mod;
					int offset = s << (h - len);
					for(int i = 0; i < p; ++i) {
						ll mod2 = mod * mod;
						ll a0 = a[i + offset + 0 * p];
						ll a1 = a[i + offset + 1 * p] * rot;
						ll a2 = a[i + offset + 2 * p] * rot2;
						ll a3 = a[i + offset + 3 * p] * rot3;
						ll a1na3imag = (a1 + mod2 - a3) % mod * imag;
						ll na2 = mod2 - a2;

						a[i + offset] = (a0 + a2 + a1 + a3) % mod;
						a[i + offset + 1 * p] = (a0 + a2 + (2 * mod2 - (a1 + a3))) % mod;
						a[i + offset + 2 * p] = (a0 + na2 + a1na3imag) % mod;
						a[i + offset + 3 * p] = (a0 + na2 + (mod2 - a1na3imag)) % mod;
					}
					if(s + 1 != (1 << len))
						rot = rot * rate3[ctz(~(unsigned int)(s))] % mod;
				}
				len += 2;
			}
		}
	}
	
	inline void invbutterfly(ll *a, int h) {
		int len = h;  // a[i, i+(n>>len), i+2*(n>>len), ..] is transformed
		while(len) {
			if(len == 1) {
				int p = 1 << (h - len);
				
				ll irot = 1;
				for(int s = 0; s < (1 << (len - 1)); ++s) {
					int offset = s << (h - len + 1);
					for(int i = 0; i < p; ++i) {
						ll l = a[i + offset];
						ll r = a[i + offset + p];
						a[i + offset] = Add(l, r);
						a[i + offset + p] = Sub(l, r) * irot % mod;
					}
					if (s + 1 != (1 << (len - 1)))
						irot = irot * irate2[ctz(~(unsigned int)(s))] % mod;
				}
				--len;
			} else {
				// 4-base
				int p = 1 << (h - len);
				ll irot = 1, iimag = iroot[2];
				for(int s = 0; s < (1 << (len - 2)); ++s) {
					ll irot2 = irot * irot % mod;
					ll irot3 = irot2 * irot % mod;
					int offset = s << (h - len + 2);
					for(int i = 0; i < p; ++i) {
						ll a0 = a[i + offset + 0 * p];
						ll a1 = a[i + offset + 1 * p];
						ll a2 = a[i + offset + 2 * p];
						ll a3 = a[i + offset + 3 * p];
						ll a2na3iimag = Sub(a2, a3) * iimag % mod;
	
						a[i + offset] = (a0 + a1 + a2 + a3) % mod;
						a[i + offset + 1 * p] = (a0 + (mod - a1) + a2na3iimag) * irot % mod;
						a[i + offset + 2 * p] = (a0 + a1 + (mod - a2) + (mod - a3)) * irot2 % mod;
						a[i + offset + 3 * p] = (a0 + (mod - a1) + (mod - a2na3iimag)) * irot3 % mod;
					}
					if(s + 1 != (1 << (len - 2)))
						irot = irot * irate3[ctz(~(unsigned int)(s))] % mod;
				}
				len -= 2;
			}
		}
		
		int N = 1 << h;
		
		ll invN = fsp(N, mod - 2);
		for(int i = 0; i < N; ++i) a[i] = a[i] * invN % mod;
	}
		
	inline void NTT(ll *f, int bit, int op) {
		if(op == 1) butterfly(f, bit);
		else invbutterfly(f, bit);
	}

	#undef ctz
} // NTT_namespace
using NTT_namespace::NTT;

void poly_multiply(unsigned *f, int n, unsigned *g, int m, unsigned *c) {
	static ll F[maxn], G[maxn];
	for(int i = 0; i <= n; ++i) F[i] = f[i];
	for(int i = 0; i <= m; ++i) G[i] = g[i];
	
	int bit = 0, N = 1;
	while(N <= n + m) ++bit, N <<= 1;
	
	NTT(F, bit, 1), NTT(G, bit, 1);
	for(int i = 0; i < N; ++i)
		F[i] = F[i] * G[i] % mod;
	NTT(F, bit, -1);
	
	for(int i = 0; i <= n + m; ++i) c[i] = F[i];
}

评测结果