矩乘是一個$n*m$的矩陣乘上一個$m*k$的矩陣，得到一個$n*k$的矩陣。
前言
何謂矩陣乘法？就是矩陣之間的乘法。
矩陣乘法并不是簡單地将兩個矩陣中對應位置上對應元素相乘，而是更為複雜。
矩陣乘法應用廣泛，典例就是優化遞推。
矩陣乘法
首先我們要知道，矩乘是一個\(n*m\)的矩陣乘上一個\(m*k\)的矩陣，得到一個\(n*k\)的矩陣。
由此容易發現，矩乘是不滿足交換律的。
其中，第一個矩陣第\(x\)行的元素，與第二個矩陣第\(y\)列的元素，逐一對應相乘之後再取得的和，就是答案矩陣中第\(x\)和第\(y\)列的值。
用式子表示，就是：
\[res_{x,y}=\sum_{i=1}^mA_{x,i}\cdot B_{i,y}
\]
用代碼表示，就是：（注意，字母表示有點出入）
inline Mat operator * (const Mat& A,const Mat& B)
{
Mat res(A.n,B.m);register int i,j,k;
for(k=1;k<=A.m;++k) for(i=1;i<=A.n;++i)
for(j=1;j<=B.m;++j) res.v[i][j]+=A.v[i][k]*B,v[k][j];
return res;
}
矩陣快速幂
矩陣快速幂與普通的快速幂類似，主要是要注意答案初始化的問題，一般會初始化為左上-右下對角線上都是\(1\)，其他位置都是\(0\)。
做矩陣快速幂的矩陣應該是形如\(n*n\)的矩陣。
代碼實作如下：
inline Mat operator ^ (Mat x,int y)
{
Mat t(x.n,x.n);for(int i=1;i<=t.n;++i) t.v[i][i]=1;
W(y) y&1&&(t=t*x,0),x=x*x,y>>=1;return t;
}
應用
對于一個遞推式，我們可以通過求出其轉移矩陣，然後矩陣快速幂來快速求出答案。
而在一些資料結構中也可以用它來較好地維護資訊。