代码

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace ConstMod
{
template<const ullt p>
class mod_ullt
{
private:
    ullt v;
    inline ullt chg(ullt w){return(w<p)?w:w-p;}
    inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
public:
    mod_ullt():v(0){}
    mod_ullt(ullt v):v(v%p){}
    inline bol empty(){return!v;}
    inline ullt val(){return v;}
    inline ullt&operator()(){return v;}
    inline friend bol operator==(mod_ullt a,mod_ullt b){return a()==b();}
    inline friend bol operator!=(mod_ullt a,mod_ullt b){return a()!=b();}
    inline mod_ullt operator+(){return*this;}
    inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a()+b());}
    inline mod_ullt&operator+=(mod_ullt b){return*this=*this+b;}
    inline mod_ullt operator-(){return _chg(p-v);}
    inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a+(-b);}
    inline mod_ullt&operator-=(mod_ullt b){return*this=*this-b;}
    inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a()*b();}
    inline mod_ullt&operator*=(mod_ullt b){return*this=*this*b;}
    inline friend mod_ullt operator/(mod_ullt a,mod_ullt b){return a*b.inv();}
    inline mod_ullt&operator/=(mod_ullt b){return*this=*this/b;}
    friend mod_ullt operator^(mod_ullt a,ullt b)
    {
        mod_ullt v(1);
        while(b)
        {
            if(b&1)v*=a;
            a*=a,b>>=1;
        }
        return v;
    }
    inline mod_ullt&operator^=(ullt b){return*this=*this^b;}
    inline mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
    inline mod_ullt&operator++(){return v=chg(v+1),*this;}
    inline mod_ullt operator--(int){mod_ullt ans=*this;return v=chg(v+p-1),ans;}
    inline mod_ullt&operator--(){return v=chg(v+p-1),*this;}
    inline mod_ullt inv(){return(*this)^(p-2);}
    mod_ullt sqrt()
    {
        if(((*this)^((p-1)>>1))!=1)return 0;
        mod_ullt b(1);do b++;while((b^((p-1)>>1))==1);
        ullt t=p-1;uint s=0;while(!(t&1))s++,t>>=1;
        mod_ullt x=(*this)^((t+1)>>1),e=(*this)^t,w=inv();
        for(uint k=1;k<s;k++,e=w*x*x)if((e^(1llu<<(s-k-1)))!=1)x*=b^((1llu<<(k-1))*t);
        ullt ans=x();_min(ans,p-ans);return ans;
    }
    voi read()
    {
        v=0;chr c;do c=getchar();while(c>'9'||c<'0');
        do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');
    }
    voi print(chr endc='\0')
    {
        static chr C[20];uint tp=0;
        ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
        while(tp--)putchar(C[tp]);
        if(endc)putchar(endc);
    }
    inline voi println(){print('\n');}
};
}
namespace NTT_POLY
{
template<const ullt p,const ullt g>
class poly_NTT
{
public:
    typedef ConstMod::mod_ullt<p>modint;
    typedef std::vector<modint>modvec;
private:
    modvec V;
public:
    class NTT
    {
    private:
        uint n;uint*T;modint*G;
    public:
        NTT():n(0),T(NULL),G(NULL){}
        NTT(uint len)
        {
            n=1;while(n<len)n<<=1;
            T=new uint[n],G=new modint[n],T[0]=0,G[0]=1;
            for(uint i=1;i<n;i++)T[i]=((i&1)?n|T[i>>1]:T[i>>1])>>1;
            modint w=power(g,(p-1)/n,p),*End=G+n;for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        ~NTT(){if(T)delete[]T,delete[]G,T=NULL,G=NULL;}
        inline uint size(){return n;}
        voi bzr(uint len)
        {
            if(T)delete[]T,delete[]G,T=NULL,G=NULL;
            n=1;while(n<len)n<<=1;
            T=new uint[n],G=new modint[n],T[0]=0,G[0]=1;
            for(uint i=1;i<n;i++)T[i]=((i&1)?n|T[i>>1]:T[i>>1])>>1;
            modint w=power(g,(p-1)/n,p),*End=G+n;for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        voi ntt(modvec&x,bol op)
        {
            if(x.size()<n)x.resize(n);
            for(uint i=0;i<n;i++)if(T[i]<i)std::swap(x[i],x[T[i]]);
            for(uint i=1,d=n>>1;d;i<<=1,d>>=1)for(uint j=0;j<n;j+=i<<1)
            {
                modint*w=G,t;for(uint k=0;k<i;k++,w+=d)x[i|j|k]=x[j|k]-(t=x[i|j|k]*(*w)),x[j|k]+=t;
            }
            if(op)
            {
                for(uint i=1;i*2<n;i++)std::swap(x[i],x[n-i]);
                modint t=modint(n).inv();for(uint i=0;i<n;i++)x[i]*=t;
            }
        }
        inline modint omega(uint t){return G[t%n];}
        NTT&operator=(NTT b)
        {
            if(T)delete[]T,delete[]G,T=NULL,G=NULL;
            if(!b.T)return*this;
            T=new uint[n],G=new modint[n=b.n];
            for(uint i=0;i<n;i++)T[i]=b.T[i],G[i]=b.G[i];
            return*this;
        }
    };
    class DIFDIT
    {
    private:
        uint n;modint*G;
    public:
        DIFDIT():n(0),G(NULL){}
        DIFDIT(uint len)
        {
            n=1;while(n<len)n<<=1;
            G=new modint[n],G[0]=1;
            modint w=power(g,(p-1)/n,p),*End=G+n;
            for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        ~DIFDIT(){if(G)delete[]G,G=NULL;}
        inline uint size(){return n;}
        voi bzr(uint len)
        {
            if(G)delete[]G;
            n=1;while(n<len)n<<=1;
            G=new modint[n],G[0]=1;
            modint w=power(g,(p-1)/n,p),*End=G+n;
            for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
        }
        voi dif(modvec&x)
        {
            if(x.size()<n)x.resize(n);
            for(uint i=n>>1,d=1;i;i>>=1,d<<=1)for(uint j=0;j<n;j+=i<<1) 
            {
                modint*w=G,u,t;for(uint k=0;k<i;k++,w+=d)x[j|k]=(u=x[j|k])+(t=x[i|j|k]),x[i|j|k]=(u-t)*(*w);
            }
        }
        voi dit(modvec&x)
        {
            if(x.size()<n)x.resize(n);
            for(uint i=1,d=n>>1;d;i<<=1,d>>=1)for(uint j=0;j<n;j+=i<<1)
            {
                modint*w=G,t;for(uint k=0;k<i;k++,w+=d)x[i|j|k]=x[j|k]-(t=x[i|j|k]*(*w)),x[j|k]+=t;
            }
            for(uint i=1;i*2<n;i++)std::swap(x[i],x[n-i]);
            modint t=modint(n).inv();for(uint i=0;i<n;i++)x[i]*=t;
        } 
        DIFDIT&operator=(DIFDIT b)
        {
            if(G!=NULL)delete[]G,G=NULL;
            if(b.G==NULL)return*this;
            G=new modint[n=b.n];
            for(uint i=0;i<n;i++)G[i]=b.G[i];
            return*this;
        }
    };
    poly_NTT(){}
    poly_NTT(uint n){V.resize(n);}
    poly_NTT(modvec V):V(V){}
    inline voi bzr(){V.clear();}
    inline voi push(modint v){V.push_back(v);}
    inline voi pop(){V.pop_back();}
    inline voi pop0s(){while(V.size()&&V.back().empty())V.pop_back();}
    inline voi chg_siz(uint n){V.resize(n);}
    inline voi chg_deg(uint n){V.resize(n+1);}
    inline bol empty(){return pop0s(),V.empty();}
    inline uint size(){return V.size();}
    inline uint deg(){return V.size()-1;}
    inline modint val(uint n){return n<size()?V[n]:modint();}
    inline modint&operator[](uint n){return V[n];}
    inline modvec GET(){return V;}
    inline decltype(V.begin()) begin(){return V.begin();}
    inline decltype(V.begin()) end(){return V.end();}
    poly_NTT reverse()
    {
        uint n=size();poly_NTT ans(n);
        for(uint i=0;i<n;i++)ans[i]=V[n-i-1];
        return ans;
    }
    friend poly_NTT operator+(poly_NTT a,poly_NTT b)
    {
        if(a.size()<b.size())a.chg_siz(b.size());
        for(uint i=0;i<b.size();i++)a[i]+=b[i];
        return a;
    }
    poly_NTT&operator+=(poly_NTT b)
    {
        if(size()<b.size())chg_siz(b.size());
        for(uint i=0;i<b.size();i++)V[i]+=b[i];
        return*this;
    }
    friend poly_NTT operator+(poly_NTT a,modint v)
    {
        if(!a.size())return{v};
        a[0]+=v;return a;
    }
    inline poly_NTT&operator+=(modint v)
    {
        if(!size())*this={v};else V[0]+=v;
        return*this;
    }
    friend poly_NTT operator+(modint v,poly_NTT a)
    {
        if(!a.size())return{v};
        a[0]+=v;return a;
    }
    friend poly_NTT operator-(poly_NTT a)
    {
        for(auto&s:a)s=-s;
        return a;
    }
    friend poly_NTT operator-(poly_NTT a,poly_NTT b)
    {
        if(a.size()<b.size())a.chg_siz(b.size());
        for(uint i=0;i<b.size();i++)a[i]-=b[i];
        return a;
    }
    poly_NTT&operator-=(poly_NTT b)
    {
        if(size()<b.size())chg_siz(b.size());
        for(uint i=0;i<b.size();i++)V[i]-=b[i];
        return*this;
    }
    friend poly_NTT operator-(poly_NTT a,modint v)
    {
        if(!a.size())return-v;
        a[0]-=v;return a;
    }
    inline poly_NTT&operator-=(modint v)
    {
        if(!size())*this={-v};else V[0]-=v;
        return*this;
    }
    friend poly_NTT operator-(modint v,poly_NTT a){return-a+v;}
    friend poly_NTT operator*(poly_NTT a,poly_NTT b)
    {
        a.pop0s(),b.pop0s();
        if(!a.size()||!b.size())return{};
        if(a.size()<=8||b.size()<=8)
        {
            modvec ans(a.size()+b.size()-1);
            for(uint i=0;i<a.size();i++)for(uint j=0;j<b.size();j++)ans[i+j]+=a[i]*b[j];
            return ans;
        }
        modvec&A=a.V,&B=b.V;DIFDIT s(A.size()+B.size());
        s.dif(A),s.dif(B);for(uint i=0;i<s.size();i++)A[i]*=B[i];
        s.dit(A),a.pop0s();return a;
    }
    poly_NTT&operator*=(poly_NTT b){return*this=*this*b;}
    friend poly_NTT operator*(poly_NTT a,modint v)
    {
        for(auto&s:a)s*=v;
        return a;
    }
    poly_NTT&operator*=(modint v)
    {
        for(auto&t:V)t*=v;
        return*this;
    }
    friend poly_NTT operator*(modint v,poly_NTT a)
    {
        for(auto&s:a)s*=v;
        return a;
    }
    friend poly_NTT operator<<(poly_NTT a,uint k){modvec t(k);a.V.insert(a.begin(),t.begin(),t.end());return a;}
    inline poly_NTT&operator<<=(uint k){modvec t(k);return V.insert(begin(),t.begin(),t.end()),*this;}
    friend poly_NTT operator>>(poly_NTT a,uint k)
    {
        if(a.size()<=k)return{};
        return a.V.erase(a.begin(),a.begin()+k),a;
    }
    inline poly_NTT&operator>>=(uint k)
    {
        if(size()<=k)return*this={};
        return V.erase(begin(),begin()+k),*this;
    }
};
}
const ullt Mod=998244353,g=3;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
typedef NTT_POLY::poly_NTT<Mod,g>poly;
int main()
{
    // for(uint i=1;i<=100;i++)
    // {
    //     modint g=modint(i).sqrt();
    //     if(g())printf("%u %llu %llu\n",i,g(),(g*g)());
    // }
    uint n,m;scanf("%u%u",&n,&m);
    poly A(n+1),B(m+1);
    for(auto&v:A)v.read();
    for(auto&v:B)v.read();
    A*=B;
    for(uint i=0;i<=n+m;i++)A.val(i).print(" \n"[i==n+m]);
    return 0;
}

评测结果