結果

問題 No.42 貯金箱の溜息
ユーザー lam6er
提出日時 2025-04-16 00:10:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 118 ms / 5,000 ms
コード長 2,909 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 81,900 KB
実行使用メモリ 77,376 KB
最終ジャッジ日時 2025-04-16 00:12:03
合計ジャッジ時間 1,170 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 9

# Precompute C(k) for k from 0 to 599
max_k = 599
C = [0] * (max_k + 1)
for k in range(max_k + 1):
    cnt = 0
    max_e = k // 100
    for e in range(max_e + 1):
        rem_k = k - 100 * e
        max_d = rem_k // 20
        for d in range(max_d + 1):
            rem_k2 = rem_k - 20 * d
            max_c = rem_k2 // 10
            for c in range(max_c + 1):
                rem_k3 = rem_k2 - 10 * c
                max_b = rem_k3 // 2
                cnt += max_b + 1
    C[k] = cnt % MOD

# Compute ans(q) as the prefix sum of C
ans = [0] * (max_k + 1)
current = 0
for k in range(max_k + 1):
    current = (current + C[k]) % MOD
    ans[k] = current

# For each residue r (0..99), collect the values ans(100m + r) for m=0,1,2,3,4,5
# Then perform Lagrange interpolation to find the coefficients of the polynomial
# Since the polynomial is of degree 5, we need 6 points
# We'll store for each residue r the coefficients of the polynomial a_5 m^5 + ... + a_0

from itertools import product

def lagrange_interpolation(xs, ys, mod):
    n = len(xs)
    res = [0] * n
    for i in range(n):
        numerator = [1]
        for j in range(n):
            if i == j:
                continue
            numerator = mul_poly(numerator, [-xs[j], 1], mod)
        denom = 1
        for j in range(n):
            if i == j:
                continue
            denom = denom * (xs[i] - xs[j]) % mod
        inv_denom = pow(denom, mod-2, mod)
        numerator = [y * inv_denom % mod for y in numerator]
        numerator = [y * ys[i] % mod for y in numerator]
        res = add_poly(res, numerator, mod)
    return res

def mul_poly(a, b, mod):
    res = [0] * (len(a) + len(b) - 1)
    for i in range(len(a)):
        for j in range(len(b)):
            res[i+j] = (res[i+j] + a[i] * b[j]) % mod
    return res

def add_poly(a, b, mod):
    res = [0] * max(len(a), len(b))
    for i in range(len(a)):
        res[i] = (res[i] + a[i]) % mod
    for i in range(len(b)):
        res[i] = (res[i] + b[i]) % mod
    return res

# Precompute coefficients for each residue
coeff = {}
for r in range(100):
    xs = []
    ys = []
    for m in range(6):
        q = 100 * m + r
        if q > max_k:
            break
        xs.append(m)
        ys.append(ans[q])
    if len(xs) < 6:
        # Not enough points, but in our case, max_k=599, r=99: 100*5+99=599, so all residues have 6 points
        pass
    poly = lagrange_interpolation(xs, ys, MOD)
    coeff[r] = poly

# Read input and process each test case
import sys
input = sys.stdin.read().split()
T = int(input[0])
cases = list(map(int, input[1:T+1]))

for M in cases:
    q = M // 5
    r = q % 100
    m = (q - r) // 100
    if m < 0:
        print(0)
        continue
    poly = coeff[r]
    res = 0
    for i, c in enumerate(poly):
        term = c
        term = term * pow(m, i, MOD) % MOD
        res = (res + term) % MOD
    print(res)
0