determinant_mod.hpp¶
在任意合数模数下计算整数矩阵行列式，不依赖每个主元可逆。
\[
\displaystyle \det(A)\bmod m
\]
Complexity: Time: \(O(n^{3} + n^{2} \log (m + 1))\) fixed-width arithmetic operations. Space: \(O(n^{2})\).
AC 记录：matrix_det_arbitrary_mod。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n^3 + n^2 log(m + 1)) fixed-width arithmetic 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
/// using Euclidean row operations, 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 ([[maybe_unused]] const auto &row : mat) {
assert(int(row.size()) == n);
}
if (mod == 1) {
return 0;
}
bool negative = false;
for (auto &row : mat) {
for (std::int64_t &val : row) {
if (val < 0 || val >= mod) {
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]);
negative = !negative;
}
for (int row = col + 1; row < n; row++) {
while (mat[row][col] != 0) {
std::int64_t quo = mat[col][col] / mat[row][col];
// The leading entry is an ordinary Euclidean remainder in [0, mod).
mat[col][col] %= mat[row][col];
if (quo != 0) {
for (int nxt = col + 1; nxt < n; nxt++) {
std::int64_t product;
if (quo == 1) {
product = mat[row][nxt];
} else if (mod <= (std::int64_t(1) << 32)) {
// Both factors are below mod, so their product fits uint64_t.
product = std::int64_t(std::uint64_t(quo) *
std::uint64_t(mat[row][nxt]) %
std::uint64_t(mod));
} else {
product = std::int64_t(static_cast<unsigned __int128>(quo) *
mat[row][nxt] % mod);
}
mat[col][nxt] -= product;
if (mat[col][nxt] < 0) {
mat[col][nxt] += mod;
}
}
}
std::swap(mat[col], mat[row]);
negative = !negative;
}
}
res = std::int64_t(__int128(res) * mat[col][col] % mod);
if (res == 0) {
return 0;
}
}
return negative ? mod - res : res;
}
} // namespace noya
// NOYA_DETERMINANT_MOD_HPP
#ifndef NOYA_DETERMINANT_MOD_HPP
#define NOYA_DETERMINANT_MOD_HPP 1
/// @complexity Time: O(n^3 + n^2 log(m + 1)) fixed-width arithmetic 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
/// using Euclidean row operations, 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 ([[maybe_unused]] const auto &row : mat) {
assert(int(row.size()) == n);
}
if (mod == 1) {
return 0;
}
bool negative = false;
for (auto &row : mat) {
for (std::int64_t &val : row) {
if (val < 0 || val >= mod) {
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]);
negative = !negative;
}
for (int row = col + 1; row < n; row++) {
while (mat[row][col] != 0) {
std::int64_t quo = mat[col][col] / mat[row][col];
// The leading entry is an ordinary Euclidean remainder in [0, mod).
mat[col][col] %= mat[row][col];
if (quo != 0) {
for (int nxt = col + 1; nxt < n; nxt++) {
std::int64_t product;
if (quo == 1) {
product = mat[row][nxt];
} else if (mod <= (std::int64_t(1) << 32)) {
// Both factors are below mod, so their product fits uint64_t.
product = std::int64_t(std::uint64_t(quo) *
std::uint64_t(mat[row][nxt]) %
std::uint64_t(mod));
} else {
product = std::int64_t(static_cast<unsigned __int128>(quo) *
mat[row][nxt] % mod);
}
mat[col][nxt] -= product;
if (mat[col][nxt] < 0) {
mat[col][nxt] += mod;
}
}
}
std::swap(mat[col], mat[row]);
negative = !negative;
}
}
res = std::int64_t(__int128(res) * mat[col][col] % mod);
if (res == 0) {
return 0;
}
}
return negative ? mod - res : res;
}
} // namespace noya
#endif // NOYA_DETERMINANT_MOD_HPP
/// @complexity Time: O(n^3 + n^2 log(m + 1)) fixed-width arithmetic 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
/// using Euclidean row operations, 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 ([[maybe_unused]] const auto &row : mat) {
assert(int(row.size()) == n);
}
if (mod == 1) {
return 0;
}
bool negative = false;
for (auto &row : mat) {
for (std::int64_t &val : row) {
if (val < 0 || val >= mod) {
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]);
negative = !negative;
}
for (int row = col + 1; row < n; row++) {
while (mat[row][col] != 0) {
std::int64_t quo = mat[col][col] / mat[row][col];
// The leading entry is an ordinary Euclidean remainder in [0, mod).
mat[col][col] %= mat[row][col];
if (quo != 0) {
for (int nxt = col + 1; nxt < n; nxt++) {
std::int64_t product;
if (quo == 1) {
product = mat[row][nxt];
} else if (mod <= (std::int64_t(1) << 32)) {
// Both factors are below mod, so their product fits uint64_t.
product = std::int64_t(std::uint64_t(quo) *
std::uint64_t(mat[row][nxt]) %
std::uint64_t(mod));
} else {
product = std::int64_t(static_cast<unsigned __int128>(quo) *
mat[row][nxt] % mod);
}
mat[col][nxt] -= product;
if (mat[col][nxt] < 0) {
mat[col][nxt] += mod;
}
}
}
std::swap(mat[col], mat[row]);
negative = !negative;
}
}
res = std::int64_t(__int128(res) * mat[col][col] % mod);
if (res == 0) {
return 0;
}
}
return negative ? mod - res : res;
}
} // namespace noya
// NOYA_DETERMINANT_MOD_HPP