行列式(Matrix Determinant)
(math/matrix_determinant.cpp)

• View this file on GitHub
• Last update: 2026-03-14 20:56:35+09:00

説明

modint 行列の行列式を計算する。 Gaussian elimination を使い、計算量は $O(N^3)$。

できること

• mint matrix_determinant(vector<vector<mint>> A) 正方行列 A の行列式を返す。特異行列なら 0

使い方

A を vector<vector<mint>> で渡す。 入力は値渡しなので、呼び出し元の行列は壊れない。

Depends on

• modint(固定MOD) (util/modint.cpp)

Verified with

• test/yosupo_matrix_det.test.cpp

Code

#include "../util/modint.cpp"

mint matrix_determinant(vector<vector<mint>> A) {
    int n = A.size();
    mint det = 1;
    for (int col = 0; col < n; ++col) {
        int pivot = col;
        while (pivot < n && !A[pivot][col].val) ++pivot;
        if (pivot == n) return 0;
        if (pivot != col) {
            swap(A[pivot], A[col]);
            det = -det;
        }
        det *= A[col][col];
        mint inv = A[col][col].inv();
        for (int row = col + 1; row < n; ++row) {
            if (!A[row][col].val) continue;
            mint coeff = A[row][col] * inv;
            for (int j = col; j < n; ++j) {
                A[row][j] -= A[col][j] * coeff;
            }
        }
    }
    return det;
}

/**
 * @brief 行列式(Matrix Determinant)
 */

#line 1 "util/modint.cpp"



template <uint Mod>
struct modint {
    uint val;
public:
    static modint raw(int v) { modint x; x.val = v; return x; }
    static constexpr uint get_mod() { return Mod; }
    static constexpr uint M() { return Mod; }
    modint() : val(0) {}
    template <class T>
    modint(T v) { ll x = (ll)(v % (ll)(Mod)); if (x < 0) x += Mod; val = uint(x); }
    modint(bool v) { val = ((unsigned int)(v) % Mod); }
    uint &value() noexcept { return val; }
    const uint &value() const noexcept { return val; }
    modint& operator++() { val++; if (val == Mod) val = 0; return *this; }
    modint& operator--() { if (val == 0) val = Mod; val--; return *this; }
    modint operator++(int) { modint result = *this; ++*this; return result; }
    modint operator--(int) { modint result = *this; --*this; return result; }
    modint& operator+=(const modint& b) { val += b.val; if (val >= Mod) val -= Mod; return *this; }
    modint& operator-=(const modint& b) { val -= b.val; if (val >= Mod) val += Mod; return *this; }
    modint& operator*=(const modint& b) { ull z = val; z *= b.val; val = (uint)(z % Mod); return *this; }
    modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
    modint inv() const { return pow(Mod - 2); }
    friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
    friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
    friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
    friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
    friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
    friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD>;
#define FIRIEXP_LIBRARY_MINT_ALIAS_DEFINED

/**
 * @brief modint(固定MOD)
 */


#line 2 "math/matrix_determinant.cpp"

mint matrix_determinant(vector<vector<mint>> A) {
    int n = A.size();
    mint det = 1;
    for (int col = 0; col < n; ++col) {
        int pivot = col;
        while (pivot < n && !A[pivot][col].val) ++pivot;
        if (pivot == n) return 0;
        if (pivot != col) {
            swap(A[pivot], A[col]);
            det = -det;
        }
        det *= A[col][col];
        mint inv = A[col][col].inv();
        for (int row = col + 1; row < n; ++row) {
            if (!A[row][col].val) continue;
            mint coeff = A[row][col] * inv;
            for (int j = col; j < n; ++j) {
                A[row][j] -= A[col][j] * coeff;
            }
        }
    }
    return det;
}

/**
 * @brief 行列式(Matrix Determinant)
 */

Back to top page