代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int P=262144;
const int M=998244353;
int m,n;
int a[P],w[P],b[P],rev[P];
inline int D(int x){
    return x>=M?x-M:x;
}
inline int U(int x){
    return x<0?x+M:x; 
}
inline int fp(int x,int y){
    int ret=1; for (; y; y>>=1,x=(ll)x*x%M) if (y&1) ret=(ll)ret*x%M; return ret;
}
void NTT(int *a,int n){
    for (int i=0; i<n; ++i) if (rev[i]>i) swap(a[i],a[rev[i]]);
    for (int i=1; i<n; i<<=1){
        w[0]=1; w[1]=fp(3,(M-1)/(i<<1));
        for (int j=2; j<i; ++j) w[j]=(ll)w[j-1]*w[1]%M;
        for (int j=0; j<n; j+=(i<<1))
        for (int k=j; k<j+i; ++k){
            int x=a[k],y=(ll)w[k-j]*a[k+i]%M;
            a[k]=D(x+y);
            a[k+i]=U(x-y);
        }
    }
}
#define fuc(a,b,c) for (int i=0; i<u; ++i) c[i]=(ll)a[i]*b[i]%M
int main(){
    scanf("%d%d",&m,&n); ++m; ++n;
    for (int i=0; i<m; ++i) scanf("%d",&a[i]);
	for (int i=0; i<n; ++i) scanf("%d",&b[i]); 
    int u,c=0; for (u=1; u<n+m-1; u<<=1,++c);
    for (int i=0; i<u; ++i) rev[i]=rev[i>>1]>>1|((i&1)<<(c-1));
    NTT(a,u); NTT(b,u);
	fuc(a,b,a);
	reverse(a+1,a+u);
	NTT(a,u);
	int ni=fp(u,M-2); 
	for (int i=0; i<u; ++i) a[i]=(ll)a[i]*ni%M;
	for (int i=0; i<=n+m-2; ++i) printf("%d ",a[i]); 
}

评测结果