数学常用模板——矩阵 高精度

矩阵与矩阵快速幂

struct Matrix {
    int n, m;
    int a[maxn][maxm];
    void clear(int x = 0, int y = 0) {
        n = x, m = y;
        memset(a, 0, sizeof(0));
    }
    void e_mat(int n) {//n阶单位矩阵
        clear(n, n);
        for (int i = 0; i < n; i++) a[i][i] = 1;
    }
    Matrix operator * (const Matrix & b) const{//重载乘法
        Matrix tmp;
        tmp.clear(n, b.m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < b.m; j++)
                for (int k = 0; k < m; k++)
                    tmp.a[i][j] += a[i][k] * b.a[k][j];
        return tmp;
    }
};

Matrix fastMatPow(Matrix a, int k) {
    Matrix res;
    res.e_mat(a.n);
    while (k) {
        if (k & 1) res = res * a;
        k >>= 1;
        a = a * a;
    }
    return res;
}

高精度整数

• 待更新