template code library

矩阵乘法类.cpp

using vec = vector<ll>;
using mat = vector<vec>;
mat get_I(int n) {
    mat res(n, vec(n));
    for (int i = 0; i < n; i++)
        res[i][i] = 1;
    return res;
}

mat operator*(const mat &a, const mat &b) {
    mat c(a.size(), vec(b[0].size()));
    for (size_t i = 0; i < a.size(); i++) {
        for (size_t j = 0; j < a[0].size(); j++) {
            if (a[i][j]) { // optimization for sparse matrix
                for (size_t k = 0; k < b[0].size(); k++) {
                    add_mod(c[i][k], a[i][j] * b[j][k] % mod);
                }
            }
        }
    }
    return c;
}

vec operator*(const mat &a, const vec &b) {
    vec c(a.size());
    for (size_t i = 0; i < a.size(); i++) {
        for (size_t j = 0; j < a[0].size(); j++) {
            add_mod(c[i], a[i][j] * b[j] % mod);
        }
    }
    return c;
}

mat pow(mat a, ll n) {
    mat res(a.size(), vec(a[0].size()));
    for (size_t i = 0; i < a.size(); i++) {
        res[i][i] = 1;
    }
    while (n) {
        if (n & 1) {
            res = res * a;
        }
        a = a * a;
        n >>= 1;
    }
    return res;
}