代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(a) (int)a.size()
#define de(a) cerr << #a << " = " << a << endl
#define dd(a) cerr << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define pw(x) (1ll<<(x))
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
#define rsz(a, x) (a.resize(x))
typedef unsigned uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;

struct FIO {
	char s[1<<20|1], *p1, *p2;
	char buf[1<<20|1], *p;
	inline FIO() { p1=p2=s; p=buf; }
	inline void flush() { p-=fwrite(buf, 1, p-buf, stdout); }
	inline ~FIO() { flush(); }
	inline char gc() {
		return (p1==p2)&&(p2=(p1=s)+fread(s, 1, 1<<20, stdin), p1==p2)?EOF:*(p1++);
	}
	inline FIO& operator >> (uint &x) {
		x=0;
		char c=0;
		while(!isdigit(c)) c=gc();
		while(isdigit(c)) x=x*10+c-'0', c=gc();
		return *this;
	}
	inline FIO& operator << (char c) {
		if(p-buf>>20) flush();
		*(p++)=c;
		return *this;
	}
	inline FIO& operator << (char *s) {
		for(char *t=s; *t; ++t) *this<<*t;
		return *this;
	}
	inline FIO& operator << (uint x) {
		static char tmp[20]={0};
		char *t=tmp+19;
		if(x==0)
			return *this<<'0';
		for(;x;x/=10)
			*(--t)=x%10+'0';
		return *this<<t;
	}
}fio;

const uint P=998244353;
inline uint kpow(uint a, ull x, uint p=P) { uint ans=1; for(; x; x>>=1, a=(ull)a*a%p) if(x&1) ans=(ull)ans*a%p; return ans; }
inline int exgcd(int a, int b, int &x, int &y) {
	static int g;
	return b?(exgcd(b, a%b, y, x), y-=a/b*x, g):(x=1, y=0, g=a);
}
inline int inv(int a, int p=P) {
	static int x, y;
	return exgcd(a, p, x, y)==1?(x<0?x+p:x):(-1);
}

const int LimBit=17;//<=22
const int M=1<<LimBit<<1;
namespace Poly{
	const uint G=3;
	inline uint norm(uint v) { return v>=P?v-P:v; }
	struct vir {
		uint v;
		vir(uint v_=0):v(norm(v_)) {}
		inline vir& operator += (const vir &x) { v=norm(v+x.v); return *this; }
		inline vir& operator -= (const vir &x) { v=norm(v+P-x.v); return *this; }
		inline vir& operator *= (const vir &x) { v=(ull)v*x.v%P; return *this; }
		inline vir operator + (const vir &x) const { vir y=*this; return y+=x; }
		inline vir operator - (const vir &x) const { vir y=*this; return y-=x; }
		inline vir operator * (const vir &x) const { vir y=*this; return y*=x; }
		
		inline vir operator - () const { return vir(P-v); }
		inline vir operator ! () const { return vir(inv(v)); }
		inline operator uint() const { return v; }
	};
	typedef vir Z;
	struct poly : public vector<Z> {
		inline friend FIO& operator << (FIO& out, const poly &p) {
			if(!p.empty()) out<<(uint)p[0];
			for(int i=1; i<sz(p); ++i) out<<' '<<(uint)p[i];
			return out;
		}
	};
	
	int N, Stk[M], curStk;
	Z Inv[M];
	vir invN, w[M>>1];
	inline void init() {
		curStk=0;
		Inv[1]=1;
		for(int i=2; i<M; ++i)
			Inv[i]=-Z(P/i)*Inv[P%i];
		
		w[0]=1; w[M>>2]=kpow(G, (P-1)/M);
		for(int i=M>>3; i; i>>=1) w[i]=w[i<<1]*w[i<<1];
		for(int i=1; i<(M>>1); ++i) w[i]=w[i&(i-1)]*w[i&-i];
	}
	
	inline void dft(vir *a) {
		for(int i=N>>1; i; i>>=1)
			for(vir *j=a, *o=w, x; j!=a+N; j+=i<<1, ++o)
				for(vir *k=j; k!=j+i; ++k)
					x=*o*k[i], k[i]=*k-x, *k+=x;
	}
	inline void idft(vir *a) {
		for(int i=1; i<N; i<<=1)
			for(vir *j=a, *o=w, x; j!=a+N; j+=i<<1, ++o)
				for(vir *k=j; k!=j+i; ++k)
					x=*k+k[i], k[i]=*o*(*k-k[i]), *k=x;
		reverse(a+1, a+N);
		for(int i=0; i<N; ++i) a[i]*=invN;//NTT/3-mod-NTT/big-mod-NTT
		//for(int i=0;i<N;++i) a[i]=vir(a[i].r/N, a[i].i/N);//FFT/MTT
	}
	vir p1[M], p0[M];
	inline void get_mul(poly &a, poly &b, int na, int nb) {//3*FFT
		na=min(na, sz(a)); nb=min(nb, sz(b));
		int d=__lg(na+nb-2)+1; N=pw(d);
		invN=!vir(N);//NTT/big-mod-NTT
		//invN=!vir(N, N, N);//3-mod-NTT
		for(int i=0; i<na; ++i) p1[i]=(vir)a[i]; for(int i=na;i<N;++i) p1[i]=vir();
		for(int i=0; i<nb; ++i) p0[i]=(vir)b[i]; for(int i=nb;i<N;++i) p0[i]=vir();
		dft(p1); dft(p0);
		for(int i=0;i<N;++i) p1[i]*=p0[i];
		idft(p1);
		rsz(a, na+nb-1); for(int i=0; i<sz(a); ++i) a[i]=p1[i];
	}
}

using Poly::poly;

uint n, m;
poly a, b;
inline void work() {
	Poly::get_mul(a, b, n, m);
	fio<<a;
}
inline void init() {
	Poly::init();
	fio>>n>>m;
	rsz(a, ++n);
	uint v;
	for(int i=0; i<n; ++i)
		fio>>v, a[i]=v;
	rsz(b, ++m);
	for(int i=0; i<m; ++i)
		fio>>v, b[i]=v;
}

int main() {
	init();
	work();
	return 0;
}

评测结果