代码

#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;
        }
    };
};
}
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);
    modvec A(n+1),B(m+1);
    for(auto&v:A)v.read();
    for(auto&v:B)v.read();
    poly::DIFDIT s(n+m+1);
    s.dif(A),s.dif(B);
    for(uint i=0;i<s.size();i++)A[i]*=B[i];
    s.dit(A);
    for(uint i=0;i<=n+m;i++)A[i].print(" \n"[i==n+m]);
    return 0;
}

评测结果