結果

問題 No.42 貯金箱の溜息
ユーザー ytft
提出日時 2022-11-05 09:21:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 265 ms / 5,000 ms
コード長 1,017 bytes
コンパイル時間 501 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 77,288 KB
最終ジャッジ日時 2024-07-19 04:43:22
合計ジャッジ時間 1,472 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input=lambda:sys.stdin.readline().rstrip()
mod=10**9+9
C=[[i==0 for i in range(6)] for j in range(6)]
for i in range(1,6):
    for j in range(1,6):
        C[i][j]=C[i-1][j]+C[i-1][j-1]
def inv(a):
    ans=1
    temp=a
    rem=mod-2
    while rem:
        if rem%2:
            ans=(ans*temp)%mod
        temp=(temp**2)%mod
        rem//=2
    return ans
S=[[1,1,0,0,0,0],[0,inv(2),inv(2),0,0,0],[0,inv(6),inv(2),inv(3),0,0],[0,0,inv(4),inv(2),inv(4),0],[0,-inv(30),0,inv(3),inv(2),inv(5)]]
coins=[500,100,50,10,5,1]
def s(poly):
    ans=[0,0,0,0,0,0]
    for i in range(5):
        for j in range(6):
            ans[j]=(ans[j]+poly[i]*S[i][j])%mod
    return ans
def sub(poly,poly2):
    ans=[0,0,0,0,0,0]
    for i in range(6):
        for j in range(i+1):
            ans[j]=(ans[j]+poly[i]*C[i][j]*poly2[1]**j*poly2[0]**(i-j))%mod
    return ans
def solve(M):
    poly=[1,0,0,0,0,0]
    a=[0 for i in range(5)]
    for i in range(5):
        a[4-i]=M//coins[i]
        M%=coins[i]
    for i in range(5):
        poly=s(poly)
        poly=sub(poly,[a[i],[2,5][i%2]])
    print(poly[0])
N=int(input())
for i in range(N):
    solve(int(input()))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0