代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define mod 998244353
#define N 400050
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
	int x=0; char s=nc();
	while(s<'0') s=nc();
	while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();
	return x;
}
char pbuf[2000000],*pp=pbuf;
void write(int x) {
	static int sta[20],tp=0;
	do {sta[++tp]=x%10,x/=10;}while(x);
	while(tp)*pp++=sta[tp--]+'0';
	*pp++=' ';
}
int mem[N*20],*ptr=mem;
int qp(int x,int y) {int re=1;for(;y;y>>=1,x=ll(x)*x%mod)if(y&1)re=ll(re)*x%mod; return re;}
int INV(int x) {return qp(x,mod-2);}
void ntt(int *a,int len,int flg) {
	int i,j,k,t,tmp,w,wn;
	for(i=k=0;i<len;i++) {
		if(i>k) swap(a[i],a[k]);
		for(j=len>>1;(k^=j)<j;j>>=1) ;
	}
	for(k=2;k<=len;k<<=1) {
		wn=qp(3,(mod-1)/k);
		t=k>>1; 
		if(flg==-1) wn=INV(wn);
		for(i=0;i<len;i+=k) {
			w=1;  
			for(j=i;j<i+t;j++) {
				tmp=ll(a[j+t])*w%mod;
				a[j+t]=(a[j]-tmp)%mod; 
				a[j]=(a[j]+tmp)%mod; 
				w=ll(w)*wn%mod;
			}
		}
	}
	if(flg==-1) for(tmp=INV(len),i=0;i<len;i++) a[i]=ll(a[i])*tmp%mod;
}
int A[N],B[N];
struct shion {
	int *a,len;
	shion() {}
	shion(int l) {len=l,a=ptr,ptr+=l;}
	void fix(int l) {len=l,a=ptr,ptr+=l;}
	shion operator * (const shion &u) const {
		shion re(len+u.len-1);
		int i,l=1,j;
		if(re.len<=100) {
			for(i=0;i<len;i++)for(j=0;j<u.len;j++) {
				re.a[i+j]=(re.a[i+j]+ll(a[i])*u.a[j])%mod;
			}return re;
		}
		while(l<len+u.len)l<<=1;
		for(i=0;i<len;i++) A[i]=a[i];
		for(i=0;i<u.len;i++) B[i]=u.a[i];
		ntt(A,l,1),ntt(B,l,1);
		for(i=0;i<l;i++) A[i]=ll(A[i])*B[i]%mod;
		ntt(A,l,-1);
		for(i=0;i<re.len;i++) re.a[i]=A[i];
		return re;
	}
};
int n,m;
int main() {
	n=rd(),m=rd();n++,m++;
	int i;
	shion a(n),b(m);
	for(i=0;i<n;i++) a.a[i]=rd();
	for(i=0;i<m;i++) b.a[i]=rd();
	shion c=a*b;
	for(i=0;i<n+m-1;i++) write((c.a[i]+mod)%mod);
	fwrite(pbuf,1,pp-pbuf,stdout);
}

评测结果