結果

問題 No.42 貯金箱の溜息
ユーザー dangodango
提出日時 2023-07-09 16:17:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 136 ms / 5,000 ms
コード長 659 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 87,168 KB
実行使用メモリ 78,528 KB
最終ジャッジ日時 2023-09-30 19:39:35
合計ジャッジ時間 1,351 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 136 ms
78,528 KB
testcase_01 AC 123 ms
77,392 KB
testcase_02 AC 122 ms
77,376 KB
権限があれば一括ダウンロードができます

ソースコード

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