矩阵快速幂test版

矩阵快速幂

矩阵快速幂是一种基于矩阵的快速幂算法。与普通的快速幂算法类似，它利用分治法对矩阵进行快速乘法运算，从而在对矩阵进行幂运算时减少计算量。矩阵快速幂的核心思想是通过反复平方来加速矩阵的幂计算，特别适用于需要计算矩阵高次幂的场景。

矩阵乘法

矩阵乘法是矩阵运算中最基本且最重要的运算之一。在进行矩阵乘法时，要求第一个矩阵的列数（column）和第二个矩阵的行数（row）相同。

假设矩阵 ( A ) 为 ( m p ) 的矩阵，矩阵 ( B ) 为 ( p n ) 的矩阵，那么它们的乘积矩阵 ( C ) 为 ( m n ) 的矩阵，其中矩阵 ( C ) 的每个元素 ( C_{ij} ) 是矩阵 ( A ) 的第 ( i ) 行和矩阵 ( B ) 的第 ( j ) 列的点积。具体公式如下：

\[ C_{ij} = \sum_{k=1}^{p} A_{ik} \cdot B_{kj} \]

这意味着要计算矩阵 ( C ) 中的元素 ( C_{ij} )，需要枚举矩阵 ( A ) 的行和矩阵 ( B ) 的列。为了确保矩阵乘法合法，必须满足矩阵 ( A ) 的列数等于矩阵 ( B ) 的行数。

矩阵快速幂算法

矩阵快速幂的思想与普通快速幂相似，即利用分治法将幂次拆分为小的部分进行计算。在矩阵快速幂中，我们对矩阵进行连续平方，从而减少乘法次数，快速得到矩阵的高次幂。

矩阵快速幂的算法流程可以分为以下几个步骤：

1. 初始化矩阵：
   创建一个单位矩阵 res，这是因为任何矩阵与单位矩阵相乘，都会得到原矩阵。

2. 循环迭代：
   对矩阵 ( a ) 进行快速幂计算，逐次平方矩阵并乘以当前的 res，直到幂指数为零。

3. 奇偶判断：
   每次计算时，判断当前幂指数是奇数还是偶数。如果是奇数，先将当前矩阵乘到 res 上，然后将矩阵平方；如果是偶数，直接将矩阵平方。

以下是矩阵快速幂的代码实现：

// 定义矩阵结构体
struct Matrix {
    int mat[MAX][MAX];  // 矩阵的元素
    int m, n;           // 矩阵的行数和列数
};

// 矩阵乘法运算符重载
Matrix operator*(const Matrix& a, const Matrix& b) {
    Matrix c;
    // 初始化结果矩阵c
    for (int i = 0; i < a.m; i++) {
        for (int j = 0; j < b.n; j++) {
            c.mat[i][j] = 0;
            for (int k = 0; k < a.n; k++) {
                c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
            }
        }
    }
    return c; // 返回乘积矩阵
}

// 矩阵快速幂运算符重载
Matrix operator^(Matrix a, long long b) {
    Matrix res, tmp;
    tmp = a;  // tmp初始为a

    // 初始化单位矩阵res
    for (int i = 0; i < a.m; i++) {
        for (int j = 0; j < a.m; j++) {
            if (i == j) res.mat[i][j] = 1; // 单位矩阵
            else res.mat[i][j] = 0;
        }
    }

    // 快速幂计算
    while (b > 0) {
        if (b & 1) res = res * tmp; // 如果当前位为1，乘上当前矩阵
        tmp = tmp * tmp; // tmp平方
        b /= 2; // 右移一位
    }

    return res; // 返回矩阵的最终结果
}