代码

#include<cstdio>
#include<algorithm>
#include<cstring>

#include<vector>
#include<cmath>

#include<cstdlib>
#include<cassert>
#include<ctime>

typedef long long ll;
typedef std::vector<ll> vec;
const ll mod = 998244353;
const ll gen = 3, img = 86583718;
const int maxn = 1E+5 + 5;

namespace IObuf {
	const int LEN = 1 << 20;
	
	char ibuf[LEN + 5], *p1 = ibuf, *p2 = ibuf;
	char obuf[LEN + 5], *p3 = obuf;
	
	inline char get() {
#ifdef ONLINE_JUDGE
		return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, LEN, stdin), p1 == p2) ? EOF : *p1++;
#endif
		return getchar();
	}
	inline ll getll(char c = get(), ll x = 0) {
		while(c < '0' || c > '9') c = get();
		while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = get();
		return x;
	}
	
	inline char* flush() { fwrite(obuf, 1, p3 - obuf, stdout); return p3 = obuf; }
	inline void put(char c) {
#ifdef INLINE_JUDGE
		p3 == obuf + LEN && flush(); *p3++ = c; return;
#endif
		putchar(c);
	}
	
	char s[20]; int t = 0;
	inline void putll(ll x, char suf = ' ') {
		if(!x) put('0');
		else {
			while(x) s[++t] = x % 10 + 48, x /= 10;
			while(t) put(s[t--]);
		} put(suf);
	}
}
using IObuf::getll;
using IObuf::putll;

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

namespace Cipolla {
	ll imgn;
	
	struct complex {
		ll re, im;
		inline complex(ll _r = 0, ll _i = 0) : re(_r), im(_i) {}
		inline complex operator*(const complex &d) const {
			return complex((re * d.re + im * d.im % mod * imgn) % mod, (re * d.im + im * d.re) % mod);
		}
	};
	
	inline complex mod_fsp(complex a, ll b, complex res = 1) {
		for(b %= mod - 1; b; a = a * a, b >>= 1)
			if(b & 1) res = res * a; return res;
	}
	
	inline ll solve(ll x) {
		if(mod == 2 || !x) return x;
		
		ll a = 0;
		while(true) {
			a = 1ll * rand() * rand() % mod;
			if(fsp(mod + a * a - x, mod - 1 >> 1) == mod - 1) break;
		} imgn = (a * a - x + mod) % mod;
		
		ll ans = mod_fsp(complex(a, 1), mod + 1 >> 1).re;
		return std::min(ans, mod - ans);
	}
}

namespace Poly {
	struct poly {
		vec f;
		
		// init
		
		inline poly(ll v = 0) : f(1) { f[0] = v; }
		inline poly(const vec &_f) : f(_f) {}
		inline poly(std::initializer_list<ll> init) : f(init) {}
		
		// tools
		
		inline ll operator[](int p) const { return p < f.size() ? f[p] : 0; }
		inline ll &operator[](int p) { if(p >= f.size()) f.resize(p + 1); return f[p]; }
		
		inline int deg() const { return f.size() - 1; }
		inline void redeg(int d) { f.resize(d + 1); }
		
		inline poly slice(int d) const {
			if(d < f.size())
				return vec(f.begin(), f.begin() + d + 1);
			
			vec res(f);
			return res.resize(d + 1), res;
		}
	
		inline void print(int d) const {
			for(int i = 0; i <= d; ++i)
				putll(operator[](i));
			IObuf::put('\n');
		}
		
		inline ll calc(ll x) const {
			ll res = 0, tmp = 1;
			for(int i = 0; i <= deg(); ++i) {
				(res += f[i] * tmp) %= mod;
				(tmp *= x) %= mod;
			} return res;
		}
		
		// operators
		
		inline poly operator+(const poly &P) const {
			vec res(std::max(f.size(), P.f.size()));
			for(int i = 0; i < res.size(); ++i)
				(res[i] = operator[](i) + P[i]) >= mod && (res[i] -= mod);
			return res;
		}
		
