b065: 電電的彈簧床
Tags : DP
Accepted rate : 3人/4人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-06 22:56

Content

電電有N個彈簧床,有一天他覺得很無聊,於是就把他們排成一排,然後從第一個彈簧床開始跳到最後一個彈簧床。

可是他覺得這樣還是很無聊,所以他決定不要一個一個跳,而是一次跳過很多個彈簧床。

對於每個彈簧床i都有一個強度值$s_i$,代表從彈簧床i起跳最多可以跳到彈簧床$i+s_i$。

電電跳了幾次之後還是覺得有點無聊,所以他限制自己跳的次數必須要剛好是K。

結合運動、臨場反應跟心算的遊戲果然讓電電玩的很開心,不過他之後開始想....依照他訂的遊戲規則,他總共有幾種完成的方法?

這個答案可能很大,所以請輸出答案除以1000000009的餘數。

 

注意電電在跳彈簧床的時候只能往前跳,不能往後或是原地跳。而且電電必須剛好落在第N個彈簧床才算結束,不能跳超過。

Input

第一行是兩個數字$N,K(1 \leq K < N \leq 2000)$。

第二行有N個正整數,表示$s_{i}(1 \leq s_i \leq N)$。

Output

輸出電電完成遊戲有幾種方法,並對1000000009取模。

Sample Input
// 1
5 3
1 4 3 2 5

// 2
6 1
4 1 2 3 4 5

// 3
7 2
6 6 6 6 6 6 6
Sample Output
// 1
2

// 2
0

// 3
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :

範例1有兩種跳法: 1->2->3->5, 1->2->4->5

範例2不可能只跳一次就跳到,所以答案是0。

範例3:1 -> (2,3,4,5,6) -> 7

Tags:
DP
出處:
臺中一中電腦資訊研習社 [管理者:
810848 (路過)
]


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