結果

問題 No.42 貯金箱の溜息
ユーザー tnodinotnodino
提出日時 2022-02-23 19:04:19
言語 Python3
(3.11.2 + numpy 1.24.2 + scipy 1.10.1)
結果
AC  
実行時間 930 ms / 5,000 ms
コード長 1,209 bytes
コンパイル時間 404 ms
実行使用メモリ 8,052 KB
最終ジャッジ日時 2023-02-02 02:53:29
合計ジャッジ時間 5,232 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 901 ms
7,892 KB
testcase_01 AC 926 ms
8,052 KB
testcase_02 AC 930 ms
7,948 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