c257: 11915 - Recurrence
Tags : 遞迴 數學
Accepted rate : 1人/5人 ( 20% ) [非即時]
評分方式:
Strictly

最近更新 : 2018-08-27 14:10

Content

考慮函數F(p[1],p[2],...,p[n])

其中F(p[1],p[2],...,p[n])=1若p[1]=p[2]=...=p[n]=0

F(p[1],p[2],...,p[n])=F(p[1]-1,p[2],...,p[n])+F(p[1],p[2]-1,...,p[n])+...+F(p[1],p[2],...,p[n]-1)若p[1]>=p[2]>=...>=p[n]>=0

剩下的都對應到0

求F(p[1],p[2],...,p[n])

Input

測資比數T<=50

正整數n<=1000

正整數p[1],p[2],...,p[n]<=1000

並保證p[1]>=p[2]>=...>=p[n]

Output

Case t: F(p[1],p[2],...,p[n])%(10^9+9)

註:10^9+9是質數,t是第幾比測資

Sample Input
8
3
7 5 4
6
7 7 5 3 2 1
2
4 2
3
7 4 4
4
8 7 5 5
5
7 7 6 5 5
2
8 7
3
6 3 1
Sample Output
Case 1: 100100
Case 2: 398009117
Case 3: 9
Case 4: 25025
Case 5: 923714728
Case 6: 311516464
Case 7: 1430
Case 8: 315
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (100%): 2.0s , <1M
Hint :

* 目前測資挺弱的

Tags:
遞迴 數學
出處:
UVA 11915 [管理者:
k034006 (Sine Wu)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」