結果

問題 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()))
0