This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// mod p 行列に対する主要な操作
// 実数じゃないので絶対値最大のものを pivot にするとかがいらない
// ガウスの消去法
template <typename mint>
int gaussianEliminationModp(Matrix<mint> &mat, bool ext=false) {
int N = mat.size(), M = mat[0].size(), rank = 0;
for(int j=0; j+ext<M; j++) {
int piv = -1;
for(int i=rank; i<N; i++) {
if(mat[i][j] != mint(0)) piv = i, i = N;
}
if(piv < 0) continue;
swap(mat[rank], mat[piv]);
mint div(mat[rank][j]);
for(auto &v : mat[rank]) v /= div;
for(int i=0; i<N; i++) {
if(i == rank or mat[i][j] == mint(0)) continue;
mint scale = mat[i][j];
for(int k=0; k<M; k++) {
mat[i][k] -= mat[rank][k] * scale;
}
}
rank++;
}
return rank;
}
template <typename mint>
vector<mint> linearEquationModp(Matrix<mint> A, vector<mint> b) {
int N = A.size(), M = A[0].size();
Matrix<mint> mat(N, M+1);
for(int i=0; i<N; i++) {
for(int j=0; j<M+1; j++) {
mat[i][j] = (j < M ? A[i][j] : b[i]);
}
}
int rank = gaussianEliminationModp(mat, true);
vector<mint> res(N);
for(int i=0; i<N; i++) {
res[i] = mat[i][M];
if(i >= rank and mat[i][M] != mint(0)) return {};
}
return res;
}
template <typename mint>
mint detModp(Matrix<mint> A) {
int N = A.size(), cnt_swap = 0;
for(int j=0; j<N; j++) {
int piv = -1;
for(int i=j; i<N; i++) {
if(A[i][j] != mint(0)) piv = i, i = N;
}
if(piv < 0) return mint(0);
cnt_swap += (piv != j);
swap(A[piv], A[j]);
for(int i=j+1; i<N; i++) {
mint scale(A[i][j] / A[j][j]);
for(int k=0; k<N; k++) {
A[i][k] -= A[j][k] * scale;
}
}
}
mint res = (cnt_swap % 2 ? mint(-1) : mint(1));
for(int i=0; i<N; i++) res *= A[i][i];
return res;
}
#line 1 "math/math_023_matrix_utils_modp.cpp"
// mod p 行列に対する主要な操作
// 実数じゃないので絶対値最大のものを pivot にするとかがいらない
// ガウスの消去法
template <typename mint>
int gaussianEliminationModp(Matrix<mint> &mat, bool ext=false) {
int N = mat.size(), M = mat[0].size(), rank = 0;
for(int j=0; j+ext<M; j++) {
int piv = -1;
for(int i=rank; i<N; i++) {
if(mat[i][j] != mint(0)) piv = i, i = N;
}
if(piv < 0) continue;
swap(mat[rank], mat[piv]);
mint div(mat[rank][j]);
for(auto &v : mat[rank]) v /= div;
for(int i=0; i<N; i++) {
if(i == rank or mat[i][j] == mint(0)) continue;
mint scale = mat[i][j];
for(int k=0; k<M; k++) {
mat[i][k] -= mat[rank][k] * scale;
}
}
rank++;
}
return rank;
}
template <typename mint>
vector<mint> linearEquationModp(Matrix<mint> A, vector<mint> b) {
int N = A.size(), M = A[0].size();
Matrix<mint> mat(N, M+1);
for(int i=0; i<N; i++) {
for(int j=0; j<M+1; j++) {
mat[i][j] = (j < M ? A[i][j] : b[i]);
}
}
int rank = gaussianEliminationModp(mat, true);
vector<mint> res(N);
for(int i=0; i<N; i++) {
res[i] = mat[i][M];
if(i >= rank and mat[i][M] != mint(0)) return {};
}
return res;
}
template <typename mint>
mint detModp(Matrix<mint> A) {
int N = A.size(), cnt_swap = 0;
for(int j=0; j<N; j++) {
int piv = -1;
for(int i=j; i<N; i++) {
if(A[i][j] != mint(0)) piv = i, i = N;
}
if(piv < 0) return mint(0);
cnt_swap += (piv != j);
swap(A[piv], A[j]);
for(int i=j+1; i<N; i++) {
mint scale(A[i][j] / A[j][j]);
for(int k=0; k<N; k++) {
A[i][k] -= A[j][k] * scale;
}
}
}
mint res = (cnt_swap % 2 ? mint(-1) : mint(1));
for(int i=0; i<N; i++) res *= A[i][i];
return res;
}