結果

問題 No.42 貯金箱の溜息
コンテスト
ユーザー cologne
提出日時 2022-01-23 20:37:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 188 ms / 5,000 ms
コード長 2,170 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 78,196 KB
最終ジャッジ日時 2024-11-30 02:01:02
合計ジャッジ時間 1,536 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys


def input(): return sys.stdin.readline().rstrip()


class Poly:
    """
    Class Denoting Polynomial
    """
    MOD = 10**9+9

    def __init__(self, poly):
        self.poly = poly

    def __mul__(self, other):
        ret = [0]*(len(self.poly)+len(other.poly)-1)
        for i in range(len(self.poly)):
            for j in range(len(other.poly)):
                ret[i+j] = (ret[i+j]+self.poly[i]*other.poly[j]) % Poly.MOD
        return Poly(ret)

    def __add__(self, other):
        ret = self.poly[:] + [0]*max(0, len(other.poly)-len(self.poly))
        for i in range(len(other.poly)):
            ret[i] = (ret[i] + other.poly[i]) % Poly.MOD

        while len(ret) > 1 and ret[-1] == 0:
            ret.pop()
        return Poly(ret)

    def __sub__(self, other):
        ret = self.poly[:] + [0]*max(0, len(other.poly)-len(self.poly))
        for i in range(len(other.poly)):
            ret[i] = (ret[i] - other.poly[i]) % Poly.MOD

        while len(ret) > 1 and ret[-1] == 0:
            ret.pop()
        return Poly(ret)

    def substitute(self, other):
        x = Poly([self.poly[-1]])
        for i in self.poly[-2::-1]:
            x = x * other + Poly([i])

        return x

    def accumulated(self):
        degree = len(self.poly)-1

        P = [Poly([1])]
        Q = [Poly([1])]
        for i in range(degree+1):
            P.append(P[-1]*Poly([0, 1]))
            Q.append(Q[-1]*Poly([-1, 1]))

        ret = [0]*(degree+2)
        remaining = Poly(self.poly[:])
        for i in range(degree+1, 0, -1):
            delta = P[i] - Q[i]
            c = remaining.poly[i-1] * \
                pow(delta.poly[i-1], -1, Poly.MOD) % Poly.MOD
            remaining -= delta * Poly([c])
            ret[i] = c

        ret[0] = self.poly[0]
        return Poly(ret)


def main():
    D = [Poly([1])]
    for i in [5, 10, 50, 100, 500]:
        D = [D[j % len(D)].substitute(
            Poly([j // len(D), i // len(D)])).accumulated() for j in range(i)]

    T = int(input())
    for i in range(T):
        M = int(input())
        print(D[M % 500].substitute(Poly([M // 500])).poly[0])


if __name__ == '__main__':
    main()
0