代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#pragma GCC optimize(2)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

typedef std::vector<int> poly;
typedef long long ll;
#define pb push_back
poly A,B;
int n,R[2000001],lim,ksm[30],w[2000001],t1[2000001],t2[2000001],m,a[1000001],fac[1000001];
poly val[1000001];
const int P=998244353;
inline int read(){
    static int x;x=0;
    static char ch;ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void write(const int &x){if(x>9)write(x/10);putchar((x%10)+'0');}
inline int mul(const int &a,const int &b){return (ll)a*b-(ll)a*b/P*P;}
inline int add(int a,const int &b){a+=b;return a>=P?a-P:a;}
inline int sub(int a,const int &b){a-=b;return a<0?a+P:a;}
inline int qsm(int a,long long b=P-2){
    int ans=1;
    while(b){if(b&1)ans=mul(ans,a);a=mul(a,a),b>>=1;}
    return ans;
}
inline int inv(const int &a){return (a<=1)?1:mul(P-P/a,inv(P%a));}
inline void NTT(int *A){
    for(register int i=0;i<lim;++i)if(i<R[i])swap(A[i],A[R[i]]);
    for(register int i=1,Ny,j,k,*A1,*A2;i<lim;i<<=1)
        for(j=0;j<lim;j+=(i<<1))
            for(k=0,A1=A+i+j,A2=A+j;k<i;++k,++A1,++A2){
                Ny=mul(*A1,w[i+k]);
                *A1=sub(*A2,Ny);
                *A2=add(*A2,Ny);
            }
}
int main(){
    n=read()+1;m=read()+1;
    for(register int i=0;i<n;++i)t1[i]=read();
    for(register int i=0;i<m;++i)t2[i]=read();
    n+=m-1;
    lim=1;
    while(lim<=n)lim<<=1;
    ksm[19]=qsm(3,(P-1)>>20);
    for(register int i=262144,lg=18;i;i>>=1,--lg)ksm[lg]=mul(ksm[lg+1],ksm[lg+1]);
    for(register int i=1,wn,lg=0;i<(m+n);i<<=1,++lg){
        wn=ksm[lg],w[i]=1;
        for(register int j=1;j<i;++j)w[i+j]=mul(w[i+j-1],wn);
    }
    for(register int i=1;i<lim;++i)R[i]=(R[i>>1]>>1)|((i&1)?(lim>>1):0);
    NTT(t1);
    NTT(t2);
    for(register int i=0;i<lim;++i)t1[i]=mul(t1[i],t2[i]);
    std::reverse(t1+1,t1+lim);
	NTT(t1);
    lim=inv(lim);
    for(register int i=0;i<n;++i)write(mul(t1[i],lim)),putchar(' ');
}

评测结果