代码

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

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 inv[1<<base],w[1<<base];
inline void init(){
	inv[1]=1;
	for(int i=2;i<(1<<base);++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
	for(int len=1;len<(1<<base);len<<=1){
		const int tmp=expow(G,MOD/(len<<1));w[len]=1;
		for(int i=1;i<len;++i) w[i|len]=1ll*w[(i-1)|len]*tmp%MOD;
	}
}

int tr[1<<base];
inline void gettr(int n){
	for(int i=0;i<n;++i)
		tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0); 
}
inline void NTT(int *a,int n,bool type){
	int i,j,len;
	static lxl T[1<<base];
	for(i=0;i<n;++i) T[tr[i]]=a[i];
	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]+MOD-tmp;T[i|j]+=tmp;
			}
	}
	for(i=0;i<n;++i) a[i]=T[i]%MOD;
	if(type) return;reverse(a+1,a+n);
	const int inv=expow(n,MOD-2);
	for(i=0;i<n;++i) a[i]=1ll*a[i]*inv%MOD;
}
inline void cdot(int *a,int *b,int n,int *c){
	for(int i=0;i<n;++i) c[i]=1ll*a[i]*b[i]%MOD;
}

int n,f[1<<base];
int m,g[1<<base];

int main(){
	int i,lim;init();
	n=read()+1;m=read()+1;
	for(i=0;i<n;++i) f[i]=read();
	for(i=0;i<m;++i) g[i]=read();
	for(lim=1;lim<(n+m-1);lim<<=1);
	gettr(lim);NTT(f,lim,1);NTT(g,lim,1);
	cdot(f,g,lim,f);NTT(f,lim,0);
	for(i=0;i<n+m-1;++i) printf("%d ",f[i]);
	return 0;
}

评测结果