determinant_mod.hpp

SECTIONMath INCLUDEnoya/determinant_mod.hpp

在任意合数模数下计算整数矩阵行列式，不依赖每个主元可逆。

\[ \displaystyle \det(A)\bmod m \]

Complexity: Time: O(n^3 log m) arithmetic bit operations. Space: O(n^2).

AC 记录：matrix_det_arbitrary_mod。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n^3 log m) arithmetic bit operations.
/// Space: O(n^2).

#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Determinant of a square integer matrix modulo any positive modulus
/// in O(n^3 log modulus), without requiring modular inverses.
inline std::int64_t determinant_mod(std::vector<std::vector<std::int64_t>> mat,
                                    std::int64_t mod) {
  assert(mod > 0);
  const int n = int(mat.size());
  for (const auto &row : mat) {
    assert(int(row.size()) == n);
  }
  for (auto &row : mat) {
    for (std::int64_t &val : row) {
      val %= mod;
      if (val < 0) {
        val += mod;
      }
    }
  }

  std::int64_t res = 1 % mod;
  for (int col = 0; col < n; col++) {
    int piv = col;
    while (piv < n && mat[piv][col] == 0) {
      piv++;
    }
    if (piv == n) {
      return 0;
    }
    if (piv != col) {
      std::swap(mat[piv], mat[col]);
      res = (mod - res) % mod;
    }

    for (int row = col + 1; row < n; row++) {
      while (mat[row][col] != 0) {
        std::int64_t quo = mat[col][col] / mat[row][col];
        for (int nxt = col; nxt < n; nxt++) {
          __int128 val = mat[col][nxt] - __int128(quo) * mat[row][nxt];
          mat[col][nxt] = std::int64_t(val % mod);
          if (mat[col][nxt] < 0) {
            mat[col][nxt] += mod;
          }
        }
        std::swap(mat[col], mat[row]);
        res = (mod - res) % mod;
      }
    }
    res = std::int64_t(__int128(res) * mat[col][col] % mod);
  }
  return res;
}

} // namespace noya

#ifndef NOYA_DETERMINANT_MOD_HPP
#define NOYA_DETERMINANT_MOD_HPP 1

/// @complexity Time: O(n^3 log m) arithmetic bit operations.
/// Space: O(n^2).

#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Determinant of a square integer matrix modulo any positive modulus
/// in O(n^3 log modulus), without requiring modular inverses.
inline std::int64_t determinant_mod(std::vector<std::vector<std::int64_t>> mat,
                                    std::int64_t mod) {
  assert(mod > 0);
  const int n = int(mat.size());
  for (const auto &row : mat) {
    assert(int(row.size()) == n);
  }
  for (auto &row : mat) {
    for (std::int64_t &val : row) {
      val %= mod;
      if (val < 0) {
        val += mod;
      }
    }
  }

  std::int64_t res = 1 % mod;
  for (int col = 0; col < n; col++) {
    int piv = col;
    while (piv < n && mat[piv][col] == 0) {
      piv++;
    }
    if (piv == n) {
      return 0;
    }
    if (piv != col) {
      std::swap(mat[piv], mat[col]);
      res = (mod - res) % mod;
    }

    for (int row = col + 1; row < n; row++) {
      while (mat[row][col] != 0) {
        std::int64_t quo = mat[col][col] / mat[row][col];
        for (int nxt = col; nxt < n; nxt++) {
          __int128 val = mat[col][nxt] - __int128(quo) * mat[row][nxt];
          mat[col][nxt] = std::int64_t(val % mod);
          if (mat[col][nxt] < 0) {
            mat[col][nxt] += mod;
          }
        }
        std::swap(mat[col], mat[row]);
        res = (mod - res) % mod;
      }
    }
    res = std::int64_t(__int128(res) * mat[col][col] % mod);
  }
  return res;
}

} // namespace noya

#endif // NOYA_DETERMINANT_MOD_HPP

#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>

/// @complexity Time: O(n^3 log m) arithmetic bit operations.
/// Space: O(n^2).

namespace noya {

/// @brief Determinant of a square integer matrix modulo any positive modulus
/// in O(n^3 log modulus), without requiring modular inverses.
inline std::int64_t determinant_mod(std::vector<std::vector<std::int64_t>> mat,
                                    std::int64_t mod) {
  assert(mod > 0);
  const int n = int(mat.size());
  for (const auto &row : mat) {
    assert(int(row.size()) == n);
  }
  for (auto &row : mat) {
    for (std::int64_t &val : row) {
      val %= mod;
      if (val < 0) {
        val += mod;
      }
    }
  }

  std::int64_t res = 1 % mod;
  for (int col = 0; col < n; col++) {
    int piv = col;
    while (piv < n && mat[piv][col] == 0) {
      piv++;
    }
    if (piv == n) {
      return 0;
    }
    if (piv != col) {
      std::swap(mat[piv], mat[col]);
      res = (mod - res) % mod;
    }

    for (int row = col + 1; row < n; row++) {
      while (mat[row][col] != 0) {
        std::int64_t quo = mat[col][col] / mat[row][col];
        for (int nxt = col; nxt < n; nxt++) {
          __int128 val = mat[col][nxt] - __int128(quo) * mat[row][nxt];
          mat[col][nxt] = std::int64_t(val % mod);
          if (mat[col][nxt] < 0) {
            mat[col][nxt] += mod;
          }
        }
        std::swap(mat[col], mat[row]);
        res = (mod - res) % mod;
      }
    }
    res = std::int64_t(__int128(res) * mat[col][col] % mod);
  }
  return res;
}

} // namespace noya