因為最近在解 Leetcode 的 91. Decode Ways，
要用到 Fibonacci sequence 來解，就我所知上次解 70. Climbing Stairs 的時候，
用 recursive 求解 Fibonacci sequence 的時候會 TLE。
（所以我就偷懶跑去用 Python3 解大數）
這次再遇到應該是要進步了xDDD
正文開始：
Fibonacci sequence 會長這個樣子：
根據基本定義，第 N 個 Fibonacci value 等於前兩個 Fibonacci value 相加，
我們便可以得到公式：
得到公式以後把它擴展成 轉移矩陣 M 的形式，
因為我們把前兩項當作初始值，所以 轉移矩陣 M 的指數會減二：
所以我們現在只要計算 M 的 (n-2) 次方就能得到第 N 個 Fibonacci value。
（左上角的 M00 會等於 第N個 Fibonacci value）
此時的計算複雜度為：O(n)
以第 45 個 value 值來比較，此方法已經比遞迴快很多了xD
但是我還要教你一個威力加強版外掛：平方求冪
（左岸又稱快速冪 or double-and-add）
我們在這裡要用平方求冪去優化轉移矩陣 M。
平方求冪的想法是把任何高階指數都化為與指數二有關的指數和，
屁話一堆直接看數學比較快：
如果你說 n 是 odd 怎麼辦？
啊不簡單？直接減一再乘回去R~：
這樣的好處是能大大的減少計算量，數學意義上來說是二分搜尋法，
以找 n = 16 舉例，
沒有平方求冪的版本會很老實地計算十五次乘法，
而有平方求冪外掛的版本會跳著算：
像是圖中有幾個節點，就計算幾次，
每次都是跟自己相乘，所以實際上只要算黃色螢光筆那條路徑，
不必考慮其他條黑色路徑。
由此可以 16 = 2^4，所以有 4 個節點，只需計算 4次。
此時又可推導出 計算複雜度為：O(logn)
（log 以 2 為底。）
用 C++ 實現的程式碼我放在這裡
有興趣的可以直接拿來用，不用再造車輪了xD
感謝各位