代码

#include <cstdio>
#include <algorithm>
using std::reverse;

#define MOD 998244353
#define N 262210
#define re register
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
typedef long long ll;
static char buf[100000],*pa(buf),*pb(buf);
static char pbuf[3000000],*pp(pbuf),st[15];
inline int read() {
    re int x(0);re char c(gc);
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9')
        x=x*10+c-48,c=gc;
    return x;
}
inline void write(re int v) {
    if(v==0)
        *pp++=48;
    else {
        re int tp(0);
        while(v)
            st[++tp]=v%10+48,v/=10;
        while(tp)
            *pp++=st[tp--];
    }
    *pp++=32;
}

inline int pow(re int a,re int b) {
	re int ans(1);
	while(b)
		ans=b&1?(ll)ans*a%MOD:ans,a=(ll)a*a%MOD,b>>=1;
	return ans;
}

int lmt(1),r[N],w[N];
inline int getLen(re int n) {
	return 1<<(32-__builtin_clz(n));
}

inline void init(re int n) {
	re int l(0);
	while(lmt<=n)
		lmt<<=1,++l;
	for(re int i(1);i<lmt;++i)
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	re int wn(pow(3,(MOD-1)>>l));
	w[lmt>>1]=1;
	for(re int i((lmt>>1)+1);i<lmt;++i)
		w[i]=(ll)w[i-1]*wn%MOD;
	for(re int i((lmt>>1)-1);i;--i)
		w[i]=w[i<<1];
	lmt=__builtin_ctz(lmt);
}

inline void DFT(int*a,re int l) {
	static unsigned long long tmp[N];
	re int u(lmt-__builtin_ctz(l)),t;
	for(re int i(0);i<l;++i)
		tmp[i]=a[r[i]>>u];
	for(re int i(1);i<l;i<<=1)
		for(re int j(0),step(i<<1);j<l;j+=step)
			for(re int k(0);k<i;++k)
				t=tmp[i+j+k]*w[i+k]%MOD,
				tmp[i+j+k]=tmp[j+k]+MOD-t,
				tmp[j+k]+=t;
	for(re int i(0);i<l;++i)
		a[i]=tmp[i]%MOD;
}

inline void IDFT(int*a,int l) {
	reverse(a+1,a+l),DFT(a,l);
	re int bk(MOD-(MOD-1)/l);
	for(re int i(0);i<l;++i)
		a[i]=(ll)a[i]*bk%MOD;
}

int len,n,m,a[N],b[N];

int main() {
	n=read()+1,m=read()+1;
	init(n+m);
	for(re int i(0);i<n;++i)
		a[i]=read();
	for(re int i(0);i<m;++i)
		b[i]=read();
	len=getLen(n+m);
	DFT(a,len),DFT(b,len);
	for(re int i(0);i<len;++i)
		a[i]=(ll)a[i]*b[i]%MOD;
	IDFT(a,len);
	for(re int i(0);i+1<n+m;++i)
		write(a[i]);
	fwrite(pbuf,1,pp-pbuf,stdout);
	return 0;
}

评测结果