代码

#include<bits/stdc++.h>
using namespace std;

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

const int SIZE=2e6;
char buf[SIZE],*p1,*p2,*p3;
#define getchar() (*p1++)
void rd(int &s) {
	static char IO; s=0;
	while(IO=getchar(),IO<48);
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(IO=getchar(),IO>=48);
}
void wt(int x){
	if(!x) *p2++='0';
	else {
		p3=p2;
		for(;x;x/=10) *p2++=x%10+'0',x/=10;
		reverse(p3,p2);
	}
}

const int N=1<<18,P=998244353;

int n,m;
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int a[N],b[N],w[N],rev[N],e[N];
void NTT(int n,int *a,int f){
	rep(i,1,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
	e[0]=1;
	for(int i=1;i<n;i<<=1) {
		int w=qpow(3,(P-1)/i/2);
		//for(int j=1;j<i;++j) e[j]=1ll*e[j-1]*w%P;
		for(int j=i-2;j>=0;j-=2) e[j+1]=1ll*w*(e[j]=e[j>>1])%P;
		//这个版本是沿用上一次预处理的结果
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				int t=1ll*a[j+i]*e[j-l]%P;
				a[j+i]=a[j]-t,((a[j+i]<0)&&(a[j+i]+=P));
				a[j]+=t,((a[j]>=P)&&(a[j]-=P));
			}
		}
	}
	if(f==-1) {
		reverse(a+1,a+n);
		int Inv=qpow(n);
		rep(i,0,n-1) a[i]=1ll*a[i]*Inv%P;
	}
}

int main(){
	p2=(p1=buf)+fread(buf,1,SIZE,stdin);
	rep(i,0,N-1) rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
	rd(n),rd(m);
	rep(i,0,n) rd(a[i]);
	rep(i,0,m) rd(b[i]);
	NTT(N,a,1),NTT(N,b,1);
	rep(i,0,N-1) a[i]=1ll*a[i]*b[i]%P;
	NTT(N,a,-1);
	p1=p2=buf;
	rep(i,0,n+m) wt(a[i]),*p2++=' ';
	fwrite(buf,1,p2-p1,stdout);
}

评测结果