#1179304 (C++23) No.3574 Sum of Mex

• 問題: No.3574 Sum of Mex
• ユーザー: yaaya
• 提出日時: 2026-08-26 09:37:05
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: TLE
• 実行時間: -
• コード長: 10,464 bytes
• コンパイル時間: 3,365 ms
• コンパイル使用メモリ: 357,664 KB
• 実行使用メモリ: 162,108 KB
• 最終ジャッジ日時: 2026-08-26 09:37:15
• 合計ジャッジ時間: 9,065 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	AC * 10 TLE * 1

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define ll long long
#define ull unsigned ll
#define ld long double
#define bl __int128_t
#define fi first
#define se second
#define vel vector<ll>
#define vvel vector<vel>
#define pll pair<ll,ll>
#define vepll vector<pll>
#define vvepll vector<vepll>
#define ves vector<string>
#define mint Mint<998244353>
#define vem vector<mint>
#define vvem vector<vem>
#define pmm pair<mint,mint>
#define cleout(i) cout<<fixed<<setprecision(i)
template<class T>using PQ=priority_queue<T,vector<T>,greater<T>>;
//               上  右 下 左
vector<int> di={-1, 0, 1, 0};
vector<int> dj={ 0, 1, 0,-1};

vector<int> dx={ 0, 1, 0,-1};
vector<int> dy={ 1, 0,-1, 0};


vector<int> ddx={ 1, 1, 1, 0, -1, -1, -1, 0 };
vector<int> ddy={ 1, 0, -1, -1, -1, 0, 1, 1 };

ll inf=1000000000000000000;//1e18
// LLONG_MAX

mt19937_64 rng((ull)chrono::steady_clock::now().time_since_epoch().count());

template<ll P>
struct Mint{
    ll num;
    static constexpr ll MOD=P;
    Mint(ll x=0){
        if(x<0){
            x*=-1;
            x%=P;
            x=P-x;
        }
        x%=P;
        num=x;
    }
    Mint operator+(const Mint &other)const{
        return Mint(num+other.num);
    }
    Mint operator-(const Mint &other)const{
        return Mint(num-other.num);
    }
    Mint operator*(const Mint &other)const{
        return Mint(num*other.num);
    }
    Mint &operator+=(const Mint &other){
        num+=other.num;
        if(num>=P) num-=P;
        return *this;
    }
    Mint &operator-=(const Mint &other){
        num-=other.num;
        if(num<0) num+=P;
        return *this;
    }
    Mint &operator*=(const Mint &other){
        num=(num*other.num)%P;
        return *this;
    }
    Mint beki(const ll &x)const{
        Mint res=1;
        Mint now=num;
        rep(i,0,60){
            if(x&(1ll<<i)){
                res*=now;
            } 
            now*=now;
        }
        return res;
    }
    Mint inv()const{
        Mint res=1;
        Mint now=num;
        rep(i,0,30){
            if((P-2)&(1ll<<i)){
                res*=now;
            } 
            now*=now;
        }
        return res;
    }
    Mint operator/(const Mint &other)const{
        return *this*other.inv();
    }
    Mint &operator/=(const Mint &other){
        num=(num*other.inv())%P;
        return *this;
    }
    operator ll()const{
        return (ll)(num);
    }
    friend ostream& operator<<(ostream& os, const Mint& m) {
        os << m.num;
        return os;
    }
    friend istream& operator>>(istream& is, Mint& m) {
        ll x;
        is>>x;
        m=Mint(x);
        return is;
    }
};

struct fps:std::vem{
    using vem::vector;

