代码

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
static constexpr auto MOD=998244353,omega=3;
namespace poly{
    constexpr auto qpow(lint a,lint b){
        auto res=1ll;
        while(b){
            if(b&1) (res*=a)%=MOD;
            (a*=a)%=MOD;b>>=1;
        }
        return res;
    }
    constexpr auto inv(lint x){
        return qpow(x,MOD-2);
    }
    template<typename _Ty>
    auto change(vector<_Ty>&a,const int n){
        vector<int> rev(n);
        cir(i,0,n){
            rev[i]=rev[i>>1]>>1;
            if(i&1) rev[i]|=(n>>1);
        }
        cir(i,0,n) if(i<rev[i]) swap(a[i],a[rev[i]]);
    }
    template<const int type>
    auto ntt(vector<lint>&a,const int n){
        change(a,n);
        for(auto h=2;h<n+1;h<<=1){
            const auto midi=h>>1;
            const auto wx=qpow(omega,(MOD-1)/h);
            for(int i=0;i<n;i+=h){
                auto u=1ll;
                for(auto k=i;k<i+midi;++k){
                    const auto wk=u*a[k+midi];
                    a[k+midi]=(a[k]-wk);
                    (a[k]+=wk);
                    (u*=wx)%=MOD;
                }
            }
        }
        if(type==-1){
            const auto invx=inv(n);
            reverse(a.begin()+1,a.end());
            for(auto&i:a) i/=invx;
        }
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m;cin>>n>>m;++n;++m;
    const auto lgn=(int)(log2(n+m)+1);
    const auto len=1<<lgn;
    vector<lint> a(len),b(len);
    cir(i,0,n) cin>>a[i];
    cir(i,0,m) cin>>b[i];
    poly::ntt<1>(a,len);
    poly::ntt<1>(b,len);
    cir(i,0,len) (a[i]*=b[i])%=MOD;
    poly::ntt<-1>(a,len);
    cir(i,0,n+m-1) cout<<a[i]<<' ';
    cout<<'\n';
    return 0;
}

评测结果