代码

#include<bits/stdc++.h>
using namespace std;
int const N=(1<<21)+5;
namespace input
{
    const int InputBufferSize=(1<<23)+5;
    char buffer[InputBufferSize],*s,*eof;
    inline void init()
    {
        assert(stdin!=NULL);
        s=buffer;
        eof=s+fread(buffer,1,InputBufferSize,stdin);
    }
    inline bool read(int &x)
    {
        x=0;
        int flag=1;
        while(!isdigit(*s)&&*s!='-')s++;
        if(eof<=s)return false;
        if(*s=='-')flag=-1,s++;
        while(isdigit(*s))x=x*10+*s++-'0';
        x*=flag;
        return true;
    }
    inline bool read(char* str)
    {
        *str=0;
        while(isspace(*s))s++;
        if(eof<s)return false;
        while(!isspace(*s))*str=0,*str=*s,str++,s++;
        *str=0;
        return true;
    }
}
namespace output
{
    const int OutputBufferSize=(1<<23)+5;
    char buffer[OutputBufferSize];
    char *s=buffer;
    inline void flush()
    {
        assert(stdout!=NULL);
        fwrite(buffer,1,s-buffer,stdout);
        s=buffer;
        fflush(stdout);
    }
    inline void print(const char ch)
    {
        if(s-buffer>OutputBufferSize-2)flush();
        *s++=ch;
    }
    inline void print(char* str)
    {
        while(*str!=0)print(char(*str++));
    }
    inline void print(int x)
    {
        char buf[25]= {0},*p=buf;
        if(x<0)print('-'),x=-x;
        if(x==0)print('0');
        while(x)*(++p)=x%10,x/=10;
        while(p!=buf)print(char(*(p--)+'0'));
    }
}
using namespace input;
using namespace output;
namespace polynomials
{
    int const p=998244353,g=3;
    int w[N],iv[N],r[N],last;
    typedef vector<int> vec;
    inline int mod(int x){return x>=p?x-p:x;}
    int pw(int x,int y)
    {
        int res=1;
        while(y)
        {
            if(y&1)res=1ll*res*x%p;
            x=1ll*x*x%p;
            y>>=1;
        }
        return res;
    }
    void init(int n)
    {
        int lim=1;
        while((lim<<1)<n)lim<<=1;
        iv[1]=1;
        for(int i=2;i<=lim;i++)iv[i]=p-1ll*p/i*iv[p%i]%p;
        for(int i=1;i<=lim;i<<=1)
        {
            int wn=pw(g,(p-1)/(i<<1));
            for(int j=0,ww=1;j<i;j++,ww=1ll*ww*wn%p)w[i+j]=ww;
        }
    }
    void ntt(vec &f,int n,int op)
    {
        if(last!=n)
        {
            for(int i=1;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);
            last=n;
        }
        for(int i=1;i<n;i++)if(i<r[i])swap(f[i],f[r[i]]);
        for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=i<<1)
            for(int k=0;k<i;k++)
            {
                int x=f[j+k],y=1ll*f[i+j+k]*w[i+k]%p;
                f[j+k]=mod(x+y);f[i+j+k]=mod(x-y+p);
            }
        if(op==-1)
        {
            reverse(&f[1],&f[n]);
            for(int i=0;i<n;i++)f[i]=1ll*f[i]*iv[n]%p;
        }
    }
}
using namespace polynomials;
vec a,b;
int main()
{
    //freopen("poly.in","r",stdin);
    //freopen("poly.out","w",stdout);
    input::init();
    int n,m;
    read(n),read(m);
    n++,m++;
    int lim=1;
    while(lim<(n+m-1))lim<<=1;
    init(lim+5);
    a.resize(lim),b.resize(lim);
    for(int i=0;i<n;i++)read(a[i]);
    for(int i=0;i<m;i++)read(b[i]);
    ntt(a,lim,1),ntt(b,lim,1);
    for(int i=0;i<lim;i++)a[i]=1ll*a[i]*b[i]%p;
    ntt(a,lim,-1);
    for(int i=0;i<n+m-1;i++)print(a[i]),print(' ');
    flush();
    return 0;
}

评测结果