diff options
Diffstat (limited to 'test/math')
34 files changed, 95 insertions, 190 deletions
diff --git a/test/math/berlekampMassey.cpp b/test/math/berlekampMassey.cpp index 58fd143..a9d5709 100644 --- a/test/math/berlekampMassey.cpp +++ b/test/math/berlekampMassey.cpp @@ -12,10 +12,10 @@ struct RandomRecurence { } ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); @@ -60,7 +60,7 @@ void performance_test() { cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } - + int main() { stress_test(); performance_test(); diff --git a/test/math/bigint.cpp b/test/math/bigint.cpp index 3fc4ac1..538d0dc 100644 --- a/test/math/bigint.cpp +++ b/test/math/bigint.cpp @@ -9,7 +9,7 @@ struct modInt { stringstream a; a << x; string b = a.str(); - for (ll i = b[0] == '-' ? 1 : 0; i < sz(b); i++) { + for (ll i = b[0] == '-' ? 1 : 0; i < ssize(b); i++) { value *= 10; value += b[i] - '0'; value %= MOD; @@ -115,7 +115,7 @@ void stress_test() { } cerr << "tested random queries: " << queries << endl; } - + int main() { stress_test(); } diff --git a/test/math/binomial0.cpp b/test/math/binomial0.cpp index 00c04d4..25ee344 100644 --- a/test/math/binomial0.cpp +++ b/test/math/binomial0.cpp @@ -14,7 +14,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial1.cpp b/test/math/binomial1.cpp index f6fe20b..f7d06dd 100644 --- a/test/math/binomial1.cpp +++ b/test/math/binomial1.cpp @@ -11,7 +11,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial2.cpp b/test/math/binomial2.cpp index b55c8af..0b6178e 100644 --- a/test/math/binomial2.cpp +++ b/test/math/binomial2.cpp @@ -12,7 +12,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/binomial3.cpp b/test/math/binomial3.cpp index 4a99689..c4791d0 100644 --- a/test/math/binomial3.cpp +++ b/test/math/binomial3.cpp @@ -15,7 +15,7 @@ void stress_test() { ll expected = last[j]; if (got != expected) cerr << "calc_binom(" << i << ", " << j << "), got: " << got << ", expected: " << expected << FAIL; } - queries += sz(last); + queries += ssize(last); last.push_back(1); for (ll j = i; j > 0; j--) { diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp index bf57aed..1694589 100644 --- a/test/math/cycleDetection.cpp +++ b/test/math/cycleDetection.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/cycleDetection.cpp> pair<ll, ll> naive(ll x0, function<ll(ll)> f) { diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp index 6e4759d..eb8f641 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -7,10 +7,10 @@ vector<vector<double>> mat; #include <math/gauss.cpp> vector<vector<double>> inverseMat(const vector<vector<double>>& m) { - int n = sz(m); + int n = ssize(m); mat = m; for (int i = 0; i < n; i++) { - if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + if (ssize(mat[i]) != n) cerr << "error: no square matrix" << FAIL; mat[i].resize(2*n); mat[i][n+i] = 1; } @@ -27,10 +27,10 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) { } vector<vector<double>> mul(const vector<vector<double>>& a, const vector<vector<double>>& b) { - int n = sz(a); - int m = sz(b[0]); - int x = sz(b); - if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + int n = ssize(a); + int m = ssize(b[0]); + int x = ssize(b); + if (ssize(a[0]) != ssize(b)) cerr << "error: wrong dimensions" << FAIL; vector<vector<double>> res(n, vector<double>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { @@ -48,21 +48,21 @@ void test_tiny() { {0, 5, 6, 7}, {0, 0, 8, 9}, }; - if (gauss(sz(mat)) != UNIQUE) cerr << "error: 1" << FAIL; + if (gauss(ssize(mat)) != UNIQUE) cerr << "error: 1" << FAIL; mat = { {-1, 1, 0, -1}, { 2, 6, 0, 10}, { 1, -2, 0, 0}, }; - if (gauss(sz(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; + if (gauss(ssize(mat)) != MULTIPLE) cerr << "error: 2" << FAIL; mat = { {-1, 1, 0, -1}, { 2, 6, 0, 10}, { 1, -2, 0, 1}, }; - if (gauss(sz(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; + if (gauss(ssize(mat)) != INCONSISTENT) cerr << "error: 3" << FAIL; } void stress_test_inv() { diff --git a/test/math/gcd-lcm.cpp b/test/math/gcd-lcm.cpp deleted file mode 100644 index 294095b..0000000 --- a/test/math/gcd-lcm.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include "../util.h" -#include <math/gcd-lcm.cpp> - -void stress_test() { - if (::gcd(0, 0) != 0) cerr << "error: gcd(0, 0)" << FAIL; - if (::lcm(0, 0) != 0) cerr << "error: lcm(0, 0)" << FAIL; - ll queries = 0; - timer t; - for (int i = 0; i < 1'000'000; i++) { - ll a = Random::integer<ll>(0, 1'000'000'000); - ll b = 0; - { - ll got = ::gcd(a, b); - ll expected = std::gcd(a, b); - if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; - } - { - ll got = ::lcm(a, b); - ll expected = std::lcm(a, b); - if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; - } - b = Random::integer<ll>(0, 1'000'000'000); - { - t.start(); - ll got = ::gcd(a, b); - t.stop(); - ll expected = std::gcd(a, b); - if (got != expected) cerr << "gcd(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; - } - { - t.start(); - ll got = ::lcm(a, b); - t.stop(); - ll expected = std::lcm(a, b); - if (got != expected) cerr << "lcm(" << a << ", " << b << "), got: " << got << ", expected: " << expected << FAIL; - } - queries++; - } - cerr << "tested random queries: " << queries << endl; - if (t.time > 750) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms" << endl; -} - -int main() { - stress_test(); -} diff --git a/test/math/inversions.cpp b/test/math/inversions.cpp index d2a54b7..fc825e4 100644 --- a/test/math/inversions.cpp +++ b/test/math/inversions.cpp @@ -1,10 +1,9 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/inversions.cpp> ll naive(const vector<ll>& v) { ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { for (ll j = 0; j < i; j++) { if (v[j] > v[i]) res++; } diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp index acdc555..7d1b0d7 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -3,7 +3,7 @@ ll naive(const vector<ll>& v) { ll res = 0; - for (ll i = 0; i < sz(v); i++) { + for (ll i = 0; i < ssize(v); i++) { for (ll j = 0; j < i; j++) { if (v[j] > v[i]) res++; } @@ -17,7 +17,7 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> v(n); for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ): - shuffle(all(v), Random::rng); + ranges::shuffle(v, Random::rng); ll expected = naive(v); ll got = mergeSort(v); if (got != expected) { diff --git a/test/math/kthperm.cpp b/test/math/kthperm.cpp index 16691b9..1b3e803 100644 --- a/test/math/kthperm.cpp +++ b/test/math/kthperm.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> void stress_test() { @@ -7,13 +6,13 @@ void stress_test() { for (ll i = 0; i < 10'000; i++) { int n = Random::integer<int>(1, 100); vector<ll> expected(n); - iota(all(expected), 0); + iota(begin(expected), end(expected), 0); ll k = 0; do { auto got = kthperm(n, k); if (got != expected) cerr << "error" << FAIL; k++; - } while (k < 100 && next_permutation(all(expected))); + } while (k < 100 && ranges::next_permutation(expected).found); queries += n; } cerr << "tested queries: " << queries << endl; diff --git a/test/math/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp index d84524e..5e05c73 100644 --- a/test/math/kthperm_permIndex.cpp +++ b/test/math/kthperm_permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/kthperm.cpp> #include <math/permIndex.cpp> diff --git a/test/math/lgsFp.cpp b/test/math/lgsFp.cpp index 08f8f84..fa2dea3 100644 --- a/test/math/lgsFp.cpp +++ b/test/math/lgsFp.cpp @@ -6,10 +6,10 @@ vector<vector<ll>> mat; constexpr ll mod = 1'000'000'007; vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) { - int n = sz(m); + int n = ssize(m); mat = m; for (int i = 0; i < n; i++) { - if (sz(mat[i]) != n) cerr << "error: no square matrix" << FAIL; + if (ssize(mat[i]) != n) cerr << "error: no square matrix" << FAIL; mat[i].resize(2*n); mat[i][n+i] = 1; } @@ -26,10 +26,10 @@ vector<vector<ll>> inverseMat(const vector<vector<ll>>& m) { } vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>>& b) { - int n = sz(a); - int m = sz(b[0]); - int x = sz(b); - if (sz(a[0]) != sz(b)) cerr << "error: wrong dimensions" << FAIL; + int n = ssize(a); + int m = ssize(b[0]); + int x = ssize(b); + if (ssize(a[0]) != ssize(b)) cerr << "error: wrong dimensions" << FAIL; vector<vector<ll>> res(n, vector<ll>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index f0ebe76..79607ac 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -6,16 +6,15 @@ vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { return mulSlow(a, b); } - struct RandomRecurence { vector<ll> f, c, cache; RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp index e03c27e..922d965 100644 --- a/test/math/linearRecurrenceNTT.cpp +++ b/test/math/linearRecurrenceNTT.cpp @@ -12,10 +12,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp index dab2256..70609f0 100644 --- a/test/math/linearRecurrenceOld.cpp +++ b/test/math/linearRecurrenceOld.cpp @@ -6,10 +6,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); diff --git a/test/math/linearSieve.cpp b/test/math/linearSieve.cpp index 8ea822b..527e729 100644 --- a/test/math/linearSieve.cpp +++ b/test/math/linearSieve.cpp @@ -57,7 +57,7 @@ void performance_test() { timer t; t.start(); sieve(); - hash_t hash = sz(primes); + hash_t hash = ssize(primes); t.stop(); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/math/longestIncreasingSubsequence.cpp b/test/math/longestIncreasingSubsequence.cpp index 407dafe..befee75 100644 --- a/test/math/longestIncreasingSubsequence.cpp +++ b/test/math/longestIncreasingSubsequence.cpp @@ -9,7 +9,7 @@ constexpr ll INF = LL::INF; template<bool STRICT> bool isLis(const vector<ll>& a, const vector<int>& lis) { - for (int i = 1; i < sz(lis); i++) { + for (int i = 1; i < ssize(lis); i++) { if (lis[i-1] >= lis[i]) return false; if (a[lis[i-1]] > a[lis[i]]) return false; if (STRICT && a[lis[i-1]] == a[lis[i]]) return false; @@ -20,12 +20,12 @@ bool isLis(const vector<ll>& a, const vector<int>& lis) { template<bool STRICT> vector<int> naive(const vector<ll>& a) { vector<int> res; - for (ll i = 1; i < (1ll << sz(a)); i++) { + for (ll i = 1; i < (1ll << ssize(a)); i++) { vector<int> tmp; - for (ll j = 0; j < sz(a); j++) { + for (ll j = 0; j < ssize(a); j++) { if (((i >> j) & 1) != 0) tmp.push_back(j); } - if (sz(tmp) >= sz(res) && isLis<STRICT>(a, tmp)) res = tmp; + if (ssize(tmp) >= ssize(res) && isLis<STRICT>(a, tmp)) res = tmp; } return res; } @@ -56,10 +56,9 @@ void performance_test() { timer t; auto a = Random::integers<ll>(N, -10'000, 10'000); auto b = Random::integers<ll>(N, -10'000, 10'000); - sort(all(b)); + ranges::sort(b); auto c = Random::integers<ll>(N, -10'000, 10'000); - sort(all(c)); - reverse(all(c)); + ranges::sort(c | views::reverse); hash_t hash = 0; t.start(); hash += lis(a).size(); diff --git a/test/math/matrixPower.cpp b/test/math/matrixPower.cpp index 4dfb0a8..169ff06 100644 --- a/test/math/matrixPower.cpp +++ b/test/math/matrixPower.cpp @@ -7,15 +7,15 @@ struct mat { mat(int dim = 0, int diag = 1) : m(dim, vector<ll>(dim)) { for (int i = 0; i < dim; i++) m[i][i] = diag; } - mat(const vector<ll> c) : m(sz(c), vector<ll>(sz(c))) { + mat(const vector<ll> c) : m(ssize(c), vector<ll>(ssize(c))) { m[0] = c; - for (ll i = 1; i < sz(c); i++) { + for (ll i = 1; i < ssize(c); i++) { m[i][i-1] = 1; } } mat operator*(const mat& o) const { - int dim = sz(m); + int dim = ssize(m); mat res(dim, 0); for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { @@ -29,7 +29,7 @@ struct mat { } vector<ll> operator*(const vector<ll>& o) const { - int dim = sz(m); + int dim = ssize(m); vector<ll> res(dim); for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { @@ -48,10 +48,10 @@ struct RandomRecurence { RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} ll operator()(ll k){ - while (sz(cache) <= k) { + while (ssize(cache) <= k) { ll cur = 0; - for (ll i = 0; i < sz(c); i++) { - cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + for (ll i = 0; i < ssize(c); i++) { + cur += (c[i] * cache[ssize(cache) - i - 1]) % mod; } cur %= mod; cache.push_back(cur); @@ -67,13 +67,13 @@ void stress_test() { RandomRecurence f(n); precalc(mat(f.c)); auto tmp = f.f; - reverse(all(tmp)); + ranges::reverse(tmp); for (int j = 0; j < 100; j++) { ll k = Random::integer<ll>(0, 1000); vector<ll> got = calc(k, tmp); - vector<ll> expected(sz(f.f)); + vector<ll> expected(ssize(f.f)); for (ll l = 0; l < n; l++) expected[n - 1 - l] = f(k + l); if (got != expected) cerr << "error" << FAIL; @@ -89,7 +89,7 @@ void performance_test() { timer t; RandomRecurence f(N); auto tmp = f.f; - reverse(all(tmp)); + ranges::reverse(tmp); t.start(); precalc(mat(f.c)); diff --git a/test/math/millerRabin.base32.cpp b/test/math/millerRabin.base32.cpp index 742d353..8c2c79a 100644 --- a/test/math/millerRabin.base32.cpp +++ b/test/math/millerRabin.base32.cpp @@ -95,7 +95,7 @@ void extra_tests() { t.start(); auto got = isPrime(x); t.stop(); - bool expected = sz(factors) == 1 && factors.begin()->second == 1; + bool expected = ssize(factors) == 1 && factors.begin()->second == 1; if (got != expected) cerr << "error: " << x << FAIL; } if (t.time > 10) cerr << "too slow" << FAIL; diff --git a/test/math/millerRabin.cpp b/test/math/millerRabin.cpp index fd98586..725b744 100644 --- a/test/math/millerRabin.cpp +++ b/test/math/millerRabin.cpp @@ -87,7 +87,7 @@ void extra_tests() { t.start(); auto got = isPrime(x); t.stop(); - bool expected = sz(factors) == 1 && factors.begin()->second == 1; + bool expected = ssize(factors) == 1 && factors.begin()->second == 1; if (got != expected) cerr << "error: " << x << FAIL; } if (t.time > 10) cerr << "too slow" << FAIL; diff --git a/test/math/modExp.cpp b/test/math/modExp.cpp deleted file mode 100644 index ebb38eb..0000000 --- a/test/math/modExp.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include "../util.h" -#include <math/modExp.cpp> - -void stress_test() { - ll queries = 0; - for (ll i = 0; i < 10'000; i++) { - int a = Random::integer<int>(1, 100); - int n = Random::integer<int>(2, 100); - ll expected = 1; - ll k = 0; - do { - auto got = powMod(a, k, n); - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; - k++; - expected = (expected * a) % n; - } while (k < 100); - queries += n; - } - cerr << "tested queries: " << queries << endl; -} - -constexpr int N = 1'000'000; -void performance_test() { - timer t; - hash_t hash = 0; - for (int operations = 0; operations < N; operations++) { - ll a = Random::integer<ll>(0, 1'000'000'000); - ll b = Random::integer<ll>(0, 1'000'000'000); - ll n = Random::integer<ll>(2, 1'000'000'000); - t.start(); - hash += powMod(a, b, n); - t.stop(); - } - if (t.time > 750) cerr << "too slow: " << t.time << FAIL; - cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; -} - -int main() { - stress_test(); - performance_test(); -} - diff --git a/test/math/permIndex.cpp b/test/math/permIndex.cpp index 61d34c8..d68ba3a 100644 --- a/test/math/permIndex.cpp +++ b/test/math/permIndex.cpp @@ -1,5 +1,4 @@ #include "../util.h" -#include <datastructures/pbds.cpp> #include <math/permIndex.cpp> void stress_test() { @@ -7,13 +6,13 @@ void stress_test() { for (ll i = 0; i < 10'000; i++) { int n = Random::integer<int>(1, 100); vector<ll> cur(n); - iota(all(cur), 0); + iota(begin(cur), end(cur), 0); ll expected = 0; do { auto got = permIndex(cur); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; expected++; - } while (expected < 100 && next_permutation(all(cur))); + } while (expected < 100 && ranges::next_permutation(cur).found); queries += n; } cerr << "tested queries: " << queries << endl; @@ -23,7 +22,7 @@ constexpr int N = 500'000; void performance_test() { timer t; vector<ll> cur(N); - iota(all(cur), 0); + iota(begin(cur), end(cur), 0); reverse(cur.end() - 10, cur.end()); t.start(); auto hash = permIndex(cur); diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp index f4a9486..adf3773 100644 --- a/test/math/polynomial.cpp +++ b/test/math/polynomial.cpp @@ -11,7 +11,7 @@ poly randomPoly(int deg) { ll eval(const vector<ll>& p, ll x) { ll res = 0; - for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) { + for (ll i = 0, j = 1; i < ssize(p); i++, j = (j * x) % mod) { res += j * p[i]; res %= mod; } @@ -50,7 +50,7 @@ void test_add() { auto c = a; c += b; - if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL; + if (ssize(c) > ssize(a) && ssize(c) > ssize(b)) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + m + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -74,7 +74,7 @@ void test_mul() { auto b = randomPoly(m); auto c = a * b; - if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL; + if (ssize(c) > ssize(a) + ssize(b) - 1) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + m + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -97,8 +97,8 @@ void test_shift() { auto a = randomPoly(n); auto b = a << m; - if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl; - if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL; + if (ssize(b) > ssize(a)) cerr << ssize(a) << " " << ssize(b) << endl; + if (ssize(b) > ssize(a)) cerr << "error: wrong degree" << FAIL; for (int i = 0; i <= n + 7; i++) { ll x = Random::integer<ll>(0, mod); @@ -126,8 +126,8 @@ void test_divmod() { auto b = randomPoly(m); auto [div, rem] = a.divmod(b); - if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL; - if (sz(div) > 1 + max<ll>(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL; + if (ssize(rem) > ssize(b)) cerr << "error: wrong degree (rem)" << FAIL; + if (ssize(div) > 1 + max<ll>(0, ssize(a) - ssize(b))) cerr << "error: wrong degree (div)" << FAIL; for (int i = 0; i <= n + m; i++) { ll x = Random::integer<ll>(0, mod); @@ -142,7 +142,7 @@ void test_divmod() { } cerr << "tested divmod: " << queries << endl; } - + int main() { test_eval(); test_add(); diff --git a/test/math/primeSieve.cpp b/test/math/primeSieve.cpp index 78a50d2..6bb63f6 100644 --- a/test/math/primeSieve.cpp +++ b/test/math/primeSieve.cpp @@ -18,7 +18,7 @@ void stress_test() { if (got) found.push_back(i); queries++; } - primes.resize(sz(found)); + primes.resize(ssize(found)); if (primes != found) cerr << "error: primes" << FAIL; for (int i = 0; i < 1'000'000; i++) { ll x = Random::integer<ll>(2, N); @@ -34,7 +34,7 @@ void performance_test() { timer t; t.start(); primeSieve(); - hash_t hash = sz(primes); + hash_t hash = ssize(primes); t.stop(); if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; diff --git a/test/math/primitiveRoot.cpp b/test/math/primitiveRoot.cpp index cd0b388..6ad7429 100644 --- a/test/math/primitiveRoot.cpp +++ b/test/math/primitiveRoot.cpp @@ -63,7 +63,7 @@ void stress_test2() { map<ll, int> facts; factor(x, facts); if (x % 2 == 0) facts.erase(facts.find(2)); - bool expected = sz(facts) == 1; + bool expected = ssize(facts) == 1; if (x % 4 == 0) expected = false; if (x == 2 || x == 4) expected = true; diff --git a/test/math/shortModInv.cpp b/test/math/shortModInv.cpp index 26960bf..565989c 100644 --- a/test/math/shortModInv.cpp +++ b/test/math/shortModInv.cpp @@ -7,7 +7,7 @@ void stress_test() { ll n = Random::integer<ll>(2, 1'000'000'000); ll x = 0; do { - x = Random::integer<ll>(0, n); + x = Random::integer<ll>(0, 1'000'000'000); } while (gcd(x, n) != 1); ll y = multInv(x, n); ll got = (x*y) % n; diff --git a/test/math/transforms/fft.cpp b/test/math/transforms/fft.cpp index 858676b..66df1bf 100644 --- a/test/math/transforms/fft.cpp +++ b/test/math/transforms/fft.cpp @@ -2,14 +2,14 @@ #include <math/transforms/fft.cpp> vector<cplx> to_cplx(const vector<ll>& in) { - vector<cplx> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = in[i]; + vector<cplx> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = in[i]; return res; } vector<ll> from_cplx(const vector<cplx>& in) { - vector<ll> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector<ll> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = llround(real(in[i])); return res; } diff --git a/test/math/transforms/fftMul.cpp b/test/math/transforms/fftMul.cpp index 5933864..7887a5e 100644 --- a/test/math/transforms/fftMul.cpp +++ b/test/math/transforms/fftMul.cpp @@ -5,21 +5,21 @@ #include <math/transforms/fftMul.cpp> vector<ll> from_cplx(const vector<cplx>& in) { - vector<ll> res(sz(in)); - for (int i = 0; i < sz(in); i++) res[i] = llround(real(in[i])); + vector<ll> res(ssize(in)); + for (int i = 0; i < ssize(in); i++) res[i] = llround(real(in[i])); return res; } vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyBitwise.cpp b/test/math/transforms/multiplyBitwise.cpp index bc73290..8b9eb2f 100644 --- a/test/math/transforms/multiplyBitwise.cpp +++ b/test/math/transforms/multiplyBitwise.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) <= i && sz(b) <= i) { + if (ssize(a) <= i && ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i&j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyFFT.cpp b/test/math/transforms/multiplyFFT.cpp index 782be1b..61040d0 100644 --- a/test/math/transforms/multiplyFFT.cpp +++ b/test/math/transforms/multiplyFFT.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; } } diff --git a/test/math/transforms/multiplyNTT.cpp b/test/math/transforms/multiplyNTT.cpp index 70fc137..6424c50 100644 --- a/test/math/transforms/multiplyNTT.cpp +++ b/test/math/transforms/multiplyNTT.cpp @@ -6,13 +6,13 @@ vector<ll> naive(const vector<ll>& a, const vector<ll>& b) { vector<ll> res; for (ll i = 1;; i *= 2) { - if (sz(a) + sz(b) <= i) { + if (ssize(a) + ssize(b) <= i) { res.resize(i, 0); break; } } - for (int i = 0; i < sz(a); i++) { - for (int j = 0; j < sz(b); j++) { + for (int i = 0; i < ssize(a); i++) { + for (int j = 0; j < ssize(b); j++) { res[i+j] += a[i] * b[j]; res[i+j] %= mod; } diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp index ee30e00..f78541d 100644 --- a/test/math/transforms/seriesOperations.cpp +++ b/test/math/transforms/seriesOperations.cpp @@ -24,7 +24,7 @@ namespace reference {//checked against yosupo } vector<ll> poly_deriv(vector<ll> a){ - for(int i = 0; i < sz(a)-1; i++) + for(int i = 0; i < ssize(a)-1; i++) a[i] = a[i+1] * (i+1) % mod; a.pop_back(); return a; @@ -32,8 +32,8 @@ namespace reference {//checked against yosupo vector<ll> poly_integr(vector<ll> a){ if(a.empty()) return {0}; - a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); - for(int i = sz(a)-2; i > 0; i--) + a.push_back(a.back() * powMod(ssize(a), mod-2, mod) % mod); + for(int i = ssize(a)-2; i > 0; i--) a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; a[0] = 0; return a; @@ -51,7 +51,7 @@ namespace reference {//checked against yosupo for(int len = 1; len < n; len *= 2){ vector<ll> p = poly_log(q, 2*len); for(int i = 0; i < 2*len; i++) - p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; + p[i] = (mod - p[i] + (i < ssize(a) ? a[i] : 0)) % mod; vector<ll> q2 = q; q2.resize(2*len); ntt(p), ntt(q2); |