結果

問題 No.1967 Sugoroku Optimization
コンテスト
ユーザー LyricalMaestro
提出日時 2025-08-07 22:56:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 178 ms / 2,000 ms
コード長 673 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 138,056 KB
最終ジャッジ日時 2025-08-07 22:56:44
合計ジャッジ時間 3,604 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1967

MOD = 998244353

def main():
    N, K = map(int, input().split())

    dp = [[0] * (K + 1) for _ in range(N + 1)]
    cum_dp = [[0] * (K + 1) for _ in range(N + 1)]
    for j in range(K + 1):
        dp[-1][j] = 1
        cum_dp[-1][j] = 1

    for i in reversed(range(N)):
        a = N - i
        inv_a = pow(a, MOD - 2, MOD)

        for k in range(K):
            y = cum_dp[i + 1][k + 1]
            y *= inv_a
            y %= MOD
            dp[i][k] = y

        for k in range(K + 1):
            cum_dp[i][k] = (cum_dp[i + 1][k] + dp[i][k]) % MOD
    
    print(dp[0][0])
    






if __name__ == "__main__":
    main()
0