結果
問題 |
No.1011 Infinite Stairs
|
ユーザー |
![]() |
提出日時 | 2023-03-21 21:12:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 793 ms / 2,000 ms |
コード長 | 596 bytes |
コンパイル時間 | 219 ms |
コンパイル使用メモリ | 82,724 KB |
実行使用メモリ | 225,988 KB |
最終ジャッジ日時 | 2024-09-18 14:30:56 |
合計ジャッジ時間 | 5,301 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
# dp[i階][j回の移動]回数は当然TLEした # 実験するとdの個数分だけの前行の和となる # 累積sdpとするか N, d, K = map(int, input().split()) dp = [0]*(K+1) sdp = [1]*(K+2) dp[0] = 1 sdp[0] = 0 mod = 10**9+7 #print(dp) #print(sdp) for i in range(1, N+1): new_dp =[0]*(K+1) for j in range(K+1): new_dp[j] = sdp[j]-sdp[max(0, j-d)] new_dp[j] %= mod dp = new_dp sdp = [0] temp = 0 for j in range(K+1): temp += dp[j] temp %= mod sdp.append(temp) #print(dp) #print(sdp) ans = dp[K]%mod print(ans)