結果

問題 No.42 貯金箱の溜息
ユーザー tnodinotnodino
提出日時 2022-02-23 19:04:19
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 633 ms / 5,000 ms
コード長 1,209 bytes
コンパイル時間 97 ms
コンパイル使用メモリ 11,068 KB
実行使用メモリ 8,328 KB
最終ジャッジ日時 2023-09-14 12:07:42
合計ジャッジ時間 3,242 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 618 ms
8,124 KB
testcase_01 AC 633 ms
8,328 KB
testcase_02 AC 628 ms
8,096 KB
権限があれば一括ダウンロードができます

ソースコード

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