矩乘是一个$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;
}
应用
对于一个递推式，我们可以通过求出其转移矩阵，然后矩阵快速幂来快速求出答案。
而在一些数据结构中也可以用它来较好地维护信息。