diff options
| -rw-r--r-- | content/math/linearRecurrence.cpp | 26 | ||||
| -rw-r--r-- | tcr.pdf | bin | 695781 -> 695518 bytes | |||
| -rw-r--r-- | test/geometry/hpi.cpp | 109 | ||||
| -rw-r--r-- | test/math/linearRecurrence.cpp | 15 | ||||
| -rw-r--r-- | test/math/linearRecurrence.cpp.awk | 4 | ||||
| -rw-r--r-- | test/math/linearRecurrenceNTT.cpp (renamed from test/math/linearRecurrenceSlowMul.cpp) | 25 | ||||
| -rw-r--r-- | test/math/linearRecurrenceOld.cpp (renamed from test/math/linearRecurenceOld.cpp) | 0 |
7 files changed, 144 insertions, 35 deletions
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index ab86f71..a8adacd 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -1,19 +1,19 @@ -// constexpr ll mod = 998244353; -// vector<ll> mul(const vector<ll> &a, const vector<ll> &b){ -// vector<ll> c(sz(a) + sz(b) - 1); -// for(int i = 0; i < sz(a); i++){ -// for(int j = 0; j < sz(b); j++){ -// c[i+j] += a[i]*b[j] % mod; -// } -// } -// for(ll &x : c) x %= mod; -// return c; -// } +constexpr ll mod = 998244353; +// oder ntt mul @\sourceref{math/transforms/ntt.cpp}@ +vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { + vector<ll> c(sz(a) + sz(b) - 1); + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + c[i+j] += a[i]*b[j] % mod; + }} + for (ll& x : c) x %= mod; + return c; +} ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { int n = sz(c); vector<ll> q(n + 1, 1); - for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i])%mod; + for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i]) % mod; vector<ll> p = mul(f, q); p.resize(n); p.push_back(0); @@ -27,4 +27,4 @@ ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { } } while (k /= 2); return p[0]; -}
\ No newline at end of file +} Binary files differdiff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp new file mode 100644 index 0000000..e61178a --- /dev/null +++ b/test/geometry/hpi.cpp @@ -0,0 +1,109 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar<ll> +#include <geometry/formulas.cpp> +#undef polar +#undef double +#include "../geometry.h" +ll sgn(ll x) { + return (x > 0) - (x < 0); +} +#include <geometry/hpi.cpp> + +using ptd = complex<long double>; +ptd convert(pt x) {return ptd(real(x), imag(x));} +auto cross(ptd a, ptd b) {return imag(conj(a) * b);} +auto cross(ptd p, ptd a, ptd b) {return cross(a - p, b - p);} +ptd lineIntersection2(ptd a, ptd b, ptd c, ptd d) { + ld x = cross(b - a, d - c); + ld y = cross(c - a, d - c); + return a + y/x*(b - a); +} + +//check if a is dominated by b and c +bool naiveCheck(array<pt, 2> a, array<pt, 2> b, array<pt, 2> c) { + //https://cp-algorithms.com/geometry/halfplane-intersection.html + //intersect b and c + //check cross of a and intersection + ptd intersection = lineIntersection2( + convert(b[0]), + convert(b[1]), + convert(c[0]), + convert(c[1]) + ); + return cross(convert(a[0]), convert(a[1]), intersection) <= -1e-12; +} +//real(a - p)*imag(b - p)-imag(a - p)*real(b - p) + +void test_check(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::line(range); + auto b = Random::line(range); + auto c = b; + while ( + cross(b[0] - b[1], c[0] - c[1]) == 0 + //||cross(a[0] - a[1], b[0] - b[1], c[0] - c[1]) >= 0 + ) c = Random::line(range); + + bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1])); + bool expected = naiveCheck(a, b, c); + + if (got != expected) { + cout << tries << endl; + cout << a[0] << " " << a[1] << endl; + cout << b[0] << " " << b[1] << endl; + cout << c[0] << " " << c[1] << endl; + cout << boolalpha << got << " " << expected << endl; + cerr << "error" << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +/*void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto centre = Random::point<ll>(n, -range / 2, range / 2); + + } + cerr << "tested random queries: " << queries << endl; +}*/ + +/*constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + double maxTime = 0; + + vector<pt> ps; + for (int i = 0; i*i <= N; i++) { + for (int j = 0; j*j <= N; j++) { + ps.emplace_back(i, j); + } + } + t.start(); + hash = shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + ps = Random::points<ll>(N, -1'000'000'000, 1'000'000'000); + t.reset(); + t.start(); + hash += shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + if (maxTime > 500) cerr << "too slow: " << maxTime << FAIL; + cerr << "tested performance: " << maxTime << "ms (hash: " << hash << ")" << endl; +}*/ + +int main() { + test_check(10); + test_check(100); + test_check(1000); + test_check(10000); + //performance_test(); +} diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 50e98a0..f0ebe76 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -1,9 +1,12 @@ #include "../util.h" -#include <math/modPowIterativ.cpp> -#include <math/transforms/ntt.cpp> -#include <math/transforms/multiplyNTT.cpp> +vector<ll> mul(const vector<ll>& a, const vector<ll>& b); #include <math/linearRecurrence.cpp> +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) {} @@ -23,7 +26,7 @@ struct RandomRecurence { void stress_test() { int queries = 0; - for (int i = 0; i < 1'000; i++) { + for (int i = 0; i < 10'000; i++) { int n = Random::integer<int>(1, 10); RandomRecurence f(n); for (int j = 0; j < 100; j++) { @@ -39,14 +42,14 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } -constexpr int N = 100'000; +constexpr int N = 1'000; void performance_test() { timer t; RandomRecurence f(N); t.start(); hash_t hash = kthTerm(f.f, f.c, 1e18); t.stop(); - if (t.time > 8000) cerr << "too slow: " << t.time << FAIL; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/math/linearRecurrence.cpp.awk b/test/math/linearRecurrence.cpp.awk new file mode 100644 index 0000000..902fd4b --- /dev/null +++ b/test/math/linearRecurrence.cpp.awk @@ -0,0 +1,4 @@ +/vector<ll> mul/ { + sub(/mul/, "mulSlow") +} +{ print } diff --git a/test/math/linearRecurrenceSlowMul.cpp b/test/math/linearRecurrenceNTT.cpp index 205e584..e03c27e 100644 --- a/test/math/linearRecurrenceSlowMul.cpp +++ b/test/math/linearRecurrenceNTT.cpp @@ -1,18 +1,11 @@ #include "../util.h" - -constexpr ll mod = 998244353; -vector<ll> mul(const vector<ll> &a, const vector<ll> &b){ - vector<ll> c(sz(a) + sz(b) - 1); - for(int i = 0; i < sz(a); i++){ - for(int j = 0; j < sz(b); j++){ - c[i+j] += a[i]*b[j] % mod; - } - } - for(ll &x : c) x %= mod; - return c; -} - +#include <math/modPowIterativ.cpp> +#include <math/transforms/ntt.cpp> +#include <math/transforms/multiplyNTT.cpp> +#define mod mod2 #include <math/linearRecurrence.cpp> +#undef mod +static_assert(mod == mod2); struct RandomRecurence { vector<ll> f, c, cache; @@ -33,7 +26,7 @@ struct RandomRecurence { void stress_test() { int queries = 0; - for (int i = 0; i < 10'000; i++) { + for (int i = 0; i < 1'000; i++) { int n = Random::integer<int>(1, 10); RandomRecurence f(n); for (int j = 0; j < 100; j++) { @@ -49,14 +42,14 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } -constexpr int N = 1'000; +constexpr int N = 100'000; void performance_test() { timer t; RandomRecurence f(N); t.start(); hash_t hash = kthTerm(f.f, f.c, 1e18); t.stop(); - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + if (t.time > 8000) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/math/linearRecurenceOld.cpp b/test/math/linearRecurrenceOld.cpp index dab2256..dab2256 100644 --- a/test/math/linearRecurenceOld.cpp +++ b/test/math/linearRecurrenceOld.cpp |