代码

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
ifstream fcin("rng.in");
ofstream fcout("rng.out");
class fileio{
public:
    ~fileio(){
        fcin.close();fcout.close();
    }
} use_fileio;
using ulint=unsigned long long;
static constexpr auto omega=3;
static constexpr auto MOD=998244353;
class mathbase{
private:
    vector<ulint> fct,ifct;
public:
    constexpr auto qpow(ulint a,ulint b){
        auto res=1ull;
        while(b){
            if(b&1) (res*=a)%=MOD;
            (a*=a)%=MOD;b>>=1;
        }
        return res;
    }
    constexpr auto inv(ulint x){
        return qpow(x,MOD-2);
    }
    auto fact(const int x){
        while((int)(fct.size())<x+1){
            fct.push_back(fct.back()*fct.size()%MOD);
            ifct.push_back(inv(fct.back()));
        }
        return fct[x];
    }
    auto ifact(const int x){
        return fact(x),ifct[x];
    }
    auto initc(const int n){
        vector<vector<ulint>> C(n,vector<ulint>(n));
        C[0][0]=1;
        cir(i,1,n) cir(j,0,n){
            C[i][j]=C[i-1][j];
            if(j) (C[i][j]+=C[i-1][j-1])%=MOD;
        }
        return C;
    }
    auto C(int a,int b){
        return fact(a)*ifct[b]%MOD*ifct[a-b]%MOD;
    }
    mathbase():fct(1,1),ifct(1,1){}
} math;
class polybase{
private:
    auto change(vector<ulint>&a,int n){
        vector<int> rev(n);
        cir(i,0,n) rev[i]=(rev[i>>1]>>1)|((n>>1)*(i&1));
        cir(i,0,n) if(rev[i]>i) swap(a[i],a[rev[i]]);
    }
    template<const int type>
    auto ntt(vector<ulint>&a,const int n){
        change(a,n);
        for(auto h=2;h<n+1;h<<=1){
            const auto midh=h/2;
            const auto wx=math.qpow(omega,(MOD-1)/h);
            const auto pwx=1ull,
                       pwy=wx,
                       pwz=wx*wx%MOD,
                       pwa=wx*wx%MOD*wx%MOD;
            for(auto i=0;i<n;i+=h){
                auto u=1ll;
                auto k=i;
                for(;k+4<i+midh;k+=4){
                    const auto wka=a[k+midh]*u%MOD*pwx%MOD;
                    a[k+midh]=(a[k]+MOD-wka)%MOD;
                    (a[k]+=wka)%=MOD;
                    const auto wkb=a[k+1+midh]*u%MOD*pwy%MOD;
                    a[k+1+midh]=(a[k+1]+MOD-wkb)%MOD;
                    (a[k+1]+=wkb)%=MOD;
                    const auto wkc=a[k+2+midh]*u%MOD*pwz%MOD;
                    a[k+2+midh]=(a[k+2]+MOD-wkc)%MOD;
                    (a[k+2]+=wkc)%=MOD;
                    const auto wkd=a[k+3+midh]*u%MOD*pwa%MOD;
                    a[k+3+midh]=(a[k+3]+MOD-wkd)%MOD;
                    (a[k+3]+=wkd)%=MOD;
                    (u*=pwa*wx%MOD)%=MOD;
                }
                for(;k<i+midh;k++){
                    const auto wk=a[k+midh]*u%MOD;
                    a[k+midh]=(a[k]+MOD-wk)%MOD;
                    (a[k]+=wk)%=MOD;
                    (u*=wx)%=MOD;
                }
            }
        }
        if(type==-1){
            const auto iv=math.inv(n);
            reverse(a.begin()+1,a.end());
            for(auto&i:a) (i*=iv)%=MOD;
        }
    }
    auto fit(vector<ulint>&a){
        while((!a.empty())&&(!a.back())) a.pop_back();
    }
public:
    auto mul(vector<ulint> a,vector<ulint> b){
        const auto n=(1<<((int)(log2(a.size()+b.size()))+1));
        a.resize(n);b.resize(n);
        ntt<1>(a,n);ntt<1>(b,n);
        cir(i,0,n) (a[i]*=b[i])%=MOD;
        ntt<-1>(a,n);fit(a);
        return a;
    }
} poly;

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
	vector<ulint> A(a,a+n),B(b,b+m);
    c=poly.mul(A,B).data();
}

评测结果