結果

問題 No.42 貯金箱の溜息
コンテスト
ユーザー tnodino
提出日時 2022-02-23 19:04:19
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 786 ms / 5,000 ms
コード長 1,209 bytes
コンパイル時間 101 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-07-01 19:33:53
合計ジャッジ時間 3,842 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LagrangeInterpolation:
    def __init__(self, dig, mod):
        self.dig = dig
        self.mod = mod

    def BinPower(self, x):
        k = self.mod - 2
        ret = 1
        while k > 0:
            if k & 1:
                ret = ret * x % self.mod
            x = x * x % self.mod
            k >>= 1
        return ret

    def init(self, X, Y, T):
        ret = 0
        for i in range(self.dig+1):
            A = 1
            B = 1
            for j in range(self.dig+1):
                if i == j:
                    continue
                A *= T - X[j]
                A %= self.mod
                B *= X[i] - X[j]
                B %= self.mod
            ret += (Y[i] * A % self.mod) * self.BinPower(B) % self.mod
            ret %= self.mod
        return ret

mod = 10**9+9
N = 3000
M = [1, 5, 10, 50, 100, 500]
DP = [0] * N
DP[0] = 1
for k in range(6):
    for i in range(N):
        if i - M[k] >= 0:
            DP[i] += DP[i-M[k]]
            DP[i] %= mod
Lag = LagrangeInterpolation(5, mod)
T = int(input())
for _ in range(T):
    M = int(input())
    Rem = M % 500
    X = [i for i in range(Rem,N,500)]
    Y = [DP[i] for i in range(Rem,N,500)]
    print(Lag.init(X, Y, M))
0