diff options
| -rw-r--r-- | content/datastructures/lichao.cpp | 2 | ||||
| -rw-r--r-- | content/math/lgsFp.cpp | 45 | ||||
| -rw-r--r-- | test/math/lgsFp.cpp | 12 |
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++) { |