先複習一下矩陣乘法的程式碼
矩陣乘法程式碼：

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        for(int k = 0; k < n; k++){
            ret[i][j] += a[i][k] * b[k][j];
        }
    }
}

例題： 環塗色

題序： 給兩個整數 n、\(\lambda\)， \(\lambda\) 是有多少種顏色，n 是指有幾個頂點圍成的環，問你有幾種塗色方式可以讓環上連在一起的頂點兩兩顏色都不同
範圍：n、\(\lambda \le 10^9\)

n = 3, \(\lambda\) = 3 以上為 6 種塗色方法
(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)

可以發現如果直接推的話，會長左下這樣，但是因為這樣很明顯無法知道最後一個的顏色是什麼，因此這個推法是錯的。

如果要正確推出多邊形有幾種塗色的方式，我們需要知道最後一個跟第一個不一樣的塗法有幾種，因此我們需要記錄每個節點跟第一個一樣及跟第一個不一樣的塗法

\(color[i][0]\) 是指第 \(i\) 個節點與第一個不一樣顏色的話有幾種塗法
\(color[i][1]\) 是指第 \(i\) 個節點與第一個一樣顏色的話有幾種塗法

轉移就會變成以下這樣

color[i][0] = color[i - 1][0] * (\(\lambda\) - 2) + color[i - 1][1] * (\(\lambda\) - 1)
color[i][1] = color[i - 1][0]

而初始值是

color[0][0] = 0
color[0][1] = \(\lambda\) (在第一個的時候顏色會跟自己一樣，因此是 \(\lambda\))

這樣就做完了嗎？
No，他的 k 的範圍最多到 \(10^9\)，除了沒辦法開那麼大的陣列以外，時間也不足以跑完 \(10^9\)，這時候就需要矩陣快速冪加速了。

推導過程：

\({\begin{bmatrix} \lambda - 2 &\lambda - 1\\1&0 \end{bmatrix}}\quad \times \quad \begin{bmatrix} \text{color[0][0]}\\\text{color[0][1]}\end{bmatrix}\)

通過以上的推導，我們就可以對求出的矩陣做快速冪，在 \(O(log_2N)\) 的時間找出我們要的多邊形塗色的答案了，也就是 color[n - 1][0] (第 n 個跟第一個顏色不同的塗法)。

2022 ICPC

題意 : 給你三個數字 \(n\) , \(k\) , \(\lambda\) 分別是中間的多邊形邊數，外擴的四邊形層數，顏色種數，詢問有幾種塗色方案(隔壁不能重複)。

知道了環內的選擇方法後外面就很簡單了，外面第一層就是
\(k_{value} = \frac{1}{\lambda-1}*(\lambda-1)+\frac{\lambda-2}{\lambda-1}*(\lambda-2)\)

然後 \((k-1)*n*k_{value}*color[n-1][0]\) 就會是答案。

2023 TOPC

題意 : 給你 \(a,b,c\) 符合 \(x + \frac 1 x = a\) , 計算出 \(x^b + \frac 1 {x^b} \mod c\)

那很直覺的方法是直接求解 \(x\) 但那樣會有模空間下的問題以及反元素的問題，不過大多數隊伍依然使用此方式。

或是可以觀察求解，那就看一下怎麼做。

矩陣快速冪思路 : 因為我們沒辦法從\(x^b + \frac 1 {x^b}\) 裡面看出任何東西，因此我們把她拆開來看

如果運算 \((x^{b-1} + \frac 1 {x^{b-1}}) * (x + \frac 1 x)\)
就會變成 \((x^{b} + \frac 1 {x^b})+(x^{b-2} + \frac 1 {x^{b-2}})\)
那也就是說 只需要把\((x^{b-1} + \frac 1 {x^{b-1}}) * (x + \frac 1 x)\) 減去 \((x^{b-2} + \frac 1 {x^{b-2}})\) 就會是我們的所求，那這樣就很像是費式數列的感覺了。

接著單看次方項就可以寫出以下式子

\({\begin{bmatrix} a &-1\\1&0 \end{bmatrix}}\quad \times \quad \begin{bmatrix} f(b-1)\\f(b-2)\end{bmatrix} \quad = \quad \begin{bmatrix} f(b)\\f(b-1)\end{bmatrix}\)

然後又因為矩陣的性質

所以又可以寫成這樣

\({\begin{bmatrix} a &-1\\1&0 \end{bmatrix}}^{b-1}\quad \times \quad \begin{bmatrix} f(1)\\f(0)\end{bmatrix} \quad = \quad \begin{bmatrix} f(b)\\f(b-1)\end{bmatrix}\)

又因為我們知道
\(x^1 + \frac 1 {x^1} = a\)
以及
\(x^0 + \frac 1 {x^0} = 2\)
所以又可以寫成這樣
\({\begin{bmatrix} a &-1\\1&0 \end{bmatrix}}^{b-1}\quad \times \quad \begin{bmatrix} a\\2\end{bmatrix} \quad = \quad \begin{bmatrix} f(b)\\f(b-1)\end{bmatrix}\)

最後計算左式即是答案。