代码

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=4e6+5,p=998244353;
int n,m,L,inv,a[N],b[N],R[N];
inline int pow(int x,int y){
    int ans=1;while(y){if(y&1)ans=1ll*ans*x%p;x=1ll*x*x%p;y>>=1;}
    return ans;
}
void FFT(int *A,int o){
    for(int i=0;i<n;++i)if(R[i]>i)swap(A[R[i]],A[i]);
    for(int i=1;i<n;i<<=1){
        int wn=pow(3,(p-1)/(i<<1)),a,b,w;
        for(int j=0;j<n;j+=(i<<1)){
            w=1;for(int k=0;k<i;++k,w=1ll*w*wn%p){
                a=A[j+k],b=1ll*A[i+j+k]*w%p;
                A[j+k]=(a+b)%p;A[i+j+k]=(a-b+p)%p;
            }
        }
    }
    if(o==-1){
        reverse(A+1,A+n);
        for(int i=0;i<n;++i)A[i]=1ll*A[i]*inv%p;
    }
}
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]);
    m+=n;for(n=1;n<=m;n<<=1)++L;inv=pow(n,p-2);
    for(int i=1;i<n;++i)R[i]=((i&1)<<(L-1))|(R[i>>1]>>1);
    FFT(a,1);FFT(b,1);for(int i=0;i<n;++i)a[i]=1ll*a[i]*b[i]%p;
    FFT(a,-1);
    for(int i=0;i<=m;++i)printf("%d ",a[i]);
    return 0;
}

评测结果