代码

#include <bits/stdc++.h>
//#define FAST
using namespace std;
namespace container{
    template<class T,size_t BLOCK_SIZE>
    class myarray{
        struct period{
            T a[BLOCK_SIZE];
            period* ne=NULL;
            period(){
            }
            period(const T &v){
                fill(a,a+BLOCK_SIZE,v);
            }
        };
        period *Be;
        size_t Sz;
        class iterator{
            period *ip;
            size_t pos;
            myarray *po;
        public:
            typedef random_access_iterator_tag iterator_category;
            typedef T value_type;
            typedef T* pointer;
            typedef T& reference;
            typedef ptrdiff_t difference_type;
            iterator():ip(nullptr),pos(0),po(nullptr){
            }
            iterator(const iterator &it){
                (*this)=it;
            }
            iterator(period * const &ip,const size_t &pos,myarray * const &po):ip(ip),pos(pos),po(po){
            }
            bool operator !=(const iterator &it) const{
                return ip!=it.ip||pos!=it.pos;
            }
            bool operator ==(const iterator &it) const{
                return ip==it.ip&&pos==it.pos;
            }
            iterator operator ++(){
                if (++pos==BLOCK_SIZE&&ip->ne!=NULL){
                    ip=ip->ne;
                    pos=0;
                }
                return *this;
            }
            const iterator operator ++(int){
                iterator tmp(*this);
                if (++pos==BLOCK_SIZE&&ip->ne!=NULL){
                    ip=ip->ne;
                    pos=0;
                }
                return tmp;
            }
            iterator operator --(){
                if (pos){
                    --pos;
                    return (*this);
                }
                period *tBe=po->Be;
                while (tBe->ne!=ip) tBe=tBe->ne;
                ip=tBe;
                pos=BLOCK_SIZE-1;
                return (*this);
            }
            const iterator operator --(int){
                iterator tmp(*this);
                if (pos){
                    --pos;
                    return tmp;
                }
                period *tBe=po->Be;
                while (tBe->ne!=ip) tBe=tBe->ne;
                ip=tBe;
                pos=BLOCK_SIZE-1;
                return tmp;
            }
            iterator operator +(const size_t &len) const{
                //ip!=NULL BUG
                if (BLOCK_SIZE>pos+len) return iterator(ip,pos+len,po);
                size_t tmp=len-(BLOCK_SIZE-1-pos);
                if (ip->ne==NULL) return iterator(ip,BLOCK_SIZE,po);
                period *tip=ip->ne;
                while (tmp>BLOCK_SIZE){
                    if (tip->ne==NULL) return iterator(tip,BLOCK_SIZE,po);
                    tip=tip->ne;
                    tmp-=BLOCK_SIZE;
                }
                return iterator(tip,tmp-1,po);
            }
            iterator operator +=(const size_t &len){
                return ((*this)=(*this)+len);
            }
            size_t operator -(const iterator &it) const{
                //only
                if (ip==it.ip) return pos-it.pos;
                period *tmp=it.ip->ne;
                size_t ret=BLOCK_SIZE-it.pos;
                while (tmp!=ip){
                    ret+=BLOCK_SIZE;
                    tmp=tmp->ne;
                }
                return ret+pos;
            }
            iterator operator -(const size_t &len) const{
                return (po->begin()+((*this)-(po->begin())-len));
            }
            iterator operator -=(const size_t &len){
                return ((*this)=(*this)-len);
            }
            bool operator <(const iterator &it) const{
                //same father
                return ((*this)-po->begin())<(it-(po->begin()));
            }
            bool operator <=(const iterator &it) const{
                //same father
                return ((*this)-po->begin())<=(it-(po->begin()));
            }
            T & operator *() const{
                return ip->a[pos];
            }
        };
    public:
        typedef T value_type;
        typedef T& reference;
        typedef const T& const_reference;
        typedef size_t size_type;
        myarray(){
            Be=NULL;
            Sz=0;
        }
        myarray(const size_t &sz){
            construct(sz);
        }
        myarray(const size_t &sz,const T &v){
            construct(sz,v);
        }
        ~myarray(){
            myfree(Be);
        }
        myarray(const myarray &rhs){
            if (this==&rhs) return;
            construct(rhs.size());
            auto j=begin();
            for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);
        }
        myarray(const initializer_list<T> &args){
            construct(args.size());
            auto j=begin();
            for (auto it=args.begin(); it!=args.end(); ++it) *(j++)=(*it);
        }
        myarray& operator =(const myarray &rhs){
            if (this==&rhs) return (*this);
            myfree(Be);
            construct(rhs.size());
            auto j=begin();
            for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);
            return *this;
        }
        void myfree(period * const &Be){
            period *tBe=Be,*tmp;
            while (tBe!=NULL){
                tmp=tBe->ne;
                delete tBe;
                tBe=tmp;
            }
        }
        void construct(const size_t &sz){
            Be=new period();//slow but safe
            Sz=sz;
            size_t tSz=sz;
            period *tBe=Be;
            while (tSz>BLOCK_SIZE){
                tBe=(tBe->ne=new period);
                tSz-=BLOCK_SIZE;
            }
        }
        void construct(const size_t &sz,const T &v){
            Be=new period(v);
            Sz=sz;
            size_t tSz=sz;
            period *tBe=Be;
            while (tSz>BLOCK_SIZE){
                tBe=(tBe->ne=new period);
                tSz-=BLOCK_SIZE;
            }
        }
        iterator begin() const{
            return iterator(Be,0,(myarray*)this);
        }
        iterator end() const{
            //Slow And Dangerous
            if (Be==NULL) return iterator(NULL,0,(myarray*)this);
            period *tBe=Be;
            while (tBe->ne!=NULL) tBe=tBe->ne;
            return iterator(tBe,((int)Sz-1)%(int)BLOCK_SIZE+1,(myarray*)this);
        }
        void push_back(const T &v){
            if (Be==NULL){
                Be=new period;
                Be->a[Sz++]=v;
                return;
            }
            period *tBe=Be;
            while (tBe->ne!=NULL) tBe=tBe->ne;
            size_t tSz=(Sz++)%BLOCK_SIZE;
            if (tSz==0) tBe=(tBe->ne=new period);
            tBe->a[tSz]=v;
        }
        void pop_back(){
            if ((--Sz)%BLOCK_SIZE) return;
            if (Sz==0){
                delete Be;
                Be=NULL;
                return;
            }
            period *tBe=Be;
            while (tBe->ne->ne!=NULL) tBe=tBe->ne;
            delete tBe->ne;
            tBe->ne=NULL;
        }
		T& operator [](const size_t &pos) const{
            size_t tpos=pos;
            for (period* i=Be; i!=NULL; i=i->ne)
                if (tpos<BLOCK_SIZE) return i->a[tpos];
                else tpos-=BLOCK_SIZE;
            throw;
		}
        T& front() const{
            //unusual
            return Be->a[0];
        }
        T& back() const{
            return *(--end());
        }
        size_t size() const{
            return Sz;
        }
        bool empty() const{
            return Sz==0;
        }
		void swap(myarray &arr){
			std::swap(Be,arr.Be);
			std::swap(Sz,arr.Sz);
		}
        template<class U>
        struct iterator_traits{
            typedef typename U::value_type value_type;
            typedef typename U::iterator_category iterator_category;
            typedef typename U::difference_type difference_type;
            typedef typename U::pointer pointer;
            typedef typename U::reference reference;
        };
    };
}
template<class T=int,size_t BLOCK_SIZE=131072>
using arr=container::myarray<T,BLOCK_SIZE>;
typedef long long ll;
const int P=262144;
const int M=998244353;
int m,n;
arr<> a(P),w(P),b(P),rev(P);
inline int D(int x){
    return x>=M?x-M:x;
}
inline int U(int x){
    return x<0?x+M:x; 
}
inline int fp(int x,int y){
    int ret=1; for (; y; y>>=1,x=(ll)x*x%M) if (y&1) ret=(ll)ret*x%M; return ret;
}
void NTT(arr<> &a,int n){
    for (int i=0; i<n; ++i) if (rev[i]>i) swap(a[i],a[rev[i]]);
    for (int i=1; i<n; i<<=1){
        w[0]=1; w[1]=fp(3,(M-1)/(i<<1));
        for (int j=2; j<i; ++j) w[j]=(ll)w[j-1]*w[1]%M;
        for (int j=0; j<n; j+=(i<<1))
        for (int k=j; k<j+i; ++k){
            int x=a[k],y=(ll)w[k-j]*a[k+i]%M;
            a[k]=D(x+y);
            a[k+i]=U(x-y);
        }
    }
}
#define fuc(a,b,c) for (int i=0; i<u; ++i) c[i]=(ll)a[i]*b[i]%M
int main(){
    scanf("%d%d",&m,&n); ++m; ++n;
    for (int i=0; i<m; ++i) scanf("%d",&a[i]);
	for (int i=0; i<n; ++i) scanf("%d",&b[i]); 
    int u,c=0; for (u=1; u<n+m-1; u<<=1,++c);
    for (int i=0; i<u; ++i) rev[i]=rev[i>>1]>>1|((i&1)<<(c-1));
    NTT(a,u); NTT(b,u);
	fuc(a,b,a);
	reverse(a.begin()+1,a.begin()+u);
	NTT(a,u);
	int ni=fp(u,M-2); 
	for (int i=0; i<u; ++i) a[i]=(ll)a[i]*ni%M;
	for (int i=0; i<=n+m-2; ++i) printf("%d ",a[i]); 
}

评测结果