linalg/det.hpp

• View this file on GitHub
• Last update: 2023-10-24 14:53:54+09:00
• Include: #include "linalg/det.hpp"

Depends on

• mod/barrett.hpp

Required by

• graph/count/BEST.hpp
• graph/count/count_spanning_tree.hpp
• random/random_matrix.hpp

Verified with

• test/1_mytest/blackbox_solve_linear.test.cpp
• test/2_library_checker/graph/count_spanning_tree_directed_dense.test.cpp
• test/2_library_checker/graph/count_spanning_tree_directed_sparse.test.cpp
• test/2_library_checker/graph/count_spanning_tree_undirected_dense.test.cpp
• test/2_library_checker/graph/count_spanning_tree_undirected_sparse.test.cpp
• test/2_library_checker/graph/counting_eulerian_dense.test.cpp
• test/2_library_checker/graph/counting_eulerian_sparse.test.cpp
• test/2_library_checker/linear_algebra/det_mod.test.cpp
• test/2_library_checker/linear_algebra/matrix_det.test.cpp
• test/3_yukicoder/1303.test.cpp

Code

#include "mod/barrett.hpp"


int det_mod(vvc<int> A, int mod) {
  Barrett bt(mod);
  const int n = len(A);
  ll det = 1;
  FOR(i, n) {
    FOR(j, i, n) {
      if (A[j][i] == 0) continue;
      if (i != j) { swap(A[i], A[j]), det = mod - det; }
      break;
    }
    FOR(j, i + 1, n) {
      while (A[i][i] != 0) {
        ll c = mod - A[j][i] / A[i][i];
        FOR_R(k, i, n) { A[j][k] = bt.modulo(A[j][k] + A[i][k] * c); }
        swap(A[i], A[j]), det = mod - det;
      }
      swap(A[i], A[j]), det = mod - det;
    }
  }
  FOR(i, n) det = bt.mul(det, A[i][i]);
  return det % mod;
}

template <typename mint>
mint det(vvc<mint>& A) {
  const int n = len(A);
  vv(int, B, n, n);
  FOR(i, n) FOR(j, n) B[i][j] = A[i][j].val;
  return det_mod(B, mint::get_mod());
}

#line 2 "mod/barrett.hpp"

// https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp
struct Barrett {
  u32 m;
  u64 im;
  explicit Barrett(u32 m = 1) : m(m), im(u64(-1) / m + 1) {}
  u32 umod() const { return m; }
  u32 modulo(u64 z) {
    if (m == 1) return 0;
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    return (z - y + (z < y ? m : 0));
  }
  u64 floor(u64 z) {
    if (m == 1) return z;
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    return (z < y ? x - 1 : x);
  }
  pair<u64, u32> divmod(u64 z) {
    if (m == 1) return {z, 0};
    u64 x = (u64)(((unsigned __int128)(z)*im) >> 64);
    u64 y = x * m;
    if (z < y) return {x - 1, z - y + m};
    return {x, z - y};
  }
  u32 mul(u32 a, u32 b) { return modulo(u64(a) * b); }
};

struct Barrett_64 {
  u128 mod, mh, ml;

  explicit Barrett_64(u64 mod = 1) : mod(mod) {
    u128 m = u128(-1) / mod;
    if (m * mod + mod == u128(0)) ++m;
    mh = m >> 64;
    ml = m & u64(-1);
  }

  u64 umod() const { return mod; }

  u64 modulo(u128 x) {
    u128 z = (x & u64(-1)) * ml;
    z = (x & u64(-1)) * mh + (x >> 64) * ml + (z >> 64);
    z = (x >> 64) * mh + (z >> 64);
    x -= z * mod;
    return x < mod ? x : x - mod;
  }

  u64 mul(u64 a, u64 b) { return modulo(u128(a) * b); }
};
#line 2 "linalg/det.hpp"

int det_mod(vvc<int> A, int mod) {
  Barrett bt(mod);
  const int n = len(A);
  ll det = 1;
  FOR(i, n) {
    FOR(j, i, n) {
      if (A[j][i] == 0) continue;
      if (i != j) { swap(A[i], A[j]), det = mod - det; }
      break;
    }
    FOR(j, i + 1, n) {
      while (A[i][i] != 0) {
        ll c = mod - A[j][i] / A[i][i];
        FOR_R(k, i, n) { A[j][k] = bt.modulo(A[j][k] + A[i][k] * c); }
        swap(A[i], A[j]), det = mod - det;
      }
      swap(A[i], A[j]), det = mod - det;
    }
  }
  FOR(i, n) det = bt.mul(det, A[i][i]);
  return det % mod;
}

template <typename mint>
mint det(vvc<mint>& A) {
  const int n = len(A);
  vv(int, B, n, n);
  FOR(i, n) FOR(j, n) B[i][j] = A[i][j].val;
  return det_mod(B, mint::get_mod());
}

Back to top page