模板 | 矩阵快速幂

基础知识储备

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：矩阵快速幂核心代码与整数的快速幂非常相似

写在最后：

资料参考：

• 博客：https://www.cnblogs.com/cmmdc/p/6936196.html
• 博客：https://www.cnblogs.com/luyingfeng/p/3674425.html