This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "linalg/det.hpp"
#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()); }