Submit Ranklist
Problem : 37 - 高空煙火時間限制
Problem Statistics
Solved Member:
41 Submission:
112 User Tried:
44 Statement:
一家專門為大型活動施放煙火的公司，在這次花博標到一件案子，負責沿著河岸施放高空煙火，在河岸每間隔一定距離會設立一個煙火施放點，假設總共有 N 個施放點。煙火的類型主要有兩類，分別為單色系列及彩色系列。單色系列的煙火施放後僅會出現單一顏色的煙火，而彩色系列的煙火施放後會出現多種顏色的彩色煙火。為了讓煙火施放效果生動，兩個施放彩色煙火的施放點之間必須至少有 M 個施放單色煙火的施放點間隔開來，因此施放煙火的方式有許多種可能的施放組合。例如：N = 3, M = 1 時有 5 種可能施放的方式，即：單單單，彩單單，單單彩，單彩單，彩單彩。
阿博剛好在這家公司打工，給定施放點的個數 N 及 M 的值，阿博的老板要他幫忙算出有多少種可能的施放煙火方式。你的任務是寫一個程式幫阿博計算出所有可能的施放方式。因為答案可能是非常大的數字，為了讓大家能夠簡化運算，所以我們只要求輸出答案最右邊的四位數 (以十進位表示)，也就是答案除以10000 後的餘數 (以十進位表示)。
Input:Output:
輸入檔包含兩個正整數 N 及 M ，其中 N 代表施放煙火的施放點總數，M 用來代表兩個施放彩色煙火的施放點之間必須至少有 M 個施放單色煙火的施放點間隔開來。其中 1 <= M < N <= 3000，並以一或多個空白隔開。
假設所有可能施放煙火方式的總數為 P，請輸出 P 除以 10000 後的餘數 (以十進位表示)。
Sample Input:Sample Output:
輸入範例 1:
3 1
輸入範例 2:
19 1
輸入範例 3:
25 1
輸出範例 1:
5
輸出範例 2:
946
輸出範例 3:
6418
Source:
99 全國賽
Problem Setter
Nekosyndrome Testdata:
| Test | Time | Memory | Score |
|---|
| 0-1 | 2000ms | 32768kb | |
| 0-2 | 2000ms | 32768kb | |
| 0-3 | 2000ms | 32768kb | |
| 1 | 2000ms | 32768kb | 20 |
| 2 | 2000ms | 32768kb | 20 |
| 3 | 2000ms | 32768kb | 20 |
| 4 | 2000ms | 32768kb | 20 |
| 5 | 2000ms | 32768kb | 20 |