blob: a4f3d0f2641e64ee5e3c09ab2b9237294d881037 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
vector<int> piv;
void gauss(){
for(int r = 0, c = 0; c < m; c++){
for(int i = r; i < n; i++){
if(mat[i][c] != 0){
swap(mat[r], mat[i]);
break;
}}
if(mat[r][c] == 0) continue;
ll f = multInv(mat[r][c], mod);
for(ll &x : mat[r]) x = x * f % mod;
for(int i = 0; i < n; i++){
if(i == r) continue;
f = mat[i][c];
for(int j = c; j < sz(mat[r]); j++){
mat[i][j] = (mat[i][j] - f * mat[r][j] % mod + mod) % mod;
}}
piv.push_back(c);
if(++r == n) break;
}}
|
