This documentation is automatically generated by online-judge-tools/verification-helper
#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());
}