模板 | 矩阵快速幂
基础知识储备
1. 矩阵的定义：
2. N阶方阵：
行数与列数相同（均为n）的矩阵，叫做n阶方阵。如下图所示就是一个的方阵：
3. 行矩阵（行向量）：
只有一行的矩阵，下图就是一个行矩阵：
4. 列矩阵（列向量）：
只有一列的矩阵，下图就是一个列矩阵：
5. 同型矩阵：
设先有矩阵A和矩阵B，矩阵A的行数与列数和矩阵B的相同，则矩阵A、B是同型矩阵。
6. 单位矩阵：（符号：E or I）
在矩阵的乘法中，有一种矩阵起着特殊的作用，如同数的乘法中的1,这种矩阵被称为单位矩阵。它是个方阵，从左上角到右下角的对角线（称为主对角线）上的元素均为1。除此以外全都为0。如下图所示是一个3阶的单位矩阵。
7. 矩阵的相关运算：
7.1 矩阵加法：（同型矩阵）
7.2 矩阵乘法：（
型 
型 * 
型）
PS：更多知识可以参考线性代数的相关知识
矩阵快速幂：
矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素算法的的时间复杂度，降到
。
这里先对原理（主要运用了矩阵乘法的结合律）做下简单形象的介绍：
一般求一个矩阵的n次方，我们会通过连乘n-1次来得到它的n次幂。（朴素算法）
但做下简单的改进就能减少连乘的次数，方法如下：
把n个矩阵进行两两分组，比如：
这样变的好处是，你只需要计算一次
，然后将结果
，即
。算一下发现这次一共乘了3次，少于原来的5次。
我们还可以取A^3作为一个基本单位。原理都一样：利用矩阵乘法的结合律，来减少重复计算的次数。
以上都是取一个具体的数来作为最小单位的长度，这样做虽然能够改进效率，但缺陷也是很明显的，取个极限的例子（可能有点不恰当，但基本能说明问题），当n无穷大的时候，你现在所取的长度其实和1没什么区别。
所以就需要我们找到一种与n增长速度”相适应“的”单位长度“，那这个长度到底怎么去取呢？？？
这点是我们要思考的问题。
既然要减少重复计算，那么就要充分利用现有的计算结果！
怎么充分利用计算结果呢？？？这里考虑二分的思想。。
我们首先要认识到这一点：任何一个整数N，都能用二进制来表示。（又是二进制，可见其重要性）
既然如此，那么我们可以将指数用二进制表示。比如
，显然采取这样的方式计算时因子数将是
级别的（原来的因子数是n）。
不仅这样，因子间也是存在某种联系的，比如
能通过
得到，
又能通过
得到，这点也充分利用了现有的结果作为有利条件。
下面给出相关代码：
结构体（存放矩阵）：
// 将二维数组放入一个结构体中
struct Mat
{
int mat[105][105];// 具体二维数组大小视具体情况而定
};
矩阵乘法：（A*B）
// 重载*运算符
// 矩阵A、B均为n阶方阵
Mat operator*(Mat A,Mat B)
{
Mat temp;
//memset(temp.mat,0,sizeof(temp.mat));// 将矩阵置0【零矩阵】
for(int i =0 ; i < n ; i++)
{
for(int j = 0 ; j < n ;j++)
{
temp.mat[i][j]=0;// 在这里将矩阵temp置零【零矩阵】
for(int k = 0 ;k < n ;k++)
{
temp.mat[i][j] = (temp.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
}
}
}
return temp;// 返回矩阵A*B的结果
}
矩阵快速幂：（A^k）
// 重载^运算符
Mat operator^(Mat A, k)
Mat base;
// 将矩阵base置为单位矩阵【单位矩阵】
for(int i=0;i<n;i++) base.mat[i][i]=1;
// 快速幂【核心代码】
while(k)
{
if(k & 1) base = base * A;
A = A * A;
k = k >> 1;
}
return base;
}
PS：矩阵快速幂核心代码与整数的快速幂非常相似
写在最后：
资料参考：
