結果

問題 No.1967 Sugoroku Optimization
ユーザー HIcoder
提出日時 2023-07-23 13:08:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,137 ms / 2,000 ms
コード長 3,883 bytes
コンパイル時間 978 ms
コンパイル使用メモリ 113,268 KB
最終ジャッジ日時 2025-02-15 18:30:01
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<set> 
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<queue>
#include<cmath>
#include <unordered_set>
#include<cassert>
using namespace std;
typedef long long ll;
const ll INF=1LL<<60;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const ll MOD=998244353;


//binary_indexed_tree bit;
struct binary_indexed_tree{
    int N;
    vector<ll> bit;
    
    //binary_indexed_tree(){};//ただのコンストラクタ
    
    binary_indexed_tree(int n){
        bit = vector<ll>(n+1,0);
        N=n;
    }

    ~binary_indexed_tree(){
        vector<ll>().swap(bit);
    }



    ll addition(ll x, ll y){
        return (x+y)%MOD;
    }
    void add(int x,ll a){
        x++;//1から始めるための補正
        //for(int i=x; i<=N; i+=(i&-i)) bit[i] = addition(bit[i],a);
        while(x<=N){
            bit[x] = addition(bit[x],a);
            x += x&-x;
        }
    }
    ll sum(int x){
        x++;//1から始まることに注意
        ll ret=0;
        //for(int i=x; i>0; i-=(i&-i)) ret = addition(ret,bit[i]);
        while(x>0){
            ret = addition(ret,bit[x]);
            x -= x&-x;
        }
        
        return ret;
    }

    //[l,r]の範囲
    ll get(int l,int r){
        if(r>N) return 0;//配列の外へのアクセス
        if(l>r) return 0;//本来は l<=r となるのでおかしい
        if(l==0) return sum(r);//[0,r]//ここでoutなわけか
        else return (sum(r) - sum(l-1)+MOD)%MOD;
    }


    
};



ll mod_pow(ll x,ll y,ll mod){
    ll res=1;
    while(y>0){
        if(y&1){
            res*=x;
            res%=mod;
        }
        x*=x;
        x%=mod;
        y/=2;
    }

    return res;
}

int main(){
    int N,K;
    cin>>N>>K;

  
    /*
    dp[i][k]=今iのマスにいる. 残りk回ルーレット
    */
    vector dp(N+1,vector<ll>(K+1,0));


    binary_indexed_tree bit(N+2);
    vector<binary_indexed_tree> bitarray(K+2,bit);

    for(int k=0;k<=K;k++){
        dp[N][k]=1;
        bitarray[k].add(N,1);
       
    }
    /*

    //これだと O(N^2 K )
    for(int i=N-1;i>=0;i--){
        for(int k=K;k>=0;k--){
            
            ll sum=0;         
            
            if(k-1>=0){
                
                for(int t=i+1;t<=N;t++){
                    sum+=dp[t][k-1];
                    sum%=MOD;
                }
            }

            ll a=N-i;
            ll inv=mod_pow(a,MOD-2,MOD); //1/a
            dp[i][k]=sum*inv%MOD;
        }
    }
    */

  

    for(int i=N-1;i>=0;i--){


        for(int k=K;k>=0;k--){
            
        
            ll tmpsum=0;         
            
            if(k-1>=0){    
                //t=[i+1,N]
                tmpsum=bitarray[k-1].get(i+1,N);

            }

            ll a=N-i;
            ll inv=mod_pow(a,MOD-2,MOD); //1/a
            dp[i][k]=tmpsum*inv%MOD;

            bitarray[k].add(i,dp[i][k]);
            
        }
    }

    cout<<dp[0][K]<<endl;
    return 0;

    /*

      vector visit(N+1,vector<bool>(K+1,false));
    vector memo(N+1,vector<ll>(K+1,0));

    //今,nowのマスにいる
    //残りk回回せる
    auto dfs=[&](auto f,int now,int k)->ll{
        
        if(now==N && k>=0) return 1;
        
        if(k>0 && now==N-1) return 1; //次で勝てる
        
        


        if(k==0) return 0; //もう回せないので
        if(visit[now][k]) memo[now][k];

        ll best=0;
        
        ll a=N-now;

        //cout<<"now="<<now<<",k="<<k<<endl;
            
            ll inv=mod_pow(a,MOD-2,MOD); //1/a
        for(int t=1;t<=a;t++){
            //cout<<"t="<<t<<endl;
            best+=f(f,now+t,k-1)*inv%MOD;
            best%=MOD;
        }
        
        visit[now][k]=true;
        return memo[now][k]=best;

    };

    ll ans=dfs(dfs,0,K);
    cout<<ans<<endl;
    */


}
0