From 2b38e35c518fa52eef8024e805fdb78df9d7f92f Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Tue, 13 May 2025 15:25:57 +0200 Subject: new gauss --- content/math/lgsFp.cpp | 45 ++++++++++++++++++++------------------------- 1 file changed, 20 insertions(+), 25 deletions(-) (limited to 'content') 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 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 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 -- cgit v1.2.3 From 14a5aa119dd90c4764c47b00f141117b0193b73e Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Wed, 14 May 2025 14:29:31 +0200 Subject: lichao: fix ll int conversion --- content/datastructures/lichao.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index 1318ca7..9c41934 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -1,5 +1,5 @@ vector xs; // IMPORTANT: Initialize before constructing! -int findX(int i) {return lower_bound(all(xs), i) - begin(xs);} +int findX(ll i) {return lower_bound(all(xs), i) - begin(xs);} struct Fun { // Default: Linear function. Change as needed. ll m, c; -- cgit v1.2.3 From aca95353f22fb48fab74bf45de85f8badaa2e274 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 6 Jun 2025 15:21:51 +0200 Subject: improve gauss + fix latex --- content/math/lgsFp.cpp | 26 +++++++++++++------------- content/other/other.tex | 10 +++++----- tcr.pdf | Bin 698689 -> 685349 bytes test/math/lgsFp.cpp | 13 +++---------- 4 files changed, 21 insertions(+), 28 deletions(-) (limited to 'content') diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index a4f3d0f..a8d7fc7 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -1,20 +1,20 @@ -vector piv; -void gauss(){ - for(int r = 0, c = 0; c < m; c++){ - for(int i = r; i < n; i++){ - if(mat[i][c] != 0){ +vector 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; + 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; + 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++){ + for (int j = c; j < m; 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 + pivots.push_back(c); + if (++r == n) break; +}} // no solution if pivots.back() == m-1 diff --git a/content/other/other.tex b/content/other/other.tex index a38f6da..a5004fb 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -18,9 +18,9 @@ \begin{expandtable} \begin{tabularx}{\linewidth}{|lR|} \hline - Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\ - Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\ - Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\ + Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\ + Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\ + Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\ \hline \end{tabularx} \end{expandtable} @@ -30,9 +30,9 @@ \begin{expandtable} \begin{tabularx}{\linewidth}{|Ll|} \hline - Bit an Position j lesen & \code{(x & (1 << j)) != 0} \\ + Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\ Bit an Position j setzten & \code{x |= (1 << j)} \\ - Bit an Position j löschen & \code{x &= ~(1 << j)} \\ + Bit an Position j löschen & \code{x \&= ~(1 << j)} \\ Bit an Position j flippen & \code{x ^= (1 << j)} \\ Anzahl an führenden nullen ($x \neq 0$) & \code{__builtin_clzll(x)} \\ Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\ diff --git a/tcr.pdf b/tcr.pdf index eb0110f..16c465d 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp index e529390..d7680ea 100644 --- a/test/math/lgsFp.cpp +++ b/test/math/lgsFp.cpp @@ -3,7 +3,6 @@ vector> mat; constexpr ll mod = 1'000'000'007; namespace lgs { - int n, m; #include } @@ -16,9 +15,7 @@ vector> inverseMat(const vector>& m) { mat[i].resize(2*n); mat[i][n+i] = 1; } - lgs::n = sz(mat); - lgs::m = sz(mat[0]); - lgs::gauss(); + lgs::gauss(sz(mat), sz(mat[0])); vector> res(m); for (int i = 0; i < n; i++) { res[i] = vector(mat[i].begin() + n, mat[i].end()); @@ -57,9 +54,7 @@ void test_square() { vector> m(n); for (auto& v : m) v = Random::integers(n, 0, mod); mat = m; - lgs::n = sz(mat); - lgs::m = sz(mat[0]); - lgs::gauss(); + lgs::gauss(sz(mat), sz(mat[0])); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { @@ -104,11 +99,9 @@ void performance_test() { vector> m(N); for (auto& v : m) v = Random::integers(N, 0, mod); mat = m; - lgs::n = sz(mat); - lgs::m = sz(mat[0]); t.start(); - lgs::gauss(); + lgs::gauss(sz(mat), sz(mat[0])); t.stop(); hash_t hash = 0; for (int i = 0; i < N; i++) { -- cgit v1.2.3 From 4335aa75cf7eb9a3bb6c64f7955a96a7dcc08c75 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 6 Jun 2025 15:24:46 +0200 Subject: fix formatting --- content/math/lgsFp.cpp | 2 +- tcr.pdf | Bin 685349 -> 685349 bytes 2 files changed, 1 insertion(+), 1 deletion(-) (limited to 'content') diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index a8d7fc7..4c12477 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -13,7 +13,7 @@ void gauss(int n, int m) { 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; + mat[i][j] = (mat[i][j] - f*mat[r][j] % mod + mod) % mod; }} pivots.push_back(c); if (++r == n) break; diff --git a/tcr.pdf b/tcr.pdf index 16c465d..e112d3d 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3