math/matrix.cpp

Back to top page

• category: math
• View this file on GitHub
  • Last commit date: 2020-09-08 14:43:17+09:00

Code

using Vector = vll;
using Matrix = vvll;

// A * B
Matrix matMul(const Matrix &A, const Matrix &B, const int Mod) {
    Matrix C(A.size(), Vector(B.front().size()));
    rep(i, A.size()) rep(k, B.size()) rep(j, B.front().size()) C[i][j] =
        (C[i][j] + A[i][k] * B[k][j]) % Mod;
    return C;
}

// A^n
Matrix matPow(Matrix A, ll n, const int Mod) {
    Matrix B(A.size(), Vector(A.size()));
    rep(i, A.size()) B[i][i] = 1;
    while (n > 0) {
        if (n & 1)
            B = matMul(B, A, Mod);
        A = matMul(A, A, Mod);
        n >>= 1;
    }
    return B;
}

#line 1 "math/matrix.cpp"
using Vector = vll;
using Matrix = vvll;

// A * B
Matrix matMul(const Matrix &A, const Matrix &B, const int Mod) {
    Matrix C(A.size(), Vector(B.front().size()));
    rep(i, A.size()) rep(k, B.size()) rep(j, B.front().size()) C[i][j] =
        (C[i][j] + A[i][k] * B[k][j]) % Mod;
    return C;
}

// A^n
Matrix matPow(Matrix A, ll n, const int Mod) {
    Matrix B(A.size(), Vector(A.size()));
    rep(i, A.size()) B[i][i] = 1;
    while (n > 0) {
        if (n & 1)
            B = matMul(B, A, Mod);
        A = matMul(A, A, Mod);
        n >>= 1;
    }
    return B;
}

Back to top page