← all categories

Matrix Exponentiation edbe9132

Matrix multiplication and exponentiation mod MOD, for linear recurrences / graph-walk-counting DP sped up via binary exponentiation.

Time: matmul O(n^3); matpow O(n^3 \log b). tested

content/math/matrix-exponentiation.h

typedef vector<vector<ll>> Matrix;

Matrix matmul(Matrix &a, Matrix &b, ll MOD) {
    int n = (int)a.size(), m = (int)b[0].size(), k = (int)b.size();
    Matrix c(n, vector<ll>(m, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int l = 0; l < k; l++)
                c[i][j] = (c[i][j] + a[i][l] * b[l][j]) % MOD;
    return c;
}

Matrix matpow(Matrix a, ll b, ll MOD) {
    int n = (int)a.size();
    Matrix res(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) res[i][i] = 1;
    while (b) {
        if (b & 1) res = matmul(res, a, MOD);
        a = matmul(a, a, MOD);
        b >>= 1;
    }
    return res;
}