#教學教學文(二) 程式設計上的矩陣快速冪 | 程式設計板

先道個歉啦這次的教學文拖了5天才po@@ 好啦那開始了這次要講的是矩陣快速冪！關於快速冪的部分可以先去看以前的教學文哦至於矩陣的乘法以及相關特性麻煩還不知道的各位可以去翻數學課本 (應該是高二的課本) 或是維基百科也可以 https://zh.wikipedia.org/wiki/%E7%9F%A9%E9%99%A3%E4%B9%98%E6%B3%95 在這裡就不再重複說明了接下來就是正文啦應該會有人好奇吧「啊考試那種考矩陣A^100的題目用矩陣快速冪也沒用那為什麼我們需要矩陣快速冪？」是誰說沒有的我之前數學段考想不出來就真的給他快速冪花了好幾分鐘但是有算對啊！沒沒事那時候的我怪怪的首先我們先來看一個大家很熟悉的東西──費氏數列 1 1 2 3 5 8 13 21 …… 矩陣快速冪和費氏數列有什麼關聯呢？最一般求費氏數列第n項的做法就是直接 a[0]=1; a[1]=1; for (int i=2; i<=n; i++) a[i]=a[i-1]+a[i-2]; 這麼做的時間複雜度是O(n) 遇到求第10^18項mod 10^9+7這種題目就GG了 (我猜會有人好奇哪個題目這麼變態請參考2016年NPSC的pF.無限兔子問題一個我想出難的部份結果漏掉簡單的部分最後TLE的題目= = 那題和費氏數列有關解法也是矩陣快速冪不過有點麻煩就是了) 那麼該怎麼加速呢？這時候矩陣乘法就派上用場了！註：這裡先定義 F[i]表示費氏數列第i項矩陣A表示下面這個2*2的矩陣 1 1 1 0 矩陣X[i]表示下面這個2*1的矩陣 F[i+1] F[i] (如果不習慣我用字母表示矩陣的話可以自己在紙上把矩陣再寫一遍哦我覺得看過原本寫成矩陣的樣子可以幫助自己的記憶但是在這裡寫成矩陣排版會跑掉所以麻煩大家自己動動手了) 如果把矩陣A乘上X[n] 會變成什麼呢？新的2*1矩陣下面那個數字是1*F[i+1]=F[i+1] 而上面那個數字呢？發現了嗎？ 1*F[i+1]+1*F[i]=F[i+2] 也就是說 A乘上X[n]會得到X[n+1]！「啊用矩陣去算還不是要乘n-1次還比用加的更慢齁」嘿！接下來就可以用快速冪加速啦如果要求第n項就是A*(……A*(A*(A*X[0]))……)=X[n] (前面共n個A) 根據矩陣乘法的性質上面的可以改寫成 (A*A*……*A)*X[0] (一樣是n個A) =A^n*X[0] 而A^n就可以用之前說過的快速冪去算啦只是把數字的乘法改成矩陣乘法而已 Code： http://codepad.org/o2QPKVoN (當然啦一般項求解也是個方法但是電腦處理根號5會有浮點數誤差而且每出現一種新的數列就要重新推一次一般項不是很實用所以就不列在這裡了) 好啦這次的教學文就到這邊了有問題都歡迎提出來討論然後如果我文章中有可以改進的地方也麻煩跟我說一下哦！下一篇：組合數