代码

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100010,mod=998244353,g=3;
int n,m;
int a[maxn<<2],b[maxn<<2];
int limit=1,l;
int R[maxn<<2];
int quickpow(int a,int b){
	ll ans=1,fac=a;
	while(b){
		if(b&1) ans=ans*fac%mod;
		fac=fac*fac%mod;
		b>>=1;
	}
	return int(ans%mod);
}
void NTT(int *c,int type){
	for(int i=0;i<limit;i++)
		if(i<R[i]) swap(c[i],c[R[i]]);
	for(int mid=1;mid<limit;mid<<=1){
		int wn=quickpow(g,mod-1+type*(mod-1)/(mid<<1));
		for(int r=mid<<1,j=0;j<limit;j+=r){
			int w=1;
			for(int k=0;k<mid;k++,w=1ll*w*wn%mod){
				int x=c[j+k],y=1ll*c[j+k+mid]*w%mod;
				c[j+k]=(x+y)%mod;
				c[j+k+mid]=(x-y+mod)%mod;
			}
		}
	}
	if(type==-1){
		int inv=quickpow(limit,mod-2);
		for(int i=0;i<limit;i++) c[i]=1ll*c[i]*inv%mod;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++) scanf("%d",a+i);
	for(int i=0;i<=m;i++) scanf("%d",b+i);
	while(limit<n+m){
		limit<<=1;l++;
	}
	for(int i=0;i<limit;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(l-1));
	NTT(a,1);NTT(b,1);
	for(int i=0;i<=limit;i++) a[i]=1ll*a[i]*b[i]%mod;
	NTT(a,-1);
	for(int i=0;i<=n+m;i++) printf("%d ",a[i]);
}

评测结果