merge mzuenni changes

2 files changed, 21 insertions, 26 deletions

diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index bdbf5f9..da965dd 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -1,5 +1,5 @@
 vector<ll> xs; // IMPORTANT: Initialize before constructing!
-int findX(int i) {
+int findX(ll i) {
 	return ranges::lower_bound(xs, i) - begin(xs); }
 
 struct Fun { // Default: Linear function. Change as needed.
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index 64e4c09..4c12477 100644
--- a/content/math/lgsFp.cpp
+++ b/content/math/lgsFp.cpp
@@ -1,25 +1,20 @@
-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 < ssize(mat[i]); 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 @\sourceref{math/gauss.cpp}@
+vector<int> pivots; // ith pivot is in ith row
+void gauss(int n, int m) {
+	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 < m; j++) {
+				mat[i][j] = (mat[i][j] - f*mat[r][j] % mod + mod) % mod;
+		}}
+		pivots.push_back(c);
+		if (++r == n) break;
+}} // no solution if pivots.back() == m-1