代码

// 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],L,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 void print(poly A,int n=-1){if(!~n)n=A.size();for(int i=0;i<n;i++)write(A[i]),putchar(' ');putchar('\n');}
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 int upp(int x){
    while((x&-x)!=x)x+=x&-x;
    return x;
}
inline void getRev(int x){
    lim=upp(x);
    for(int i=1;i<lim;i++)R[i]=(R[i>>1]>>1)|((i&1)?(lim>>1):0);
}
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;i<lim;i<<=1)
        for(register int j=0;j<lim;j+=(i<<1))
            for(register int k=0,t=1;k<i;++k){
                const int Ny=mul(A[i+j+k],w[i+k]);
                A[i+j+k]=sub(A[j+k],Ny);
                A[j+k]=add(A[j+k],Ny);
            }
}
int main(){
    n=read()+1;m=read()+1;
    for(int i=1,wn;i<(m+n);i<<=1){
        wn=qsm(3,(P-1)/(i<<1)),w[i]=1;
        for(int j=1;j<i;j++)w[i+j]=mul(w[i+j-1],wn);
    }
    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;
    getRev(n);
    NTT(t1);
    NTT(t2);
    for(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(int i=0;i<n;++i)write(mul(t1[i],lim)),putchar(' ');
}

评测结果