c560: SF 愛運動

c560: SF 愛運動

題目連結：c560: SF 愛運動

題意：

第一行共兩個數字n,m(1<=n<=100000,0<=m<n)，分別代表 101 大樓的階梯總數及休息站的數量。

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

SF可以一次走1階或走3階，請輸出SF完成比賽的方法數並 mod 1000000007。

解法：

因為每個休息點都要走到，所以我們可以把問題簡化成：

(從起點走到第一個休息點的方法數)*(從第一個休息點走到第二個休息點的方法數)*(從第二個休息點走到第三個休息點的方法數)*......*(從第m個休息點走到終點的方法數)。

我們仔細觀察後可以發現方法數是費氏數列的變形。

F[0]=1

F[1]=1

F[2]=1

F[N]=(F[N-1]+F[N-3])%1000000007

Python:

time:0.2s

memory used:14.5MB

code:

1. f=[1,1,1]
2. for i in range(3,100001):
3.  f.append((f[i-1]+f[i-3])%1000000007)
5. ans=1
6. start=0
7. a,b=input().split()
8. a=int(a)
9. b=int(b)
10. line=input().split()
11. for i in range(b):
12.  x=int(line[i])
13.  ans=(ans*f[x-start])%1000000007
14.  start=x
15. ans=(ans*f[a-start])%1000000007
16. print(ans)

本人的分享到此結束

若有更好的想法或建議,請在留言區留言喔