c560: SF 愛運動

內容

一年一度的 101 大樓爬樓梯競賽始報名囉，喜歡運動的 StillFantasy (以下簡稱 SF ) 毫不猶豫的馬上報名參加。

現在 101 大樓共有 N 階樓梯，每個參賽者都必須從第 0 階走到最後一階（也就是第 N 階），且主辦單位在某些階樓梯設有休息站（一定要剛好走到那階樓梯），提供礦泉水及 Kinder 巧克力 等零食給選手補充體力。

聰明的 SF 想了一個絕對能贏的方法 :

1. 每步可以選擇走三階（EX 0 -> 3）或走一階（EX 0 -> 1 ）

2. 必須到每個休息站休息及吃一個 Kinder 以維持體力。

現在無聊的 CTF 想知道 SF 完成比賽的方法數，請你寫個程式幫助 CTF 算出答案。

輸入

第一行共兩個數字 n 跟 m ，分別代表 101 大樓的階梯總數及休息站的數量。

(1 <= n <= 100000 , 0 <= m < n)

接下來一行共 m 個數字 a [ i ] ( 1 <= a [ i ] < n ) ，代表每個休息站所在的階梯，且 a [ i ] < a [ i + 1]。

5 1
3

輸出

輸出一個數，代表 SF 完成比賽的方法數。

答案可能很大，請 mod 1000000007 。

2

解題思路

c574 的進化版，不知道移動方法數怎麼算的可以參考那篇，這邊就是把原本的兩步改成三步。

這題的目標是到所有的休息站吃到所有的 Kinder，所以取起點到第一個休息站、第一個休息站到第二個、二到三…倒數第一個到終點的移動距離，查表找到對應的階梯移動方法，將它們數相乘即為答案。

完整程式碼

AC (11ms, 500KB)

#include <stdio.h>
#define MAX 100001
#define MOD 1000000007

int DP[MAX] = { 1, 1, 1 }, n, m, kinder, pKinder;
long long ans = 1;

int main()
{
    for (int i = 3; i < MAX; i++)
        DP[i] = (DP[i - 1] + DP[i - 3]) % MOD;
    scanf(" %d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        scanf(" %d", &kinder);
        ans = (ans * DP[kinder - pKinder]) % MOD;
        pKinder = kinder;
    }
    printf("%lld\n", (ans * DP[n - pKinder]) % MOD);
    return 0;
}