[模板] 矩阵乘法与矩阵快速幂

矩阵乘法

设 $A$ 为一个 $n \times m$ 的矩阵，$B$ 为一个 $m \times p$ 的矩阵，那么他们的乘积 $AB$ 会是一个 $n \times p$ 矩阵，其中

$$
(AB)_{ij} = \sum_{r=1}^n a_{ir}b_{rj} = a_{i1}b_{1j} + a_{i2}+b_{2j} + \cdots + a_{in}b_{nj}
$$

我们可以通过简单的模拟进行矩阵运算

struct Matrix{
    int n, m;
    long long data[MAXN][MAXN]; 

    Matrix(int _n, int _m){
        n=_n;
        m=_m;
        memset(data, 0, sizeof(data));
    }

    Matrix operator + (Matrix a){
        Matrix ans(n, m);
        for(register int i=1; i<=n; i++){
            for(register int j=1; j<=m; j++){
                ans.data[i][j] = (data[i][j] + a.data[i][j]) % MOD;
            }
        } 

        return ans;
    }

    Matrix operator * (Matrix a){
        Matrix ans(n, a.m);

        for(register int i=1; i<=n; i++){
            for(register int j=1; j<=a.m; j++){
                long long t = 0;

                for(register int k=1; k<=m; k++){
                    t = (t + (data[i][k] * a.data[k][j]) % MOD) % MOD;
                }

                ans.data[i][j] = t;
            }
        }

        return ans;
    }
};

矩阵快速幂

矩阵快速幂和整数快速幂运算原理和方法完全一致

但是整数快速幂是在初始时将ans赋值为 $1$，矩阵快速幂需要将ans矩阵赋值为单位矩阵 $e$

Matrix pow(Matrix a, long long n){
    Matrix ans(a.n, a.n);
    Matrix tmp(a.n, a.n);

    for(register int i=1; i<=a.n; i++){
        ans.data[i][i] = 1;
    }

    memcpy(tmp.data, a.data, sizeof(tmp.data));

    while(n){
        if(n & 1){
            ans = ans * tmp;
        }

        n >>= 1;
        tmp = tmp * tmp;
    }

    return ans;
}