結果

問題 No.42 貯金箱の溜息
コンテスト
ユーザー dango
提出日時 2023-07-09 16:17:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 101 ms / 5,000 ms
コード長 659 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,724 KB
実行使用メモリ 76,484 KB
最終ジャッジ日時 2024-07-23 13:27:31
合計ジャッジ時間 1,101 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10 ** 9 + 9
invs = [0] * 100
invs[1] = 1
for i in range(2, 100):
    invs[i] = (invs[MOD % i] * (MOD - MOD // i)) % MOD

C = [1, 1, 2, 10, 20, 100]
p = [1]
for i in range(5):
    np = [0] * (len(p) + 100 - C[i])
    for j in range(0, 100, C[i]):
        for k in range(len(p)):
            np[j + k] += p[k]
    p = np
T = int(input())
for _ in range(T):
    n = int(input()) // 5
    m = MOD + n // 100 % MOD
    r = n % 100
    ans = 0
    while r < len(p) and r <= n:
        b = 1
        for i in range(5):
            b = b * (m + 5 - i) % MOD * invs[i + 1] % MOD
        ans += p[r] * b % MOD
        r += 100
        m -= 1
    print(ans % MOD)
0