代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define mod 998244353
#define N 400050
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;
		memset(A,0,sizeof(int)*l);
		memset(B,0,sizeof(int)*l);
		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() {
	scanf("%d%d",&n,&m);n++,m++;
	int i;
	shion a(n),b(m);
	for(i=0;i<n;i++) scanf("%d",&a.a[i]);
	for(i=0;i<m;i++) scanf("%d",&b.a[i]);
	shion c=a*b;
	for(i=0;i<n+m-1;i++) printf("%d ",(c.a[i]+mod)%mod);
}

评测结果