結果
問題 |
No.1967 Sugoroku Optimization
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:55:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 1,128 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 76,516 KB |
最終ジャッジ日時 | 2025-03-31 17:57:00 |
合計ジャッジ時間 | 2,806 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
MOD = 998244353 def main(): import sys input = sys.stdin.read N, K = map(int, input().split()) # Precompute inverses of 1..N max_inv = N inv = [1] * (max_inv + 2) for i in range(2, max_inv + 1): inv[i] = pow(i, MOD - 2, MOD) # Initialize DP table dp_prev = [0] * (N + 1) dp_prev[N] = 1 # dp[0][x] = 1 if x == N else 0 for k in range(1, K+1): # Compute prefix sums of dp_prev pre_sum = [0] * (N + 1) pre_sum[0] = dp_prev[0] for i in range(1, N+1): pre_sum[i] = (pre_sum[i-1] + dp_prev[i]) % MOD dp_current = [0] * (N + 1) for x in range(N): a = N - x if a == 0: continue # sum_{y = x+1 to N-1} dp_prev[y] + 1 (from s=a) sum_val = (pre_sum[N-1] - pre_sum[x] + 1) % MOD # Handle negative mod sum_val = (sum_val + MOD) % MOD dp_current[x] = sum_val * inv[a] % MOD dp_prev = dp_current result = dp_prev[0] % MOD print(result) if __name__ == '__main__': main()