結果

問題 No.129 お年玉(2)
ユーザー lam6er
提出日時 2025-04-15 21:01:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 200 ms / 5,000 ms
コード長 391 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 81,836 KB
実行使用メモリ 59,904 KB
最終ジャッジ日時 2025-04-15 21:06:58
合計ジャッジ時間 5,647 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9

n = int(input())
m = int(input())

s = n // 1000
r = s % m

if r == 0:
    print(1 % MOD)
else:
    r = min(r, m - r)
    dp = [0] * (r + 1)
    dp[0] = 1
    for i in range(1, m + 1):
        # Iterate j in reverse to avoid overwriting values we need
        end = min(i, r)
        for j in range(end, 0, -1):
            dp[j] = (dp[j] + dp[j-1]) % MOD
    print(dp[r] % MOD)
0