代码

#include <bits/stdc++.h>
#define maxn 500005
#define mod 998244353
#define LL long long
using namespace std;
int Wl,Wl2,w[maxn];
inline int Pow(int b, int k) { int r=1; for(;k;k>>=1,b=1ll*b*b%mod) if(k&1) r=1ll*r*b%mod; return r; }
inline void init(int n) {
	for(Wl=1;n>=Wl<<1;Wl<<=1); int pw=Pow(3,(mod-1)/(Wl2=Wl<<1)); w[Wl]=1;
	for(int i=Wl+1;i<=Wl2;i++) w[i]=w[i-1]*1ll*pw%mod; for(int i=Wl-1;i>=1;i--) w[i]=w[i<<1];
}
inline int upd(int x) { return x+=x>>31&mod; }
inline void NTT(int *A, int bit, int tp) {
	static int r[maxn]={}; static unsigned LL ar[maxn]={};
	int n=1<<bit; if(tp^1) reverse(A+1,A+n);
	for(int i=0;i<n;i++) r[i]=(r[i>>1]>>1|(i&1)<<bit-1),ar[i]=upd(A[r[i]]);
	for(int L=1;L<n;L<<=1) for(int s=0,L2=L<<1;s<n;s+=L2)
	for(int k=s,x=L,t;x<L2;x++,k++) t=ar[k+L]*w[x]%mod,ar[k+L]=ar[k]-t+mod,ar[k]+=t;
	for(int i=0;i<n;i++) A[i]=ar[i]%mod;
	if(tp^1) for(int i=0,iv=Pow(n,mod-2);i<n;i++) A[i]=1ll*A[i]*iv%mod;
}
inline int Init(int n) { int m; for(m=1;m<=n;m<<=1); init(m); return m; }
int n,m,A[maxn],B[maxn];
int main() {
	scanf("%d%d",&n,&m),n++,m++; Init(n+m);
	for(int i=0;i<n;i++) scanf("%d",&A[i]); for(int i=0;i<m;i++) scanf("%d",&B[i]);
	int N=n+m-1,M=1; while((1<<M)<=N) M++; NTT(A,M,1); NTT(B,M,1);
	for(int i=0;i<(1<<M);i++) A[i]=1ll*A[i]*B[i]%mod; NTT(A,M,-1);
	for(int i=0;i<N;i++) printf("%d ",A[i]);
}

评测结果