    static fps DFT(fps &f,mint iv){
        ll cnt=1;
        ll size=f.size()/2;
        fps INV(f.size(),1);
        INV[1]=iv;
        rep(i,2,f.size()){
            INV[i]=INV[i-1]*iv;
        }
        ll SIZE=1;
        while(size!=0){
            rep(i,0,SIZE){
                mint IV=1;
                ll I=i*(mint)2*size;
                rep(j,0,size){
                    f[I+j]=f[I+j]+f[I+size+j];
                    f[I+size+j]=(f[I+j]-(mint)2*f[I+size+j])*INV[cnt*j];
                }
            }
            cnt<<=1;
            size>>=1;
            SIZE<<=1;
        }
        int n=f.size();
        int j=0;
        for(int i=1;i<n-1;i++){
            int bit=n>>1;
            while(j>=bit){
                j-=bit;
                bit>>=1;
            }
            j+=bit;
            if(i<j)std::swap(f[i],f[j]);
        }
        return f;
    }
    fps &operator*=(const mint &c){
        rep(i,0,this->size()){
            (*this)[i]*=c;
        }
        return *this;
    }
    fps operator*(const mint &c)const{
        return (fps(*this)*=c);
    }
    fps &operator/=(const mint &c){
        mint c_inv=(mint)1/c;
        rep(i,0,this->size()){
            (*this)[i]*=c_inv;
        }
        return *this;
    }
    fps operator/(const mint &c)const{
        return (fps(*this)/=c);
    }
    fps pre(ll d){
        fps res(this->begin(),this->begin()+min((ll)this->size(),d));
        if(this->size()<d)res.resize(d,0);
        return res;
    }
    void shrink(){
        while(this->size()&&this->back()==0)this->pop_back();
    }
    fps &operator+=(const fps &other){
        if(other.size()>this->size()){
            this->resize(other.size(),0);
        }
        rep(i,0,other.size()){
            (*this)[i]+=other[i];
        }
        return *this;
    }
    fps operator+(const fps &other)const{
        return (fps(*this)+=other);
    }
    fps &operator-=(const fps &other){
        if(other.size()>this->size()){
            this->resize(other.size(),0);
        }
        rep(i,0,other.size()){
            (*this)[i]-=other[i];
        }
        return *this;
    }
    fps operator-(const fps &other)const{
        return (fps(*this)-=other);
    }
    fps operator*(const fps &other)const{
        if(this->empty()||other.empty())return{};
        int rsz=this->size()+other.size()-1;
        int sz=bit_ceil((ull)this->size()+other.size()-1);

        mint w=mint(3).beki(998244352/sz);

        fps Fthis(this->begin(),this->end());
        Fthis.resize(sz);
        Fthis=DFT(Fthis,w);

        fps Fother=other;
        Fother.resize(sz);
        Fother=DFT(Fother,w);

        rep(i,0,Fthis.size())Fthis[i]*=Fother[i];
        fps res=DFT(Fthis,(mint)1/w);
        res.resize(rsz);
        return res/(mint)sz;
    }
    fps &operator*=(const fps &other){
        *this=(*this)*other;
        return *this;
    }
    fps &operator<<=(int d){
        this->insert(this->begin(),d,(mint)0);
        return *this;
    }
    fps operator<<(int d)const{
        return(fps(*this)<<=d);
    }
    fps &operator>>=(int d){
        if((ll)this->size()<=d){
            this->clear();
        }else{
            this->erase(this->begin(),this->begin()+d);
        }
        return *this;
    }
    fps operator>>(int d)const{
        return(fps(*this)>>=d);
    }
    void show(){
        for(auto it=this->begin();it!=this->end();it++){
            cout<<*it<<" ";
        }
        cout<<"\n";
    }
};
mint bostan_mori(fps f,fps g,ll K){//[x^k]f/g
    fps og;
    while(K){
        og=g;
        for(ll i=1;i<og.size();i+=2){
            og[i]=-og[i];
        }
        f*=og;
        g*=og;
        ll f_size=0;
        ll g_size=0;
        for(ll i=0;2*i<g.size();i++){
            g[i]=g[2*i];
            g_size++;
        }
        g.resize(g_size);
        for(ll i=0;2*i+(K%2)<f.size();i++){
            f[i]=f[2*i+(K%2)];
            f_size++;
        }
        f.resize(f_size);
        K/=2;
    }
    return f.size()?f[0]/g[0]:(mint)0;
}
pair<ll,fps> Berlekamp_Massey(fps &S){
    ll N=S.size();
    fps Q={1};
    ll L=0;
    fps B={1};
    ll n0=-1;
    mint b=1;
    rep(n,0,N){
        mint d=0;
        rep(j,0,min((ll)Q.size(),n+1))d+=Q[j]*S[n-j];
        if(d==0)continue;
        fps Q_new=Q-(B<<(n-n0))*(d/b);
        ll L_new;
        if(2*L<=n){
            L_new=n+1-L;
            B=Q;
            n0=n;
            b=d;
        }else L_new=L;
        Q=Q_new;
        L=L_new;
    }
    return {L,Q};
}
mint BMBM(fps &f,ll K,bool debug=false){
    auto[L,Q]=Berlekamp_Massey(f);
    if(debug)cout<<f.size()<<" "<<2*L<<endl;
    assert((ll)f.size()>=2*L);
    fps P=(f*Q).pre(Q.size()-1);
    P.shrink();
    return bostan_mori(P,Q,K);
}
fps Str(ll K){//klogk
    fps f(K+1,0);
    fps g(K+1,0);
    mint dv=1;
    rep(i,1,K+1)dv*=(mint)i;
    dv=(mint)1/dv;
    rrep(i,K+1,1){
        f[i]=dv;
        if(i%2)f[i]*=(mint)(-1);
        mint I=i;
        g[i]=I.beki(K)*dv;
        dv*=(mint)i;
    }
    f[0]=1;
    return f*g.pre(K+1);
}

