矩陣 並不想扯什麼高端線代的內容因為我也不會 定義 由$n \times m$個數$a_{ij}$排成的$n$行$m$列的數表稱為$n$行$m$列的矩陣，簡稱$n \times m$矩陣。 $$A =\begin{bmatrix}a_{11} & a_{12} & \dots a_{1m} \\ a ...
矩陣
並不想扯什麼高端線代的內容因為我也不會
定義
由$n \times m$個數$a_{ij}$排成的$n$行$m$列的數表稱為$n$行$m$列的矩陣，簡稱$n \times m$矩陣。
$$
A =
\begin{bmatrix}
a_{11} & a_{12} & \dots a_{1m} \\
a_{21}, & \dots & \dots \\
a_{31}, & \dots & \dots \\
a_{41} & \dots & a_{nm}
\end{bmatrix}
$$
運算
這裡只講加法減法和乘法，其他的例如矩陣求逆等與本文內容出入較大，有興趣的可以自己學習
加法
註意，只有行列均相同的矩陣才有加法！
運算也比較簡單，把對應位置的數相加得到一個新的矩陣，即為答案
例如
$$
\begin{bmatrix} 1 & 1 & 2 \\ 1 & 0 & 1 \end{bmatrix}
+
\begin{bmatrix} 2 & 3 & 3 \\ 3 & 3 & 2 \end{bmatrix}
=
\begin{bmatrix} 3 & 4 & 5 \\ 4 & 3 & 3 \end{bmatrix}
$$
加法滿足以下運算律
$A + B = B + A$
$(A + B) + C = A + (B + C)$
減法
與加法同理。
乘法
這才是重點！！
兩個矩陣能進行乘法的前提條件是：一個矩陣的行數等於另一個矩陣的列數
形式化的來說，若$A$是$i \times k$的矩陣，那麼$B$必須是$k \times j$的矩陣！
他們相乘得到的$C$是$i \times j$的矩陣
其中$C_{ij} = \sum_{i = 1}^n A_{ik} * B_{kj}$
比如
$$
\begin{bmatrix} 1 & 2\\ 2 & 3 \end{bmatrix}
\times
\begin{bmatrix} 2 & 4 & 5 \\ 3 & 4 & 3 \end{bmatrix}
=
\begin{bmatrix} 8 & 12 & 11 \\ 13 & 20 & 19 \end{bmatrix}
$$
乘法滿足結合律，左分配律，右分配律，即
$(A \times B) \times C = A \times (B \times C)$
$(A + B) \times C = A \times C + B \times C$
$C(A + B) = C \times A + C \times B$
千萬註意！矩陣乘法不滿足交換律！(很多情況下交換之後都不能相乘)
矩陣快速冪
因為矩陣有結合律，因此我們可以把整數的快速冪推廣的矩陣上面
同樣是利用二進位倍增的思想，不難得到以下代碼
其中的base，代表的是單位矩陣，也就是除了對角線全為$1$，其他位置都為$0$的矩陣，可以證明任意矩陣乘單位矩陣都等於自身
顯然矩陣快速冪的複雜度為$O(n^3 log k)$
#include<cstdio> #define LL long long using namespace std; const int mod = 1e9 + 7; int N; LL K; struct Matrix { int m[101][101]; Matrix operator * (const Matrix &rhs) const { Matrix ans = {}; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) (ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod; return ans; } }; Matrix fastpow(Matrix a, LL p) { Matrix base; for(int i = 1; i <= N; i++) base.m[i][i] = 1;//構造單位矩陣 while(p) { if(p & 1) base = base * a; a = a * a; p >>= 1; } return base; } int main() { scanf("%d %lld", &N, &K); Matrix a; for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) scanf("%d", &a.m[i][j]); a = fastpow(a, K); for(int i = 1; i <= N; i++, puts("")) for(int j = 1; j <= N; j++) printf("%d ", a.m[i][j]); return 0; }
應用
矩陣快速冪最常見的應用就是優化遞推啦
還是從最常見的斐波那契數列說起吧。
眾周所知，斐波那契數列的遞推公式為$$f_{n} = f_{n - 1} + f_{n - 2}, f_1 = 1, f_2 = 1$$
一般來說，這種看起來長得很萌簡單，只與自身的函數值有關(可能帶幾個常數)的式子，一般都可以用矩陣快速冪來加速。
當然，如果你想找刺激，可以學一下這玩意兒
矩陣快速冪具體是怎麼加速遞推的呢？
首先我們把斐波那契數列寫成矩陣的形式，因為$f_n$的取值與$f_{n - 1}, f_{n - 2}$這兩項有關，因此我們需要同時保留這兩項的值，我們不難得到一個$2 \times 1$的矩陣
$$
\begin{bmatrix}
f_{n} \\
f_{n - 1}
\end{bmatrix}
$$
現在我們要進行遞推，也就是得到這樣一個矩陣
$$
\begin{bmatrix}
f_{n + 1} \\
f_{n}
\end{bmatrix}
$$
展開
$$
\begin{bmatrix}
f_{n} + f_{n - 1} \\
f_{n}
\end{bmatrix}
$$
觀察一下，上面的一項需要用到$f_{n}$和$f_{n - 1}$，下麵的一項只需要用到$f_n$
同時結合上面的矩陣乘法的定義，我們不難得到一個轉移矩陣
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}
\begin{bmatrix} f_{n} \\ f_{n - 1}\\ \end{bmatrix}
=
\begin{bmatrix} f_{n} + f_{n - 1} \\ f_{n}\\ \end{bmatrix}
$$
這樣我們乘一次即可遞推到下一項。
但是這樣好像並沒有什麼卵用啊，複雜度上還多了個矩陣相乘
嘿嘿
不要忘了，我們前面可以講過矩陣有結合律的！
這樣的話我們只需要把轉移矩陣自乘$n - 1$次，然後再與初始矩陣相乘，就能得到答案矩陣啦！
// luogu-judger-enable-o2 #include<cstdio> #include<cstring> #define LL long long using namespace std; const int mod = 1e9 + 7; LL K; struct Matrix { int m[101][101], N; Matrix() { memset(m, 0, sizeof(m)); N = 2; } Matrix operator * (const Matrix &rhs) const { Matrix ans; for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) (ans.m[i][j] += 1ll * m[i][k] * rhs.m[k][j] % mod) %= mod; return ans; } }; Matrix fastpow(Matrix a, LL p) { Matrix base; for(int i = 1; i <= base.N; i++) base.m[i][i] = 1;//鏋勯€犲崟浣嶇煩闃? while(p) { if(p & 1) base = base * a; a = a * a; p >>= 1; } return base; } int main() { scanf("%lld", &K); Matrix a; a.m[1][1] = 1; a.m[1][2] = 1; a.m[2][1] = 1; a.m[2][2] = 0; a = fastpow(a, K - 1); printf("%d", a.m[1][1]); return 0; }代碼
