blob: 7081fea837090bb7d64dfe2a229f25c9eb28923c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
void normalLine(int line, ll p) {
ll factor = multInv(mat[line][line], p);
for (ll& x : mat[line]) x = (x * factor) % p;
}
void takeAll(int n, int line, ll p) {
for (int i = 0; i < n; i++) {
if (i == line) continue;
ll diff = mat[i][line];
for (int j = 0; j <= n; j++) {
mat[i][j] -= (diff * mat[line][j]) % p;
mat[i][j] = (mat[i][j] + p) % p;
}}}
void gauss(int n, ll mod) {
vector<bool> done(n, false);
for (int i = 0; i < n; i++) {
int j = 0;
while (j < n && (done[j] || mat[j][i] == 0)) j++;
if (j == n) continue;
swap(mat[i], mat[j]);
normalLine(i, mod);
takeAll(n, i, mod);
done[i] = true;
}}
// für Eindeutigkeit, Existenz etc. siehe LGS über R
|