struct CB{
    vem n,r;
    CB(ll N){//N以下のものをmod INFで返す
        n.assign(N+1,1);
        r.assign(N+1,1);
        rep(i,2,N+1){
            n.at(i)=n.at(i-1)*mint(i);
        }
        r.back()=n.back().inv();
        rrep(i,N,0) r.at(i)=r.at(i+1)*(mint)(i+1);
    }
    mint comb(ll N,ll R){//NCR
        if(N<R) return 0;
        return n.at(N)*r.at(R)*r.at(N-R);
    }
    mint P(ll N,ll R){//NPR
        return n.at(N)*r.at(N-R);
    }
};
CB cb(1.1e6);

mint get_val(fps &v,int i){
    return (i<v.size())?v[i]:(mint)0;
}

fps inverse(fps &f,ll N=0){
    if (N==0)N=f.size();
    fps res={(mint)1/f[0]};
    while(res.size()<N){
        ll n=res.size();
        ll target=2*n;
        fps f_part(target);
        rep(i,0,target)f_part[i]=get_val(f,i);
        fps mul=res*f_part;
        if(mul.size()>target)mul.resize(target);
        mul[0]-=(mint)2;
        rep(i,0,mul.size())mul[i]*=(mint)-1;
        res=res*mul;
        if(res.size()>target)res.resize(target);
    }
    if(res.size()>N)res.resize(N);
    return res;
}

fps log(fps &f,ll N=0){
    if(N==0)N=f.size();
    fps inv=inverse(f,N);
    // 微分
    fps df(N-1);
    rep(i,0,N-1)df[i]=get_val(f,i+1)*(mint)(i+1);
    fps res=df*inv;
    // 積分
    fps ret(N);
    ret[0]=0;
    rep(i,1,N)ret[i]=get_val(res,i-1)*cb.n[i-1]*cb.r[i];
    return ret;
}

fps exp(fps &f,ll N=0){
    if(N==0)N=f.size();
    fps res={1};
    while(res.size()<N){
        ll len=res.size()*2;
        fps l_res=log(res,len);
        fps mul(len);
        rep(i,0,len)mul[i]=get_val(f,i)-l_res[i];
        mul[0]+=(mint)1;
        res=res*mul;
        if(res.size()>len)res.resize(len);
    }
    if(res.size()>N)res.resize(N);
    return res;
}
fps pow(fps &f,ll Pow,ll N=0){
    if(N==0)N=f.size();
    ll pos=0;
    while(pos<f.size()){
        if(f[pos]==0)pos++;
        else break;
    }
    if(pos==f.size()||pos*Pow>=N){
        fps ret(N,0);
        return ret;
    }
    fps g=f>>pos;
    mint c=g[0];
    g/=c;
    fps ret=log(g,N)*(mint)Pow;
    ret=exp(ret,N)<<(Pow*pos);
    ret=ret.pre(N);
    ret*=c.beki(Pow);
    return ret;
}

void _solve(){
    ll N;
    cin>>N;
    fps h(N+1);
    rep(i,1,N+1){
        h[i]=cb.r[i];
    }
    fps e(N+1);
    rep(i,0,N+1){
        e[i]=cb.r[i];
    }
    fps ret=h*(pow(e,N)-pow(h,N));
    fps S=Str(N);
    mint ans=0;
    mint mul=N;
    rep(k,1,N+1){
        ans+=cb.comb(N,k)*(S[k]*cb.n[k])*mul.beki(N-k)*(ret[k]*cb.n[k]);
    }
    cout<<ans<<"\n";
}

int main(){
    cin.tie(nullptr);
 	ios_base::sync_with_stdio(false);


    ll _;
    bool multitest=0;
    if(multitest)cin>>_;
    else _=1;
    rep(__,0,_){
        _solve();
    }
}