代码

#include<bits/stdc++.h>
using namespace std;
typedef long long lxl;
const int MOD=998244353;
const int G=3,base=21;

int n,m;
int a[1<<base],b[1<<base],inv[1<<base];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch))(ch=='-')&&(f=-f),ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline int expow(int n,int k){
	int ans=1;
	for(;k;k>>=1,n=1ll*n*n%MOD) (k&1)&&(ans=1ll*ans*n%MOD);
	return ans;
}
int w[1<<base],tr[1<<base];
lxl T[1<<base];
inline void init(){
	int i,len;
	for(len=1;len<(1<<base);len<<=1){
		const int tmp=expow(G,MOD/(len<<1));w[len]=1;
		for(i=1;i<len;++i) w[i|len]=1ll*w[(i-1)|len]*tmp%MOD;
	}
}
inline void NTT(int *a,int n,bool type){
	int i,j,len;
	for(i=0;i<n;++i) T[i]=a[tr[i]=(tr[i>>1]>>1)|(i&1?n>>1:0)];
	for(len=1;len<n;len<<=1){
		if(len==(1<<16)) for(i=0;i<n;++i) T[i]%=MOD;
		for(i=0;i<n;i+=(len<<1))
			for(j=0;j<len;++j){
				const int tmp=1ull*T[i|j|len]*w[j|len]%MOD;
				T[i|j|len]=T[i|j]-tmp+MOD;T[i|j]+=tmp;
			}
	}
	for(i=0;i<n;++i) a[i]=T[i]%MOD;
	if(type) return;reverse(a+1,a+n);
	int inv=expow(n,MOD-2);
	for(i=0;i<n;++i) a[i]=1ll*a[i]*inv%MOD;
}

int main(){
	init();
	int i,lim;
	n=read()+1;m=read()+1;
	for(lim=1;lim<=(n+m);lim<<=1);
	for(i=0;i<n;++i) a[i]=read();
	for(i=0;i<m;++i) b[i]=read();
	NTT(a,lim,1);NTT(b,lim,1);
	for(i=0;i<lim;++i) a[i]=1ll*a[i]*b[i]%MOD;
	NTT(a,lim,0);
	for(i=0;i<n+m-1;++i) printf("%d ",a[i]);
	return 0;
} 

评测结果