結果
問題 |
No.1967 Sugoroku Optimization
|
ユーザー |
|
提出日時 | 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 |
ソースコード
## 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()