		inline poly operator-() const {
			poly res(f);
			for(int i = 0; i < f.size(); ++i)
				res[i] && (res[i] = mod - res[i]);
			return res;
		}
		
		inline poly operator-(const poly &P) const { return operator+(-P); }
		
		inline poly operator<<(int d) const {
			poly res;
			for(int i = 0; i <= deg(); ++i)
				res[i + d] = operator[](i);
			return res;
		}
		
		inline poly operator>>(int d) const {
			if(d > deg()) return poly(0);
			return vec(f.begin() + d, f.end());
		}
		
		inline poly operator*(const ll v) const {
			poly res(f);
			for(int i = 0; i <= deg(); ++i)
				(res[i] *= v) %= mod;
			return res;
		}
		
		inline poly operator*(const poly &P) const;			// redeg to max(deg(), P.deg())
		inline poly operator/(const poly &P) const;
		inline poly operator%(const poly &P) const;
		
		inline poly mul(const poly &P) const;				// redeg to deg() + P.deg()
		
		inline poly intg(ll C) const;
		inline poly der() const;
		
		inline poly inv() const;
		inline poly ln() const;
		inline void divexp(poly &res, int l, int r) const;
		inline poly exp() const;
		
		inline poly pow(ll k) const;
		
		inline poly sqrt() const;
	};
	
	int Len = -1, rev[maxn << 2], rt[maxn << 3];
	inline void NTTpre(int bit) {
		for(int i = Len + 1; i <= bit; ++i) {
			ll stp = fsp(gen, mod - 1 >> i);
			
			rt[1 << i] = 1;
			for(int j = (1 << i) + 1; j < (1 << i + 1); ++j)
				rt[j] = rt[j - 1] * stp % mod;
		} Len = bit;
	}
	
	unsigned long long tmp[maxn << 2];
	inline void NTT(poly &f, int bit, int op) {
		if(Len < bit) NTTpre(bit);
		
		int N = 1 << bit;
		for(int i = 0; i < N; ++i) {
			rev[i] = (rev[i >> 1] >> 1 | (i & 1) << bit - 1);
			tmp[i] = f[rev[i]] + (f[rev[i]] >> 31 & mod);		// magic
		}
		
		for(int len = 1; len < N; len <<= 1) {
			for(int i = 0; i < N; i += len << 1) {
				for(int k = i; k < i + len; ++k) {
					ll g = tmp[k], h = tmp[k + len] * rt[(len << 1) + k - i] % mod;
					tmp[k] = g + h, tmp[k + len] = mod + g - h;
				}
			}
		}
		
		for(int i = 0; i < N; ++i) f[i] = tmp[i] % mod;
		if(op == -1) {
			reverse(f.f.begin() + 1, f.f.begin() + N);
			
			ll invN = fsp(N, mod - 2);
			for(int i = 0; i < N; ++i)
				f[i] = f[i] * invN % mod;
		}
	}
	
	bool WayToDeg = 0;
	inline poly poly::operator*(const poly &P) const {
		poly F(f), G = P;
		
		int bit = ceil(log2(F.deg() + G.deg() + 1));
		int N = 1 << bit;
		
		NTT(F, bit, 1), NTT(G, bit, 1);
		for(int i = 0; i < N; ++i)
			(F[i] *= G[i]) %= mod;
		NTT(F, bit, -1);
		
		if(!WayToDeg) return F.slice(std::max(deg(), P.deg()));
		else return F.slice(deg() + P.deg());
	}
	
	inline poly poly::operator/(const poly &P) const {
		if(deg() < P.deg()) return 0;
		
		poly g = vec(f.rbegin(), f.rend());
		poly h = vec(P.f.rbegin(), P.f.rend());
		
		g.redeg(deg() - P.deg()), h.redeg(deg() - P.deg());
		poly res = g * h.inv();
		
		res.redeg(deg() - P.deg());
		reverse(res.f.begin(), res.f.end());
		
		return res;
	}
	
