模板

struct Matrix {
    ll mat[N][N];
};
// a: n*n b: n*n
Matrix mul_matrix(Matrix a, Matrix b, int n, ll m) {
    Matrix res;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            res.mat[i][j] = 0;
            for (int k = 0; k < n; k++) {
                res.mat[i][j] += a.mat[i][k] * b.mat[k][j] % m;
                res.mat[i][j] %= m;
            }
        }
    }
    return res;
}
// a^p
Matrix pow_matrix(Matrix a, ll p, int n, ll m) {
    Matrix res;
    // 单位矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            res.mat[i][j] = (i == j ? 1 : 0);
        }
    }
    while (p != 0) {
        if (p & 1)
            res = mul_matrix(a, res, n, m);
        a = mul_matrix(a, a, n, m);
        p >>= 1;
    }
    return res;
}

大矩阵作为函数参数且以值传递会发生段错误。

一种大矩阵不会段错误的实现方式。

#define N 505
#define MOD 998244353

struct Matrix {
    int mat[N][N];
    int n;
    Matrix(int n) : n(n) { memset(mat, 0, sizeof(mat)); }
    inline void operator*=(const Matrix& o) {
        int ans[n][n] = {};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j])
                    for (int k = 0; k < n; k++)
                        ans[i][k] =
                            (ans[i][k] + (long long)(mat[i][j]) * o.mat[j][k]) %
                            MOD;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                mat[i][j] = ans[i][j];
    }
    void print() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << mat[i][j] << " ";
            }
            cout << "\\n";
        }
    }
};
/*
    // a *= b^n
    for (; n; n >>= 1, b *= b)
        if (n & 1)
            a *= b;
    a.print();
*/

应用场景

常系数的递推式

已知$f_0, f_1,\cdots,f_{k-1}$

$f_i= c_0+c_1f_{i-1}+c_2f_{i-2}+\cdots+c_kf_{i-k}, i\ge k$

二维状态转移只依赖前一维度

$f_{p,i} = \sum \limits_{j=0}^{n-1}f_{p-1, j}*c_{i,j}$

设置一个$n\times n$的转移矩阵A。设置元素$A_{i,j}$为前一状态$f_{p-1,i}$向当前状态$f_{p,j}$转移的贡献$c_{i,j}$