b065: 電電的彈簧床
Tags : DP prefix_sum
Accepted rate : 8人/10人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-16 12:07

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

Sample Output #1
2
Sample Input #2
6 1
4 1 2 3 4 5

Sample Output #2
0
Sample Input #3
7 2
6 6 6 6 6 6 6
Sample Output #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 prefix_sum
出處:
臺中一中電腦資訊研習社 [管理者:
810848 (路過)
]


ID User Problem Subject Hit Post Date
121
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
b065
參考想法
83 2022-04-15 14:41