From 2b38e35c518fa52eef8024e805fdb78df9d7f92f Mon Sep 17 00:00:00 2001
From: Lucas Schwebler <lucas.schwebler@gmail.com>
Date: Tue, 13 May 2025 15:25:57 +0200
Subject: new gauss

---
 content/math/lgsFp.cpp | 45 ++++++++++++++++++++-------------------------
 test/math/lgsFp.cpp    | 19 ++++++++++++++-----
 2 files changed, 34 insertions(+), 30 deletions(-)

diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index bf18c86..a4f3d0f 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 < sz(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> 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;
+}}
\ No newline at end of file
diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp
index 08f8f84..e529390 100644
--- a/test/math/lgsFp.cpp
+++ b/test/math/lgsFp.cpp
@@ -1,9 +1,12 @@
 #include "../util.h"
 #include <math/shortModInv.cpp>
 vector<vector<ll>> mat;
-#include <math/lgsFp.cpp>
-
 constexpr ll mod = 1'000'000'007;
+namespace lgs {
+	int n, m;
+	#include <math/lgsFp.cpp>
+}
+
 
 vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) {
 	int n = sz(m);
@@ -13,7 +16,9 @@ vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) {
 		mat[i].resize(2*n);
 		mat[i][n+i] = 1;
 	}
-	gauss(n, mod);
+	lgs::n = sz(mat);
+	lgs::m = sz(mat[0]);
+	lgs::gauss();
 	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 +57,9 @@ 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::n = sz(mat);
+		lgs::m = sz(mat[0]);
+		lgs::gauss();
 
 		for (int i = 0; i < n; i++) {
 			for (int j = 0; j < n; j++) {
@@ -97,9 +104,11 @@ void performance_test() {
 	vector<vector<ll>> m(N);
 	for (auto& v : m) v = Random::integers<ll>(N, 0, mod);
 	mat = m;
+	lgs::n = sz(mat);
+	lgs::m = sz(mat[0]);
 
 	t.start();
-	gauss(N, mod);
+	lgs::gauss();
 	t.stop();
 	hash_t hash = 0;
 	for (int i = 0; i < N; i++) {
-- 
cgit v1.2.3