代码

#include <bits/stdc++.h>
using namespace std;
const int Mod=998244353;
const int N=400005;
int R[N],a[N],b[N],n,m;
int read(int &a) {
	char ch=getchar(); a=0;
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9') a=a*10+ch-'0',ch=getchar();
	return a;
}
int Pow(int x,int y) {
	int res=1;
	while (y) {
		if (y&1) res=1ll*res*x%Mod;
		x=1ll*x*x%Mod; y>>=1;
	}
	return res%Mod;
}
void NTT(int *A,int f) {
	for (int i=0; i<n; i++) if (i<R[i]) swap(A[i],A[R[i]]);
	for (int i=1; i<n; i<<=1) {
		int gn=Pow(3,(Mod-1)/(i<<1)),x,y;
		for (int j=0; j<n; j+=(i<<1)) {
			int g=1;
			for (int k=0; k<i; k++,g=1ll*g*gn%Mod) {
				x=A[j+k],y=1ll*g*A[i+j+k]%Mod;
				A[j+k]=(x+y)%Mod,A[i+j+k]=(x-y+Mod)%Mod;
			}
		}
	}
	if (f==1) return;
	reverse(A+1,A+n);
	int y=Pow(n,Mod-2);
	for (int i=0; i<n; i++) A[i]=1ll*A[i]*y%Mod;
}
int main() {
	read(n),read(m);
	for (int i=0; i<=n; i++) read(a[i]);
	for (int i=0; i<=m; i++) read(b[i]);
	int L=0;
	m+=n; for (n=1; n<=m; n<<=1) L++;
	for (int i=0; i<n; i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	NTT(a,1); NTT(b,1);
	for (int i=0; i<n; i++) a[i]=1ll*a[i]*b[i]%Mod;
	NTT(a,-1);
	for (int i=0; i<=m; i++) printf("%d ",a[i]); printf("\n"); 
	return 0;
}

评测结果