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

最近更新 : 2020-07-04 23:29

Content

(2020/07/04 18:46) 測資已修復,並重測完成

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3066

考慮函數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

非負整數0<=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 #1
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 #1
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
沒有發現任何「解題報告」