一个 n 行 m 列的矩阵就是一个类似二维数组的东西。
矩阵乘法
见 B2105 矩阵乘法 - 洛谷，就里写了矩阵乘法的怎么弄，相信大家都会，我就不详讲了。
矩阵快速幂
快速幂都会吧，我们只需要把里面的乘法变成矩阵乘法就行模板题代码大概是这样：
void qpow(int k)
{
while(k!=0)
{
memset(s,0,sizeof(s));
if(k%2==1)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int x=1;x<=n;++x) s[i][j]=(s[i][j]+b[i][x]*a[x][j]%Mod)%Mod;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) b[i][j]=s[i][j];
}
memset(s,0,sizeof(s));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int x=1;x<=n;++x) s[i][j]=(s[i][j]+a[i][x]*a[x][j]%Mod)%Mod;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) a[i][j]=s[i][j];
k/=2;
}
}
矩阵快速幂有什么用呢？
矩阵快速幂加速地推
P1962 斐波那契数列 - 洛谷
如果我们绘制一个转移矩阵从 F_{i-1} 到 F_i 只需要乘上转移矩阵后，在某个固定位置是答案，就可以用矩阵快速幂做了。
那么转移矩阵怎么绘制呢。
首先我们了解一下单位矩阵 I 。
他大概长这样：
\begin{bmatrix}
1&0 &0 &0 &0 \\
0&1 &0 &0 &0 \\
0&0 &1 &0 &0 \\
0&0 &0 &1 &0 \\
0&0 &0 &0 &1
\end{bmatrix}
转移矩阵就是上面一排是系数，下面左边是一个单位矩阵，右边全是 0 ，向斐波那契额的转移矩阵就是：
\begin{bmatrix}
1&1\\
1&0\\
\end{bmatrix}
那么就可以做出这题了。
矩阵快速幂求路径数量
给一张图让你求这张图，两点互相的长度 k 的路径数量。
首先弄一个邻接矩阵，然后算出这个矩阵的 k 次方，这是这个矩阵 a_{i,j} 就是 i 到 j 的路径条数。
具体证明可以看一下，老师的课件。
下一篇讲高斯消元