2011-06-10 21:23:25Morris
d916. 4. 高空煙火時間限制
http://zerojudge.tw/ShowProblem?problemid=d916
內容 ：
一家專門為大型活動施放煙火的公司，在這次花博標到一件案子，負責沿著河岸施放高空煙火，在河岸每間隔一定距離會設立一個煙火施放點，假設總共有 N 個施放點。煙火的類型主要有兩類，分別為單色系列及彩色系列。單色系列的煙火施放後僅會出現單一顏色的煙火，而彩色系列的煙火施放後會出現多種顏色的彩色煙火。為了讓煙火施放效果生動，兩個施放彩色煙火的施放點之間必須至少有 M 個施放單色煙火的施放點間隔開來，因此施放煙火的方式有許多種可能的施放組合。例如：N = 3, M = 1 時有 5 種可能施放的方式，即：單單單，彩單單，單單彩，單彩單，彩單彩。
阿博剛好在這家公司打工，給定施放點的個數 N 及 M 的值，阿博的老板要他幫忙算出有多少種可能的施放煙火方式。你的任務是寫一個程式幫阿博計算出所有可能的施放方式。因為答案可能是非常大的數字，為了讓大家能夠簡化運算，所以我們只要求輸出答案最右邊的四位數 (以十進位表示)，也就是答案除以10000 後的餘數 (以十進位表示)。
阿博剛好在這家公司打工，給定施放點的個數 N 及 M 的值，阿博的老板要他幫忙算出有多少種可能的施放煙火方式。你的任務是寫一個程式幫阿博計算出所有可能的施放方式。因為答案可能是非常大的數字，為了讓大家能夠簡化運算，所以我們只要求輸出答案最右邊的四位數 (以十進位表示)，也就是答案除以10000 後的餘數 (以十進位表示)。
輸入說明
：
輸入檔包含兩個正整數 N 及 M ，其中 N 代表施放煙火的施放點總數，M 用來代表兩個施放彩色煙火的施放點之間必須至少有 M 個施放單色煙火的施放點間隔開來。其中 1 <= M < N <= 3000，並以一或多個空白隔開。
輸出說明
：
假設所有可能施放煙火方式的總數為 P，請輸出 P 除以 10000 後的餘數 (以十進位表示)。
範例輸入 ：
輸入範例 1: 3 l 輸入範例 2: 19 1 輸入範例 3: 25 1
範例輸出 ：
輸出範例 l: 5 輸出範例 2: 946 輸出範例 3: 6418
提示
：
出處
：
/**********************************************************************************/
/* Problem: d916 "4. 高空煙火時間限制" from 99資訊能力競賽全國決賽*/
/* Language: C */
/* Result: AC (39ms, 17204KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-09 23:27:17 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define Mod 10000
short P[3011][3011] = {0};
int PASCAL() {
int a, b;
P[0][0] = 1;
for(a = 1; a <= 3010; a++) {
P[a][0] = 1;
for(b = 1; b < a; b++)
P[a][b] = (P[a-1][b] + P[a-1][b-1])%Mod;
P[a][a] = 1;
}
}
main() {
int N, M;
PASCAL();
while(scanf("%d %d", &N, &M) == 2) {
int Ans=0, a;
for(a = 0;a <= N + 1; a++) {
if(N - (a-1)*M >= 0) {
Ans = (Ans + P[N - (a-1)*M][a])%Mod;
}
else break;
}
printf("%d\n",Ans);
}
return 0;
}
上一篇：d914. 2. 圍棋資料庫比對
下一篇：d908. 4. 最佳路徑