本題暗示有夠明顯，就是要求費氏數列的和。

遞迴：$O(2^n)$ Bad!!

計算費氏數列最入門的方法，遞迴，有許多改進的空間，例如求 F(n) 而呼叫 F(n-1) 及 F(n-2)，復各自呼叫 F(n-2)、F(n-3)、F(n-3) 及 F(n-4)，在過程中會不斷重複呼叫同樣的值，十分浪費。簡單證明時間複雜度：$T(n) = T(n-1) + T(n-2) \in O(F(n))$ 也是費氏數列，不過通常也可以寫成 $O(2^n)$，因為費氏數量各項之比趨近於黃金比例 $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ 而 $Big-O$ 表緊的漸進上界，故 $O(2^n)$ 合理。

其實，那些在教遞迴時提到費氏數列或在教費氏數列時提到遞迴的人實在是誤人子弟。費氏數列確實是遞迴數列，但不代表要以遞迴計算之啊！！正常人如何數費氏數列？？$1, 1, 2, 3, 5, 8, \cdots$ 一個一個加啊！！假若你看到費氏數列只想到遞迴，那你中毒太深惹，可憐哪。用遞迴算費氏數無疑是反社會行為，正常人類都使用下一個方法：遞推。

遞推：$O(n)$

離題惹。對於遞迴常見的加速手段有記憶化搜索 (Memoization)（是的，很有動態規劃 (Dynamic Programming, DP) 的味道），也就是說，在每次計算一個 $F(n)$ 時，就把他存入陣列，下次就別再算一遍，這是一個由上而下 (top-down) 的方法。另外，更人類的作法也可以從 $F(0) = 0, F(1) = 1$ 開始由下而上 (bottom-up) 遞推∕迭代 (iterate)。bottom-up 的好處是可以順便計算和。顯然兩者的時間複雜度皆為 $O(n)$。

取模的部份要小心。費氏數列增長很快，有關數論的題目通常會要求對一個很大的質數取模。取模是為惹防止整數溢出，畢竟沒有必要刁難大數。因此，在每個加乘法運算的過程中都應當取模，否則還是有可能溢出，那麼答案就錯誤惹。

附帶一提，上述之所以成立，是由於 $(A + B) \% M = (A \% M + B \% M) \% M$ 且 $(A * B) \% M = (A \% M * B \% M) \% M$。然而，模運算中只有除法沒有分配律，所以才需要所謂「關於模運算的乘法反元素」，簡稱模逆元。

矩陣：$O(\log n)$

又再度離題惹。完成上述操作，你最多還是會得到 \textbf{NA 80\%}。剩下四筆測資該如何通過呢？？此時，我們需要數學的幫忙惹。不知道你是否有印象，徐氏數學第四冊第三章矩陣課後練習或精彩命題圈有遞迴數列與矩陣之結合？？沒錯就是他！！

首先令 $S_n = \sum_{i=0}^{n}{F_i}$，依據定義可得：$$\begin{aligned}
& F_1 = & 1 \enspace\qquad \\
& F_2 = & 2 \enspace\qquad \\
& F_3 = & F_2 \enspace\qquad & + & F_1 \\
& F_4 = & F_3 \enspace\qquad & + & F_2 \\
& F_5 = & F_4 \enspace\qquad & + & F_3 \\
& \enspace\vdots & \vdots\quad\qquad & & \vdots\enspace \\
+) \quad & F_n = & F_{n-1} \qquad & + & \enspace F_{n-2} \\
\hline \\
& S_n = & (S_{n-1} - F_1) & + & S_{n - 2} & + 2
\end{aligned}$$
列出矩陣轉移式：$$
\left(\begin{array}{c}
S_n \\
S_{n-1} \\
1 \\
\end{array}
\right)
= \left(\begin{array}{ccc}
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{array}
\right)
\left(\begin{array}{c}
S_{n-1} \\
S_{n-2} \\
1 \\
\end{array}
\right)
$$
接著利用矩陣快速冪，即可在 $O(\log n)$ 內算出 $S_n$。

最後最後，本題還有更簡單的矩陣解法。對於費氏數列，我們有此性質：$\displaystyle\sum_{i=1}^{n}{F_i} = F_{n+2} - 1$。也就是說，二階矩陣快速冪求 $F_{n+2}-1$ 即可。

費氏數列實在太漂亮惹，還有好多好多性質可以玩呢。

一個有趣的討論

加入討論群組以取得完整解析