以這題當代表，來解釋什麼是矩陣快速冪
首先，什麼是快速冪呢？
在電腦剛發展的時代，CPU跟記憶體容量都很少的情況，為了盡可能提升程式運行速度，科學家們想出各種方法，將某些運算利用"位元"來減少運算的次數，其中之一便是指數運算，我們知道當一個整數 a 連乘自己 b 次之後，可以寫成指數：a^b
，
，看起來指數運算只是連乘多次，應該會很快完成，但如果連乘的不是一個數字而是一個矩陣呢，光是最小的 2x2 方陣自己乘自己，每個元素要2次乘法1次加法一共3次操作，全部4個元素共12次操作，如果需要乘一百萬次矩陣呢，許多模擬運算都需要非常龐大的次數，如果光是基本運算就消耗一堆時間，那整個模擬跑完都不知道過多久了，因此科學家才發明了這個演算法。廢話講完了來講重點
一：快速冪
(一)先看特殊情況：指數的次方是2的次方數，例如 a^64
如果使用一般乘法，就是將 a 乘 64次，而這裡我們換個方式乘，每乘一次後下一次將結果乘以自己：
1. 將 a 乘 a 得到 a^2
2. 將 a^2 乘 a^2 得到 a^4
3. 將 a^4 乘 a^4 得到 a^8
4. 將 a^8 乘 a^8 得到 a^16
5. 將 a^16 乘 a^16 得到 a^32
6. 將 a^32 乘 a^32 得到 a^64
可以看到，只要6次就能得到結果，像這樣翻倍再翻倍的方式，就能在短時間內得到非常龐大的結果，利用這一點，來處理一般情況。
(二)再看一般情況：指數的次方是任意次方，例如 a^107
由特殊情況我們能在短短幾步達成目標，那麼只要將一般情況轉化成多個特殊情況，便能快速得到結果，首先 107 依照2的次方由大到小可以拆成 64、32、8、2、1，也就是 107 = 64+32+8+2+1，
根據指數的運算規則，底數相乘 => 指數相加，因此我們將 a^107 拆成 a^64、a^32、a^8、a^2、a^1，將這些數字相乘就是答案，而這些數字我們利用前面自己乘自己很快就能得到，所以接下來的問題是要如何快速將指數分解成2的次方。
(三) 位元運算
我們知道電腦儲存數字是採用二進位(二進制)，這裡我們將上面的107跟分解的數字用二進位來表示
仔細觀察可以發現，107的二進位當中1的位元，恰好能對應每個2的次方數，快速冪運算正是基於電腦儲存資料的基本機制才能實現，接下來我直接用Java的程式碼來解說
| public static long power_fast(long a, long b) { long ans = 1; while(b>0) { if( (b&1) != 0) ans = ans*a; a = a*a; b>>=1; } return ans; } |
看起來很複雜對吧，我們直接使用範例，計算 3^107 ( 程式碼僅是示範，實際回傳值依輸出結果而定 )
(1) 首先 107>0，進入迴圈，將107與1做"與位元運算"，也就是將兩數依位元逐一比對，若兩個數字對應位元的數字都是 1，就輸出 1，其他輸出 0 (不懂的看上面的表格比對)，運算後結果是 1 != 0，條件 true，
因此答案乘以一個 3，ans = 3^1，然後 a 自己乘自己 = 3^2，b 右移一個位元，此時最右邊的1被捨去，
b 就變成 (0011 0101)二進位，即 b 的值 = 53
(2) 53 > 0，進入迴圈，將53與1做"與位元運算"，運算後結果是 1 != 0，條件 true，因此答案乘以一個 3^2，ans = 3^1 * 3^2，然後 a 自己乘自己 = 3^4，b 右移一個位元變成 (0001 1010)二進位，即 b 的值 = 26
(3) 26 > 0，進入迴圈，將26與1做"與位元運算"，運算後結果是 0 != 0，條件 false，因此跳過 if，然後 a 自己乘自己 = 3^8，b 右移一個位元變成 (0000 1101)二進位，即 b 的值 = 13
(4) 13 > 0，進入迴圈，將13與1做"與位元運算"，運算後結果是 1 != 0，條件 true，因此答案乘以一個3^8，ans = 3^1 * 3^2 * 3^8，然後 a 自己乘自己 = 3^16，b 右移一個位元變成 (0000 0110)二進位，即 b 的值 = 6
(5) 6 > 0，進入迴圈，將6與1做"與位元運算"，運算後結果是 0 != 0，條件 false，因此跳過 if，然後 a 自己乘自己 = 3^32，b 右移一個位元變成 (0000 0011)二進位，即 b 的值 = 3
(6) 3 > 0，進入迴圈，將3與1做"與位元運算"，運算後結果是 1 != 0，條件 true，因此答案乘以一個3^32，ans = 3^1 * 3^2 * 3^8 * 3^32，然後 a 自己乘自己 = 3^64，b 右移一個位元變成 (0000 0001)二進位，即 b 的值 = 1
(7) 1 > 0，進入迴圈，將1與1做"與位元運算"，運算後結果是 1 != 0，條件 true，因此答案乘以一個3^64，ans = 3^1 * 3^2 * 3^8 * 3^32 * 3^64 = 3^107，然後 a 自己乘自己 = 3^128，b 右移一個位元變成 (0000 0000)二進位，即 b 的值 = 0
(8) 0 > 0，條件 false，離開迴圈，答案 ans 回傳，算完了。
我們可以發現，每一次while迴圈都會讓 a 的值翻倍，而每當 b 的最右邊位元是 1，就代表答案需要乘這時候的 a，而一開始的 b，每一個 1 位元都代表一個2的次方，當我們在每次迴圈去確認 b 的位元同時，a 也正在翻倍，利用這個操作技巧就能省下大量的乘法時間，下面是比較直觀的表格
表格的循環次數對應上面的文字版，在第一次進入while 迴圈時，循環次數為 (1)，第二~第四欄為剛進入迴圈的狀態值，第五欄答案是本次迴圈結束時的值。
好了，講完快速冪了，接下來就是搭配矩陣乘法。
二：矩陣快速冪
zerojudge 的 a272 很適合講解矩陣快速冪，我就直接講這題的規律了。
這題是求費式數列的值，其中第一項 F1 = 1，第二項 F2 = 2，然後因為測資會很大，需要取餘數計算( 我前面的文章有講解取餘數 )。我們知道費式數列的規律：Fn+2 = Fn+1 + Fn，我們也知道這個數列有一般通式解，但是一般解涉及根號運算，電腦的浮點數運算有誤差，我們又知道電腦能快速處理簡單的運算，那我們就從遞推式下手。
如果使用一般的遞迴，效率實在太差了，運算過程有一大堆重複答案，如果使用陣列或其他方式儲存答案，這題的測資上限太大，沒有那麼多記憶體，總之先把遞推式變形一下，觀察突破點：
我們把遞推式改成矩陣的形式，其中第一列展開就是原來遞推式，第二列是為了獲得方陣而湊的，接著假設我們要求 F5 的值，依照上面可以展開成：
我特別標註顏色底線，方便讀者比對展開，並且我們令 F0 = 1。
第五項 F5，能從 [1 1,1 0] 矩陣的4次方，與 [1, 1] 相乘得到，那F2147483647 這一項只要自乘 2147483646次就好，看起來很誇張，別忘了我們上面可以利用快速冪的演算法，只要循環30多次就可以得到答案，以下是我Java的程式碼：
| public static int fib_fast(int n) { int[] fib = {1,1}; int[][] pow = {{1,1},{1,0}}; while(n>0) { if( (n&1) != 0) matrix_mul(fib, pow); matrix_pow2(pow); n>>=1; } return fib[0]; } |
最後提醒一點，F1 = 1，如果你直接呼叫方法傳入 n = 1，程式會做一次相乘運算，fib[0] 會等於 2，記得呼叫前 n 要減一。
至於矩陣的乘法，只要設定兩個迴圈，矩陣 [ i ] [ j ] 等於 第一個矩陣第 i 列的元素 乘以 第二個矩陣第 j 列的元素，最後相加，程式寫法如下
| temp[i][j] = (pow[i][0]*pow[0][j] + pow[i][1]*pow[1][j])%MOD; |
以上就是本題的個人思路歷程。
----------------------------------------------------------------------------------------------------------------------------------------
d639這題跟a272類似，只是矩陣變成 3x3，核心演算法一樣，注意初始項、呼叫方法的傳入值、以及矩陣乘法實作即可。
達人