	inline poly poly::operator%(const poly &P) const {
		return operator-(operator/(P) * P).slice(P.deg() - 1);
	}

	inline poly poly::mul(const poly &P) const {
		WayToDeg = 1; poly H = operator*(P);
		return WayToDeg = 0, H;
	}
	
	inline poly poly::inv() const {
		poly g = fsp(f[0], mod - 2), h, g0;
		for(int stp = 1; (1 << stp - 1) <= deg(); ++stp) {
			int N = 1 << stp; h = slice(N - 1), g0 = g;
			
			NTT(g, stp, 1), NTT(h, stp, 1);
			for(int i = 0; i < N; ++i)
				h[i] = h[i] * g[i] % mod;
			NTT(h, stp, -1), h.redeg(N - 1);
			for(int i = 0; i < (N >> 1); ++i) h[i] = 0;
			
			NTT(h, stp, 1);
			for(int i = 0; i < N; ++i)
				g[i] = g[i] * h[i] % mod;
			NTT(g, stp, -1);
			
			for(int i = 0; i < (N >> 1); ++i) g[i] = 0;
			g = (g0 - g).slice(N - 1);
		} return g.slice(deg());
	}
	
	inline poly poly::der() const {
		poly res;
		for(int i = 1; i <= deg(); ++i)
			res[i - 1] = f[i] * i % mod;
		return res;
	}
	
	inline poly poly::intg(ll C = 0) const {
		poly res = C;
		for(int i = 0; i <= deg(); ++i)
			res[i + 1] = f[i] * fsp(i + 1, mod - 2) % mod;
		return res;
	}
	
	inline poly poly::ln() const { return (inv() * der()).intg().slice(deg()); }
	
	inline void poly::divexp(poly &res, int l, int r) const {
		if(l == r) {
			if(l == 0) res[l] = 1;
			else res[l] = fsp(l, mod - 2, res[l]) % mod;
			return;
		}
		
		int mid = l + r >> 1; divexp(res, l, mid);
		int bit = ceil(log2(r - l + 1)), N = 1 << bit;
		
		poly F1, F2; F1.redeg(mid - l + 1), F2.redeg(r - l + 1);
		for(int i = l; i <= mid; ++i) F1[i - l] = res[i];
		for(int i = l; i <= r; ++i) F2[i - l] = f[i - l] * (i - l) % mod;
		
		Poly::NTT(F1, bit, 1), Poly::NTT(F2, bit, 1);
		for(int i = 0; i < N; ++i) F1[i] = F1[i] * F2[i] % mod;
		Poly::NTT(F1, bit, -1);
		
		for(int i = mid + 1; i <= r; ++i) (res[i] += F1[i - l]) %= mod;
		divexp(res, mid + 1, r);
	}
	
	inline poly poly::exp() const {	poly res; return divexp(res, 0, deg()), res; }
	inline poly poly::pow(ll k) const { return (ln() * k).exp(); }
	
	inline poly poly::sqrt() const {
		poly g = Cipolla::solve(operator[](0)), h, j;
		for(int stp = 1; (1 << stp - 1) <= deg(); ++stp) {
			int N = 1 << stp + 1;
			
			h = slice((N >> 1) - 1), j = (g + g).slice((N >> 1) - 1).inv();
			
			NTT(g, stp + 1, 1), NTT(h, stp + 1, 1), NTT(j, stp + 1, 1);
			for(int i = 0; i < N; ++i)
				g[i] = (g[i] * g[i] % mod + h[i]) * j[i] % mod;
			NTT(g, stp + 1, -1), g.redeg((N >> 1) - 1);
		} return g.slice(deg());
	}
}
using Poly::poly;

int main() {
	int n = getll(), m = getll(); poly F, G;
	for(int i = 0; i <= n; ++i) F[i] = getll();
	for(int i = 0; i <= m; ++i) G[i] = getll();
	F.mul(G).print(n + m), IObuf::flush();
}

评测结果