小花生

study & life record.

矩阵快速幂

发表于 分类于 ，

介绍矩阵快速幂、模板整理。

矩阵乘 + 快速幂 = 矩阵快速幂。

常用于构建矩阵后，加速递推。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct Matrix{
    int n, m;
    vector<vector<int>>a;
    Matrix(int n, int m) : n(n), m(m), a(n, vector<int>(m)) {}

    // 模意义下的矩阵乘
    Matrix operator* (const Matrix &o){
        Matrix c(n, o.m);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < o.m; j++){
                for(int k = 0; k < m; k++){
                    c.a[i][j] += a[i][k] * o.a[k][j];
                    c.a[i][j] %= mod;
                }
            }
        }
        return c;
    }
};

Matrix Mqmi(Matrix M, int k){
    Matrix res(M.n, M.n);
    for(int i = 0; i < M.n; i++) res.a[i][i] = 1;
    while(k){
        if(k & 1) res = res * M;
        M = M * M;
        k >>= 1;
    }
    return res;
}

题例

P1349 广义斐波那契数列 - 洛谷。