merge mzuenni changes

3 files changed, 28 insertions, 31 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
diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp
index fa2dea3..9c7bda8 100644
--- a/test/math/lgsFp.cpp
+++ b/test/math/lgsFp.cpp
@@ -1,9 +1,11 @@
 #include "../util.h"
 #include <math/shortModInv.cpp>
 vector<vector<ll>> mat;
-#include <math/lgsFp.cpp>
-
 constexpr ll mod = 1'000'000'007;
+namespace lgs {
+	#include <math/lgsFp.cpp>
+}
+
 
 vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) {
 	int n = ssize(m);
@@ -13,7 +15,7 @@ vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) {
 		mat[i].resize(2*n);
 		mat[i][n+i] = 1;
 	}
-	gauss(n, mod);
+	lgs::gauss(ssize(mat), ssize(mat[0]));
 	vector<vector<ll>> res(m);
 	for (int i = 0; i < n; i++) {
 		res[i] = vector<ll>(mat[i].begin() + n, mat[i].end());
@@ -52,7 +54,7 @@ void test_square() {
 		vector<vector<ll>> m(n);
 		for (auto& v : m) v = Random::integers<ll>(n, 0, mod);
 		mat = m;
-		gauss(n, mod);
+		lgs::gauss(ssize(mat), ssize(mat[0]));
 
 		for (int i = 0; i < n; i++) {
 			for (int j = 0; j < n; j++) {
@@ -99,7 +101,7 @@ void performance_test() {
 	mat = m;
 
 	t.start();
-	gauss(N, mod);
+	lgs::gauss(ssize(mat), ssize(mat[0]));
 	t.stop();
 	hash_t hash = 0;
 	for (int i = 0; i < N; i++) {