over 1 year ago

By ShinFeb

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)
typedef long long ll;
typedef double db;
typedef pair<int,int> ii;
const long double pi=acos(-1);
template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}
template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

const int mod=998244353;
const int maxn=262144;

int a[maxn],b[maxn];
int qpow(int a,int b,int mod=::mod)
{
    int c=1;
    for(;b;b>>=1,a=(ll)a*a%mod)
        if(b&1)c=(ll)a*c%mod;
    return c;
}
namespace FFT{
    const int maxb=25;
    const int g=3,ng=332748118;
    //mod=998244353
 
    int n,L,rev[maxn];
    int G[maxb],nG[maxb],fra;
    
    void dft(int *a,int f)
    {
        rep(i,0,n)if(rev[i]<i)swap(a[i],a[rev[i]]);
        for(int m=1,now=1;m<n;m<<=1,now++)
        {
            int w=f==1?G[now]:nG[now];
            for(int i=0;i<n;i+=m<<1)
            {
                int cur=1;
                for(int j=0;j<m;j++)
                {
                    int x=a[i+j],y=1ll*a[i+j+m]*cur%mod;
                    a[i+j]=(x+y)%mod;
                    a[i+j+m]=(x-y+mod)%mod;
                    cur=1ll*cur*w%mod;
                }
            }
        }
        if(f==-1)rep(i,0,n)a[i]=1ll*a[i]*fra%mod;
    }
    void InitN(int nn)
    {
        for(n=1,L=0;n<nn;n<<=1)L++;
        rep(i,1,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<L-1);
        fra=qpow(n,mod-2);
    }
    void InitG()
    {
        int tmp=mod-1,t=0;
        do{
            tmp>>=1;
            G[++t]=qpow(g,tmp);
            nG[t]=qpow(ng,tmp);
        }while(~tmp&1);
    }
    void fft(int *a,int *b,int *c,int na,int nb,int &nc)
    {
        int nn=na+nb-1;
        InitN(nn);
        rep(i,na,n)a[i]=0;
        rep(i,nb,n)b[i]=0;
        dft(a,1);dft(b,1);
        rep(i,0,n)c[i]=(ll)a[i]*b[i]%mod;
        dft(c,-1);
        nc=nn;
    }
}

int main()
{
// freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);
 int na,nb;
    sc(na);sc(nb);++na;++nb;
    rep(i,0,na)sc(a[i]);
    rep(i,0,nb)sc(b[i]);
    
    FFT::InitG();
    FFT::fft(a,b,a,na,nb,na);
    rep(i,0,na)pt(a[i]),putchar(" \n"[i==na-1]);
    return 0;
}
← Hello World 后缀自动机试水 →