From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- math/berlekampMassey.cpp | 31 -- math/bigint.cpp | 275 ----------------- math/binomial0.cpp | 14 - math/binomial1.cpp | 8 - math/binomial2.cpp | 32 -- math/binomial3.cpp | 10 - math/chineseRemainder.cpp | 14 - math/cycleDetection.cpp | 16 - math/discreteLogarithm.cpp | 14 - math/discreteNthRoot.cpp | 5 - math/divisors.cpp | 11 - math/extendedEuclid.cpp | 6 - math/gauss.cpp | 36 --- math/gcd-lcm.cpp | 2 - math/goldenSectionSearch.cpp | 15 - math/inversions.cpp | 9 - math/inversionsMerge.cpp | 27 -- math/kthperm.cpp | 14 - math/legendre.cpp | 4 - math/lgsFp.cpp | 26 -- math/linearCongruence.cpp | 5 - math/linearRecurence.cpp | 33 --- math/linearSieve.cpp | 49 ---- math/longestIncreasingSubsequence.cpp | 17 -- math/math.tex | 535 ---------------------------------- math/matrixPower.cpp | 16 - math/millerRabin.cpp | 19 -- math/mobius.cpp | 21 -- math/modExp.cpp | 6 - math/modMulIterativ.cpp | 9 - math/modPowIterativ.cpp | 9 - math/modSqrt.cpp | 23 -- math/multInv.cpp | 4 - math/permIndex.cpp | 13 - math/phi.cpp | 21 -- math/piLegendre.cpp | 23 -- math/piLehmer.cpp | 52 ---- math/polynomial.cpp | 65 ----- math/primeSieve.cpp | 16 - math/primitiveRoot.cpp | 23 -- math/rho.cpp | 19 -- math/shortModInv.cpp | 3 - math/simpson.cpp | 12 - math/sqrtModCipolla.cpp | 13 - math/squfof.cpp | 89 ------ math/tables.tex | 18 -- math/tables/binom.tex | 28 -- math/tables/composite.tex | 27 -- math/tables/nim.tex | 96 ------ math/tables/numbers.tex | 59 ---- math/tables/platonic.tex | 39 --- math/tables/probability.tex | 27 -- math/tables/series.tex | 33 --- math/tables/stuff.tex | 32 -- math/tables/twelvefold.tex | 32 -- math/transforms/andTransform.cpp | 8 - math/transforms/bitwiseTransforms.cpp | 12 - math/transforms/fft.cpp | 23 -- math/transforms/fftMul.cpp | 14 - math/transforms/multiplyBitwise.cpp | 8 - math/transforms/multiplyFFT.cpp | 12 - math/transforms/multiplyNTT.cpp | 8 - math/transforms/ntt.cpp | 23 -- math/transforms/orTransform.cpp | 8 - math/transforms/seriesOperations.cpp | 56 ---- math/transforms/xorTransform.cpp | 10 - 66 files changed, 2237 deletions(-) delete mode 100644 math/berlekampMassey.cpp delete mode 100644 math/bigint.cpp delete mode 100644 math/binomial0.cpp delete mode 100644 math/binomial1.cpp delete mode 100644 math/binomial2.cpp delete mode 100644 math/binomial3.cpp delete mode 100644 math/chineseRemainder.cpp delete mode 100644 math/cycleDetection.cpp delete mode 100644 math/discreteLogarithm.cpp delete mode 100644 math/discreteNthRoot.cpp delete mode 100644 math/divisors.cpp delete mode 100644 math/extendedEuclid.cpp delete mode 100644 math/gauss.cpp delete mode 100644 math/gcd-lcm.cpp delete mode 100644 math/goldenSectionSearch.cpp delete mode 100644 math/inversions.cpp delete mode 100644 math/inversionsMerge.cpp delete mode 100644 math/kthperm.cpp delete mode 100644 math/legendre.cpp delete mode 100644 math/lgsFp.cpp delete mode 100644 math/linearCongruence.cpp delete mode 100644 math/linearRecurence.cpp delete mode 100644 math/linearSieve.cpp delete mode 100644 math/longestIncreasingSubsequence.cpp delete mode 100644 math/math.tex delete mode 100644 math/matrixPower.cpp delete mode 100644 math/millerRabin.cpp delete mode 100644 math/mobius.cpp delete mode 100644 math/modExp.cpp delete mode 100644 math/modMulIterativ.cpp delete mode 100644 math/modPowIterativ.cpp delete mode 100644 math/modSqrt.cpp delete mode 100644 math/multInv.cpp delete mode 100644 math/permIndex.cpp delete mode 100644 math/phi.cpp delete mode 100644 math/piLegendre.cpp delete mode 100644 math/piLehmer.cpp delete mode 100644 math/polynomial.cpp delete mode 100644 math/primeSieve.cpp delete mode 100644 math/primitiveRoot.cpp delete mode 100644 math/rho.cpp delete mode 100644 math/shortModInv.cpp delete mode 100644 math/simpson.cpp delete mode 100644 math/sqrtModCipolla.cpp delete mode 100644 math/squfof.cpp delete mode 100644 math/tables.tex delete mode 100644 math/tables/binom.tex delete mode 100644 math/tables/composite.tex delete mode 100644 math/tables/nim.tex delete mode 100644 math/tables/numbers.tex delete mode 100644 math/tables/platonic.tex delete mode 100644 math/tables/probability.tex delete mode 100644 math/tables/series.tex delete mode 100644 math/tables/stuff.tex delete mode 100644 math/tables/twelvefold.tex delete mode 100644 math/transforms/andTransform.cpp delete mode 100644 math/transforms/bitwiseTransforms.cpp delete mode 100644 math/transforms/fft.cpp delete mode 100644 math/transforms/fftMul.cpp delete mode 100644 math/transforms/multiplyBitwise.cpp delete mode 100644 math/transforms/multiplyFFT.cpp delete mode 100644 math/transforms/multiplyNTT.cpp delete mode 100644 math/transforms/ntt.cpp delete mode 100644 math/transforms/orTransform.cpp delete mode 100644 math/transforms/seriesOperations.cpp delete mode 100644 math/transforms/xorTransform.cpp (limited to 'math') diff --git a/math/berlekampMassey.cpp b/math/berlekampMassey.cpp deleted file mode 100644 index 29e084f..0000000 --- a/math/berlekampMassey.cpp +++ /dev/null @@ -1,31 +0,0 @@ -constexpr ll mod = 1'000'000'007; -vector BerlekampMassey(const vector& s) { - int n = sz(s), L = 0, m = 0; - vector C(n), B(n), T; - C[0] = B[0] = 1; - - ll b = 1; - for (int i = 0; i < n; i++) { - m++; - ll d = s[i] % mod; - for (int j = 1; j <= L; j++) { - d = (d + C[j] * s[i - j]) % mod; - } - if (!d) continue; - T = C; - ll coef = d * powMod(b, mod-2, mod) % mod; - for (int j = m; j < n; j++) { - C[j] = (C[j] - coef * B[j - m]) % mod; - } - if (2 * L > i) continue; - L = i + 1 - L; - swap(B, T); - b = d; - m = 0; - } - - C.resize(L + 1); - C.erase(C.begin()); - for (auto& x : C) x = (mod - x) % mod; - return C; -} diff --git a/math/bigint.cpp b/math/bigint.cpp deleted file mode 100644 index 6f83a93..0000000 --- a/math/bigint.cpp +++ /dev/null @@ -1,275 +0,0 @@ -// base and base_digits must be consistent -constexpr ll base = 1'000'000; -constexpr ll base_digits = 6; -struct bigint { - vll a; ll sign; - - bigint() : sign(1) {} - - bigint(ll v) {*this = v;} - - bigint(const string &s) {read(s);} - - void operator=(const bigint& v) { - sign = v.sign; - a = v.a; - } - - void operator=(ll v) { - sign = 1; - if (v < 0) sign = -1, v = -v; - a.clear(); - for (; v > 0; v = v / base) - a.push_back(v % base); - } - - bigint operator+(const bigint& v) const { - if (sign == v.sign) { - bigint res = v; - for (ll i = 0, carry = 0; i < max(sz(a), sz(v.a)) || carry; ++i) { - if (i == sz(res.a)) - res.a.push_back(0); - res.a[i] += carry + (i < sz(a) ? a[i] : 0); - carry = res.a[i] >= base; - if (carry) - res.a[i] -= base; - } - return res; - } - return *this - (-v); - } - - bigint operator-(const bigint& v) const { - if (sign == v.sign) { - if (abs() >= v.abs()) { - bigint res = *this; - for (ll i = 0, carry = 0; i < sz(v.a) || carry; ++i) { - res.a[i] -= carry + (i < sz(v.a) ? v.a[i] : 0); - carry = res.a[i] < 0; - if (carry) res.a[i] += base; - } - res.trim(); - return res; - } - return -(v - *this); - } - return *this + (-v); - } - - void operator*=(ll v) { - if (v < 0) sign = -sign, v = -v; - for (ll i = 0, carry = 0; i < sz(a) || carry; ++i) { - if (i == sz(a)) a.push_back(0); - ll cur = a[i] * v + carry; - carry = cur / base; - a[i] = cur % base; - } - trim(); - } - - bigint operator*(ll v) const { - bigint res = *this; - res *= v; - return res; - } - - friend pair divmod(const bigint& a1, const bigint& b1) { - ll norm = base / (b1.a.back() + 1); - bigint a = a1.abs() * norm; - bigint b = b1.abs() * norm; - bigint q, r; - q.a.resize(sz(a.a)); - for (ll i = sz(a.a) - 1; i >= 0; i--) { - r *= base; - r += a.a[i]; - ll s1 = sz(r.a) <= sz(b.a) ? 0 : r.a[sz(b.a)]; - ll s2 = sz(r.a) <= sz(b.a) - 1 ? 0 : r.a[sz(b.a) - 1]; - ll d = (base * s1 + s2) / b.a.back(); - r -= b * d; - while (r < 0) r += b, --d; - q.a[i] = d; - } - q.sign = a1.sign * b1.sign; - r.sign = a1.sign; - q.trim(); - r.trim(); - return make_pair(q, r / norm); - } - - bigint operator/(const bigint& v) const { - return divmod(*this, v).first; - } - - bigint operator%(const bigint& v) const { - return divmod(*this, v).second; - } - - void operator/=(ll v) { - if (v < 0) sign = -sign, v = -v; - for (ll i = sz(a) - 1, rem = 0; i >= 0; --i) { - ll cur = a[i] + rem * base; - a[i] = cur / v; - rem = cur % v; - } - trim(); - } - - bigint operator/(ll v) const { - bigint res = *this; - res /= v; - return res; - } - - ll operator%(ll v) const { - if (v < 0) v = -v; - ll m = 0; - for (ll i = sz(a) - 1; i >= 0; --i) - m = (a[i] + m * base) % v; - return m * sign; - } - - void operator+=(const bigint& v) { - *this = *this + v; - } - void operator-=(const bigint& v) { - *this = *this - v; - } - void operator*=(const bigint& v) { - *this = *this * v; - } - void operator/=(const bigint& v) { - *this = *this / v; - } - - bool operator<(const bigint& v) const { - if (sign != v.sign) return sign < v.sign; - if (sz(a) != sz(v.a)) - return sz(a) * sign < sz(v.a) * v.sign; - for (ll i = sz(a) - 1; i >= 0; i--) - if (a[i] != v.a[i]) - return a[i] * sign < v.a[i] * sign; - return false; - } - - bool operator>(const bigint& v) const { - return v < *this; - } - bool operator<=(const bigint& v) const { - return !(v < *this); - } - bool operator>=(const bigint& v) const { - return !(*this < v); - } - bool operator==(const bigint& v) const { - return !(*this < v) && !(v < *this); - } - bool operator!=(const bigint& v) const { - return *this < v || v < *this; - } - - void trim() { - while (!a.empty() && !a.back()) a.pop_back(); - if (a.empty()) sign = 1; - } - - bool isZero() const { - return a.empty() || (sz(a) == 1 && a[0] == 0); - } - - bigint operator-() const { - bigint res = *this; - res.sign = -sign; - return res; - } - - bigint abs() const { - bigint res = *this; - res.sign *= res.sign; - return res; - } - - ll longValue() const { - ll res = 0; - for (ll i = sz(a) - 1; i >= 0; i--) - res = res * base + a[i]; - return res * sign; - } - - void read(const string& s) { - sign = 1; - a.clear(); - ll pos = 0; - while (pos < sz(s) && (s[pos] == '-' || s[pos] == '+')) { - if (s[pos] == '-') sign = -sign; - ++pos; - } - for (ll i = sz(s) - 1; i >= pos; i -= base_digits) { - ll x = 0; - for (ll j = max(pos, i - base_digits + 1); j <= i; j++) - x = x * 10 + s[j] - '0'; - a.push_back(x); - } - trim(); - } - - friend istream& operator>>(istream& stream, bigint& v) { - string s; - stream >> s; - v.read(s); - return stream; - } - - friend ostream& operator<<(ostream& stream, const bigint& v) { - if (v.sign == -1) stream << '-'; - stream << (v.a.empty() ? 0 : v.a.back()); - for (ll i = sz(v.a) - 2; i >= 0; --i) - stream << setw(base_digits) << setfill('0') << v.a[i]; - return stream; - } - - static vll karatsubaMultiply(const vll& a, const vll& b) { - ll n = sz(a); - vll res(n + n); - if (n <= 32) { - for (ll i = 0; i < n; i++) - for (ll j = 0; j < n; j++) - res[i + j] += a[i] * b[j]; - return res; - } - ll k = n >> 1; - vll a1(a.begin(), a.begin() + k); - vll a2(a.begin() + k, a.end()); - vll b1(b.begin(), b.begin() + k); - vll b2(b.begin() + k, b.end()); - vll a1b1 = karatsubaMultiply(a1, b1); - vll a2b2 = karatsubaMultiply(a2, b2); - for (ll i = 0; i < k; i++) a2[i] += a1[i]; - for (ll i = 0; i < k; i++) b2[i] += b1[i]; - vll r = karatsubaMultiply(a2, b2); - for (ll i = 0; i < sz(a1b1); i++) r[i] -= a1b1[i]; - for (ll i = 0; i < sz(a2b2); i++) r[i] -= a2b2[i]; - for (ll i = 0; i < sz(r); i++) res[i + k] += r[i]; - for (ll i = 0; i < sz(a1b1); i++) res[i] += a1b1[i]; - for (ll i = 0; i < sz(a2b2); i++) res[i + n] += a2b2[i]; - return res; - } - - bigint operator*(const bigint& v) const { - vll a(this->a.begin(), this->a.end()); - vll b(v.a.begin(), v.a.end()); - while (sz(a) < sz(b)) a.push_back(0); - while (sz(b) < sz(a)) b.push_back(0); - while (sz(a) & (sz(a) - 1)) - a.push_back(0), b.push_back(0); - vll c = karatsubaMultiply(a, b); - bigint res; - res.sign = sign * v.sign; - for (ll i = 0, carry = 0; i < sz(c); i++) { - ll cur = c[i] + carry; - res.a.push_back(cur % base); - carry = cur / base; - } - res.trim(); - return res; - } -}; diff --git a/math/binomial0.cpp b/math/binomial0.cpp deleted file mode 100644 index 896a0f1..0000000 --- a/math/binomial0.cpp +++ /dev/null @@ -1,14 +0,0 @@ -constexpr ll lim = 10'000'000; -ll fac[lim], inv[lim]; - -void precalc() { - fac[0] = inv[0] = 1; - for (int i = 1; i < lim; i++) fac[i] = fac[i-1] * i % mod; - inv[lim - 1] = multInv(fac[lim - 1], mod); - for (int i = lim - 1; i > 0; i--) inv[i-1] = inv[i] * i % mod; -} - -ll calc_binom(ll n, ll k) { - if (n < 0 || n < k || k < 0) return 0; - return (inv[n] * inv[n-k] % mod) * fac[k] % mod; -} diff --git a/math/binomial1.cpp b/math/binomial1.cpp deleted file mode 100644 index dab20b3..0000000 --- a/math/binomial1.cpp +++ /dev/null @@ -1,8 +0,0 @@ -ll calc_binom(ll n, ll k) { - if (k > n) return 0; - ll r = 1; - for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit - r *= n--, r /= d; - } - return r; -} diff --git a/math/binomial2.cpp b/math/binomial2.cpp deleted file mode 100644 index 4531505..0000000 --- a/math/binomial2.cpp +++ /dev/null @@ -1,32 +0,0 @@ -constexpr ll mod = 1'000'000'009; - -ll binomPPow(ll n, ll k, ll p) { - ll res = 1; - if (p > n) { - } else if (p > n - k || (p * p > n && n % p < k % p)) { - res *= p; - res %= mod; - } else if (p * p <= n) { - ll c = 0, tmpN = n, tmpK = k; - while (tmpN > 0) { - if (tmpN % p < tmpK % p + c) { - res *= p; - res %= mod; - c = 1; - } else c = 0; - tmpN /= p; - tmpK /= p; - }} - return res; -} - -ll calc_binom(ll n, ll k) { - if (k > n) return 0; - ll res = 1; - k = min(k, n - k); - for (ll i = 0; primes[i] <= n; i++) { - res *= binomPPow(n, k, primes[i]); - res %= mod; - } - return res; -} diff --git a/math/binomial3.cpp b/math/binomial3.cpp deleted file mode 100644 index f52337c..0000000 --- a/math/binomial3.cpp +++ /dev/null @@ -1,10 +0,0 @@ -ll calc_binom(ll n, ll k, ll p) { - assert(n < p) //wichtig: sonst falsch! - if (k > n) return 0; - ll x = k % 2 != 0 ? p-1 : 1; - for (ll c = p-1; c > n; c--) { - x *= c - k; x %= p; - x *= multInv(c, p); x %= p; - } - return x; -} diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp deleted file mode 100644 index ccbc5dc..0000000 --- a/math/chineseRemainder.cpp +++ /dev/null @@ -1,14 +0,0 @@ -struct CRT { - using lll = __int128; - lll M = 1, sol = 0; // Solution unique modulo M - bool hasSol = true; - - // Adds congruence x = a (mod m) - void add(ll a, ll m) { - auto [d, s, t] = extendedEuclid(M, m); - if((a - sol) % d != 0) hasSol = false; - lll z = M/d * s; - M *= m/d; - sol = (z % M * (a-sol) % M + sol + M) % M; - } -}; diff --git a/math/cycleDetection.cpp b/math/cycleDetection.cpp deleted file mode 100644 index 621af82..0000000 --- a/math/cycleDetection.cpp +++ /dev/null @@ -1,16 +0,0 @@ -void cycleDetection(ll x0, function f) { - ll a = x0, b = f(x0), length = 1; - for (ll power = 1; a != b; b = f(b), length++) { - if (power == length) { - power *= 2; - length = 0; - a = b; - }} - ll start = 0; - a = x0; b = x0; - for (ll i = 0; i < length; i++) b = f(b); - while (a != b) { - a = f(a); - b = f(b); - start++; -}} diff --git a/math/discreteLogarithm.cpp b/math/discreteLogarithm.cpp deleted file mode 100644 index d9227b9..0000000 --- a/math/discreteLogarithm.cpp +++ /dev/null @@ -1,14 +0,0 @@ -ll dlog(ll a, ll b, ll m) { - ll bound = sqrtl(m) + 1; //memory usage bound - map vals; - for (ll i = 0, e = 1; i < bound; i++, e = (e * a) % m) { - vals[e] = i; - } - ll fact = powMod(a, m - bound - 1, m); - - for (ll i = 0; i < m; i += bound, b = (b * fact) % m) { - if (vals.count(b)) { - return i + vals[b]; - }} - return -1; -} diff --git a/math/discreteNthRoot.cpp b/math/discreteNthRoot.cpp deleted file mode 100644 index 7201b2b..0000000 --- a/math/discreteNthRoot.cpp +++ /dev/null @@ -1,5 +0,0 @@ -ll root(ll a, ll b, ll m) { - ll g = findPrimitive(m); - ll c = dlog(powMod(g, a, m), b, m); //dLog @\sourceref{math/discreteLogarithm.cpp}@ - return c < 0 ? -1 : powMod(g, c, m); -} diff --git a/math/divisors.cpp b/math/divisors.cpp deleted file mode 100644 index 5afd4fb..0000000 --- a/math/divisors.cpp +++ /dev/null @@ -1,11 +0,0 @@ -ll countDivisors(ll n) { - ll res = 1; - for (ll i = 2; i * i * i <= n; i++) { - ll c = 0; - while (n % i == 0) {n /= i; c++;} - res *= c + 1; - } - if (isPrime(n)) res *= 2; - else if (n > 1) res *= isSquare(n) ? 3 : 4; - return res; -} diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp deleted file mode 100644 index ecf4a16..0000000 --- a/math/extendedEuclid.cpp +++ /dev/null @@ -1,6 +0,0 @@ -// a*x + b*y = ggt(a, b) -array extendedEuclid(ll a, ll b) { - if (a == 0) return {b, 0, 1}; - auto [d, x, y] = extendedEuclid(b % a, a); - return {d, y - (b / a) * x, x}; -} diff --git a/math/gauss.cpp b/math/gauss.cpp deleted file mode 100644 index 3e3b7aa..0000000 --- a/math/gauss.cpp +++ /dev/null @@ -1,36 +0,0 @@ -void normalLine(int line) { - double factor = mat[line][line]; - for (double& x : mat[line]) x /= factor; -} - -void takeAll(int n, int line) { - for (int i = 0; i < n; i++) { - if (i == line) continue; - double diff = mat[i][line]; - for (int j = 0; j <= n; j++) { - mat[i][j] -= diff * mat[line][j]; -}}} - -int gauss(int n) { - vector done(n, false); - for (int i = 0; i < n; i++) { - int swappee = i; // Sucht Pivotzeile für bessere Stabilität. - for (int j = 0; j < n; j++) { - if (done[j]) continue; - if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j; - } - swap(mat[i], mat[swappee]); - if (abs(mat[i][i]) > EPS) { - normalLine(i); - takeAll(n, i); - done[i] = true; - }} - // Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung. - for (int i = 0; i < n; i++) { - bool allZero = true; - for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS; - if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT; - if (allZero && abs(mat[i][n]) <= EPS) return MULTIPLE; - } - return UNIQUE; -} diff --git a/math/gcd-lcm.cpp b/math/gcd-lcm.cpp deleted file mode 100644 index a1c63c8..0000000 --- a/math/gcd-lcm.cpp +++ /dev/null @@ -1,2 +0,0 @@ -ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);} -ll lcm(ll a, ll b) {return a * (b / gcd(a, b));} diff --git a/math/goldenSectionSearch.cpp b/math/goldenSectionSearch.cpp deleted file mode 100644 index 20b15e8..0000000 --- a/math/goldenSectionSearch.cpp +++ /dev/null @@ -1,15 +0,0 @@ -ld gss(ld l, ld r, function f) { - ld inv = (sqrt(5.0l) - 1) / 2; - ld x1 = r - inv*(r-l), x2 = l + inv*(r-l); - ld f1 = f(x1), f2 = f(x2); - for (int i = 0; i < 200; i++) { - if (f1 < f2) { //change to > to find maximum - u = x2; x2 = x1; f2 = f1; - x1 = r - inv*(r-l); f1 = f(x1); - } else { - l = x1; x1 = x2; f1 = f2; - x2 = l + inv*(r-l); f2 = f(x2); - } - } - return l; -} diff --git a/math/inversions.cpp b/math/inversions.cpp deleted file mode 100644 index 9e47f9b..0000000 --- a/math/inversions.cpp +++ /dev/null @@ -1,9 +0,0 @@ -ll inversions(const vector& v) { - Tree> t; //ordered statistics tree @\sourceref{datastructures/pbds.cpp}@ - ll res = 0; - for (ll i = 0; i < sz(v); i++) { - res += i - t.order_of_key({v[i], i}); - t.insert({v[i], i}); - } - return res; -} diff --git a/math/inversionsMerge.cpp b/math/inversionsMerge.cpp deleted file mode 100644 index 8235b11..0000000 --- a/math/inversionsMerge.cpp +++ /dev/null @@ -1,27 +0,0 @@ -// Laufzeit: O(n*log(n)) -ll merge(vector& v, vector& left, vector& right) { - int a = 0, b = 0, i = 0; - ll inv = 0; - while (a < sz(left) && b < sz(right)) { - if (left[a] < right[b]) v[i++] = left[a++]; - else { - inv += sz(left) - a; - v[i++] = right[b++]; - } - } - while (a < sz(left)) v[i++] = left[a++]; - while (b < sz(right)) v[i++] = right[b++]; - return inv; -} - -ll mergeSort(vector &v) { // Sortiert v und gibt Inversionszahl zurück. - int n = sz(v); - vector left(n / 2), right((n + 1) / 2); - for (int i = 0; i < n / 2; i++) left[i] = v[i]; - for (int i = n / 2; i < n; i++) right[i - n / 2] = v[i]; - - ll result = 0; - if (sz(left) > 1) result += mergeSort(left); - if (sz(right) > 1) result += mergeSort(right); - return result + merge(v, left, right); -} diff --git a/math/kthperm.cpp b/math/kthperm.cpp deleted file mode 100644 index 899dff1..0000000 --- a/math/kthperm.cpp +++ /dev/null @@ -1,14 +0,0 @@ -vector kthperm(ll k, ll n) { - Tree t; - vector res(n); - for (ll i = 1; i <= n; k /= i, i++) { - t.insert(i - 1); - res[n - i] = k % i; - } - for (ll& x : res) { - auto it = t.find_by_order(x); - x = *it; - t.erase(it); - } - return res; -} diff --git a/math/legendre.cpp b/math/legendre.cpp deleted file mode 100644 index f08755f..0000000 --- a/math/legendre.cpp +++ /dev/null @@ -1,4 +0,0 @@ -ll legendre(ll a, ll p) { - ll s = powMod(a, p / 2, p); - return s < 2 ? s : -1ll; -} diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp deleted file mode 100644 index 7081fea..0000000 --- a/math/lgsFp.cpp +++ /dev/null @@ -1,26 +0,0 @@ -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 <= n; 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 diff --git a/math/linearCongruence.cpp b/math/linearCongruence.cpp deleted file mode 100644 index cdb5a37..0000000 --- a/math/linearCongruence.cpp +++ /dev/null @@ -1,5 +0,0 @@ -ll solveLinearCongruence(ll a, ll b, ll m) { - ll g = gcd(a, m); - if (b % g != 0) return -1; - return ((b / g) * multInv(a / g, m / g)) % (m / g); -} diff --git a/math/linearRecurence.cpp b/math/linearRecurence.cpp deleted file mode 100644 index 2501e64..0000000 --- a/math/linearRecurence.cpp +++ /dev/null @@ -1,33 +0,0 @@ -constexpr ll mod = 1'000'000'007; -vector modMul(const vector& a, const vector& b, - const vector& c) { - ll n = sz(c); - vector res(n * 2 + 1); - for (int i = 0; i <= n; i++) { //a*b - for (int j = 0; j <= n; j++) { - res[i + j] += a[i] * b[j]; - res[i + j] %= mod; - }} - for (int i = 2 * n; i > n; i--) { //res%c - for (int j = 0; j < n; j++) { - res[i - 1 - j] += res[i] * c[j]; - res[i - 1 - j] %= mod; - }} - res.resize(n + 1); - return res; -} - -ll kthTerm(const vector& f, const vector& c, ll k) { - assert(sz(f) == sz(c)); - vector tmp(sz(c) + 1), a(sz(c) + 1); - tmp[0] = a[1] = 1; //tmp = (x^k) % c - - for (k++; k > 0; k /= 2) { - if (k & 1) tmp = modMul(tmp, a, c); - a = modMul(a, a, c); - } - - ll res = 0; - for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; - return res % mod; -} diff --git a/math/linearSieve.cpp b/math/linearSieve.cpp deleted file mode 100644 index b029b9a..0000000 --- a/math/linearSieve.cpp +++ /dev/null @@ -1,49 +0,0 @@ -constexpr ll N = 10'000'000; -ll smallest[N], power[N], sieved[N]; -vector primes; - -//wird aufgerufen mit (p^k, p, k) für prime p -ll mu(ll pk, ll p, ll k) {return -(k == 1);} -ll phi(ll pk, ll p, ll k) {return pk - pk / p;} -ll div(ll pk, ll p, ll k) {return k+1;} -ll divSum(ll pk, ll p, ll k) {return (pk*p+1) / (p - 1);} -ll square(ll pk, ll p, ll k) {return k % 2 ? pk / p : pk;} -ll squareFree(ll pk, ll p, ll k) {return k % 2 ? pk : 1;} - -void sieve() { // O(N) - smallest[1] = power[1] = sieved[1] = 1; - for (ll i = 2; i < N; i++) { - if (smallest[i] == 0) { - primes.push_back(i); - for (ll pk = i, k = 1; pk < N; pk *= i, k++) { - smallest[pk] = i; - power[pk] = pk; - sieved[pk] = mu(pk, i, k); // Aufruf ändern! - }} - for (ll j = 0; i * primes[j] < N && primes[j] < smallest[i]; j++) { - ll k = i * primes[j]; - smallest[k] = power[k] = primes[j]; - sieved[k] = sieved[i] * sieved[primes[j]]; - } - if (i * smallest[i] < N && power[i] != i) { - ll k = i * smallest[i]; - smallest[k] = smallest[i]; - power[k] = power[i] * smallest[i]; - sieved[k] = sieved[power[k]] * sieved[k / power[k]]; -}}} - -ll naive(ll n) { // O(sqrt(n)) - ll res = 1; - for (ll p = 2; p * p <= n; p++) { - if (n % p == 0) { - ll pk = 1; - ll k = 0; - do { - n /= p; - pk *= p; - k++; - } while (n % p == 0); - res *= mu(pk, p, k); // Aufruf ändern! - }} - return res; -} diff --git a/math/longestIncreasingSubsequence.cpp b/math/longestIncreasingSubsequence.cpp deleted file mode 100644 index fcb63b4..0000000 --- a/math/longestIncreasingSubsequence.cpp +++ /dev/null @@ -1,17 +0,0 @@ -vector lis(vector& a) { - int n = sz(a), len = 0; - vector dp(n, INF), dp_id(n), prev(n); - for (int i = 0; i < n; i++) { - int pos = lower_bound(all(dp), a[i]) - dp.begin(); - dp[pos] = a[i]; - dp_id[pos] = i; - prev[i] = pos ? dp_id[pos - 1] : -1; - len = max(len, pos + 1); - } - // reconstruction - vector res(len); - for (int x = dp_id[len-1]; len--; x = prev[x]) { - res[len] = x; - } - return res; // indices of one LIS -} diff --git a/math/math.tex b/math/math.tex deleted file mode 100644 index c157e1b..0000000 --- a/math/math.tex +++ /dev/null @@ -1,535 +0,0 @@ -\section{Mathe} - -\begin{algorithm}{Zykel Erkennung} - \begin{methods} - \method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l} - \end{methods} - \sourcecode{math/cycleDetection.cpp} -\end{algorithm} - -\begin{algorithm}{Longest Increasing Subsequence} - \begin{itemize} - \item \code{lower\_bound} $\Rightarrow$ streng monoton - \item \code{upper\_bound} $\Rightarrow$ monoton - \end{itemize} - \sourcecode{math/longestIncreasingSubsequence.cpp} -\end{algorithm} - -\begin{algorithm}{Permutationen} - \begin{methods} - \method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)} - \end{methods} - \sourcecode{math/kthperm.cpp} - \begin{methods} - \method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)} - \end{methods} - \sourcecode{math/permIndex.cpp} -\end{algorithm} -\clearpage - -\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$} -%\vspace{-1.25em} -%\begin{multicols}{2} -\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)} -\sourcecode{math/modMulIterativ.cpp} -% \vfill\null\columnbreak -\method{powMod}{berechnet $a^b \bmod n$}{\log(b)} -\sourcecode{math/modPowIterativ.cpp} -%\end{multicols} -%\vspace{-2.75em} -\begin{itemize} - \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! -\end{itemize} - -\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} - \runtime{\log(a) + \log(b)} - \sourcecode{math/extendedEuclid.cpp} -\end{algorithm} - -\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$} -\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$ - -\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:} -\begin{itemize} - \item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit - $\alpha x + \beta m = 1$. - \item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$. - \item $x^{-1} :\equiv \alpha \bmod m$ -\end{itemize} -\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$. -% \sourcecode{math/multInv.cpp} -\sourcecode{math/shortModInv.cpp} - -\paragraph{Lemma von \textsc{Bézout}} -Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$. -Dann lassen sich wie folgt alle Lösungen berechnen: -\[ -\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right) -\] - -\paragraph{\textsc{Pell}-Gleichungen} -Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert. -Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen -sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: -\begin{align*} - x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\ - x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k -\end{align*} - -\begin{algorithm}{Lineare Kongruenz} - \begin{itemize} - \item Löst $ax\equiv b\pmod{m}$. - \item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt - also $g$ Lösungen modulo $m$. - \end{itemize} - \sourcecode{math/linearCongruence.cpp} -\end{algorithm} - -\begin{algorithm}{Chinesischer Restsatz} - \begin{itemize} - \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden. - \item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$: - \[ - x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d} - \qquad \text{mit} \qquad - d := \ggT(n, m) = yn + zm - \] - Formel kann auch für nicht teilerfremde Moduli verwendet werden. - Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung, - wenn $a\equiv~b \bmod \ggT(m, n)$. - In diesem Fall sind keine Faktoren - auf der linken Seite erlaubt. - \end{itemize} - \sourcecode{math/chineseRemainder.cpp} -\end{algorithm} - -\begin{algorithm}{Primzahltest \& Faktorisierung} - \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2} - \sourcecode{math/millerRabin.cpp} - \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}} - \sourcecode{math/rho.cpp} - %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}} - %\sourcecode{math/squfof.cpp} -\end{algorithm} - -\begin{algorithm}{Teiler} - \begin{methods} - \method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}} - \end{methods} - \sourcecode{math/divisors.cpp} -\end{algorithm} - -\begin{algorithm}{Numerisch Extremstelle bestimmen} - \sourcecode{math/goldenSectionSearch.cpp} -\end{algorithm} - -\begin{algorithm}{Numerisch Integrieren, Simpsonregel} - \sourcecode{math/simpson.cpp} -\end{algorithm} - -\begin{algorithm}{Diskreter Logarithmus} - \begin{methods} - \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)} - \end{methods} - \sourcecode{math/discreteLogarithm.cpp} -\end{algorithm} -%TODO -\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel} - \begin{methods} - \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)} - \end{methods} - Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$ - \sourcecode{math/discreteNthRoot.cpp} -\end{algorithm} - - -\begin{algorithm}{Primitivwurzeln} - \begin{itemize} - \item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$ - \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln - \item Sei $g$ Primitivwurzel modulo $n$. - Dann gilt:\newline - Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$. - \end{itemize} - \begin{methods} - \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)} - \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)} - \end{methods} - \sourcecode{math/primitiveRoot.cpp} -\end{algorithm} - -\begin{algorithm}{Linearessieb und Multiplikative Funktionen} - Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$. - - $\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen. - - \begin{methods} - \method{sieve}{berechnet Primzahlen und co.}{N} - \method{sieved}{Wert der endsprechenden Multiplikativen Funktion}{1} - - \method{naive}{Wert der endsprechenden Multiplikativen Funktion}{\sqrt{n}} - \end{methods} - \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}! - - \sourcecode{math/linearSieve.cpp} - \textbf{\textsc{Möbius}-Funtkion:} - \begin{itemize} - \item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat - \item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat - \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist - \end{itemize} - - \textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:} - \begin{itemize} - \item Zählt die relativ primen Zahlen $\leq n$. - \item $p$ prim, $k \in \mathbb{N}$: - $~\varphi(p^k) = p^k - p^{k - 1}$ - - \item \textbf{Euler's Theorem:} - Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$. - Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}: - $a^{m} \equiv a \pmod{m}$ - \end{itemize} -\end{algorithm} - -\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} - \begin{itemize} - \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) - \end{itemize} - \begin{methods} - \method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))} - \method{isPrime}{prüft ob Zahl prim ist}{1} - \end{methods} - \sourcecode{math/primeSieve.cpp} -\end{algorithm} - -\begin{algorithm}{\textsc{Möbius}-Inversion} - \begin{itemize} - \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$. - Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. - \item $\sum\limits_{d \vert n}\mu(d) = - \begin{cases*} - 1 & falls $n = 1$\\ - 0 & sonst - \end{cases*}$ - \end{itemize} - \textbf{Beispiel Inklusion/Exklusion:} - Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline - \textbf{Lösung}: - Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$. - Es gibt $2^{[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten. - Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$. - %\sourcecode{math/mobius.cpp} -\end{algorithm} - -\optional{ -\columnbreak -\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion} -\begin{itemize} - \item Zählt die relativ primen Zahlen $\leq n$. - - \item Multiplikativ: - $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$ - - \item $p$ prim, $k \in \mathbb{N}$: - $~\varphi(p^k) = p^k - p^{k - 1}$ - - \item \textbf{\textsc{Euler}'s Theorem:} - Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$. - Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}: - $a^{m} \equiv a \pmod{m}$ -\end{itemize} -\sourcecode{math/phi.cpp} -} - -\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} - Multipliziert Polynome $A$ und $B$. - \begin{itemize} - \item $\deg(A \cdot B) = \deg(A) + \deg(B)$ - \item Vektoren \code{a} und \code{b} müssen mindestens Größe - $\deg(A \cdot B) + 1$ haben. - Größe muss eine Zweierpotenz sein. - \item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))} - \item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$ - \end{itemize} - %\lstinputlisting{math/fft.cpp} - %\lstinputlisting{math/ntt.cpp} - %\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code - \sourcecode{math/transforms/fft.cpp} - \sourcecode{math/transforms/ntt.cpp} - \vfill\null - \columnbreak - \sourcecode{math/transforms/bitwiseTransforms.cpp} - Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!) - \sourcecode{math/transforms/fftMul.cpp} -\end{algorithm} - -\begin{algorithm}{Operations on Formal Power Series} - \sourcecode{math/transforms/seriesOperations.cpp} -\end{algorithm} - -\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} -\method{gauss}{löst LGS}{n^3} -\sourcecode{math/lgsFp.cpp} - -\subsection{LGS über $\boldsymbol{\mathbb{R}}$} -\method{gauss}{löst LGS}{n^3} -\sourcecode{math/gauss.cpp} - -\begin{algorithm}{\textsc{Legendre}-Symbol} - Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: - \begin{align*} - \legendre{a}{p} &= - \begin{cases*} - \hphantom{-}0 & falls $p~\vert~a$ \\[-1ex] - \hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex] - -1 & sonst - \end{cases*} \\ - \legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &= - \begin{cases*} - \hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex] - -1 & falls $p \equiv 3 \bmod 4$ - \end{cases*} \\ - \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &= - \begin{cases*} - \hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex] - -1 & falls $p \equiv \pm 3 \bmod 8$ - \end{cases*} - \end{align*} - \begin{align*} - \legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} && - \legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p - \end{align*} - \sourcecode{math/legendre.cpp} -\end{algorithm} - -\optional{ -\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} -\begin{methods} - \method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))} - \method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???} - \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}} -\end{methods} -\sourcecode{math/piLehmer.cpp} -} - -\begin{algorithm}{Lineare Rekurrenz} - \begin{methods} - \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2} - \method{}{aus den ersten $2n$ Werte}{} - \end{methods} - \sourcecode{math/berlekampMassey.cpp} - Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Rekurrenz. - - \begin{methods} - \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2} - \end{methods} - \sourcecode{math/linearRecurence.cpp} - Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: - $$\renewcommand\arraystretch{1.5} - \setlength\arraycolsep{3pt} - \begin{pmatrix} - c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\ - 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\ - 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\ - \smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\ - 0 & \smash{\cdots} & 0 & 1 & 0 \\ - \end{pmatrix}^k - \times~~ - \begin{pmatrix} - f(n-1) \\ - f(n-2) \\ - \smash{\vdots} \\ - \smash{\vdots} \\ - f(0) \\ - \end{pmatrix} - ~~=~~ - \begin{pmatrix} - f(n-1+k) \\ - f(n-2+k) \\ - \smash{\vdots} \\ - \smash{\vdots} \\ - f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\ - \end{pmatrix} - $$ -\end{algorithm} - -\begin{algorithm}{Matrix-Exponent} - \begin{methods} - \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3} - \method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2} - \end{methods} - \sourcecode{math/matrixPower.cpp} -\end{algorithm} - -\begin{algorithm}{Inversionszahl} - \sourcecode{math/inversions.cpp} -\end{algorithm} - -\subsection{Satz von \textsc{Sprague-Grundy}} -Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu: -\[ -g\left(X\right) := \min\left\{ -\mathbb{Z}_0^+ \setminus -\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\} -\right\} -\] -$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\ -Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$. - -\subsection{Kombinatorik} - -\paragraph{Wilsons Theorem} -A number $n$ is prime if and only if -$(n-1)!\equiv -1\bmod{n}$.\\ -($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$) -\begin{align*} - (n-1)!\equiv\begin{cases} - -1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\ - \hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\ - \hphantom{-}0\bmod{n},&\mathrm{sonst} - \end{cases} -\end{align*} - -\paragraph{\textsc{Zeckendorfs} Theorem} -Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer -verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei -aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\ -\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch -hineinpasst. - -\paragraph{\textsc{Lucas}-Theorem} -Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung), -so gilt -\vspace{-0.75\baselineskip} -\[ - \binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}. -\] - -%\begin{algorithm}{Binomialkoeffizienten} -\paragraph{Binomialkoeffizienten} - Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge. - - \begin{methods} - \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}} - \method{calc\_binom}{berechnet Binomialkoeffizient}{1} - \end{methods} - \sourcecode{math/binomial0.cpp} - Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$ - - \begin{methods} - \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} - \end{methods} - \sourcecode{math/binomial1.cpp} - - \begin{methods} - \method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n} - \end{methods} - \sourcecode{math/binomial3.cpp} - -% \begin{methods} -% \method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n} -% \end{methods} -% \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$ -% \sourcecode{math/binomial2.cpp} -%\end{algorithm} - -\paragraph{\textsc{Catalan}-Zahlen} -\begin{itemize} - \item Die \textsc{Catalan}-Zahl $C_n$ gibt an: - \begin{itemize} - \item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten. - \item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren. - \item Anzahl der korrekten Klammerungen von $n+1$ Faktoren. - \item Anzahl Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren. - \item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in - einem $n \times n$-Gitter, die nicht die Diagonale kreuzen. - \end{itemize} -\end{itemize} -\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = -\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} \cdot C_{n-1}\] -\begin{itemize} - \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2} - \item Formel $2$ und $3$ erlauben Berechnung in \runtime{n} -\end{itemize} - -\paragraph{\textsc{Catalan}-Convolution} -\begin{itemize} - \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $(^k$ beginnen. -\end{itemize} -\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} = -\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)\cdot(2n+k)}{n(n+k+1)} \cdot C_{n-1}\] - -\paragraph{\textsc{Euler}-Zahlen 1. Ordnung} -Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen. -Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen. -Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt. -\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad -\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}= -\sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\] -\begin{itemize} - \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2} - \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)} -\end{itemize} - -\paragraph{\textsc{Euler}-Zahlen 2. Ordnung} -Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen. -\[\eulerII{n}{0} = 1 \qquad\eulerII{n}{n} = 0 \qquad\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}\] -\begin{itemize} - \item Formel erlaubt Berechnung ohne Division in \runtime{n^2} -\end{itemize} - -\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung} -Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen. -Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden. -\[\stirlingI{0}{0} = 1 \qquad -\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad -\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\] -\begin{itemize} - \item Formel erlaubt berechnung ohne Division in \runtime{n^2} -\end{itemize} -\[\sum_{k=0}^{n}\pm\stirlingI{n}{k}x^k=x(x-1)(x-2)\cdots(x-n+1)\] -\begin{itemize} - \item Berechne Polynom mit FFT und benutzte betrag der Koeffizienten \runtime{n\log(n)^2} (nur ungefähr gleich große Polynome zusammen multiplizieren beginnend mit $x-k$) -\end{itemize} - -\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung} -Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen. -Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen. -Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht. -\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad -\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} = -\frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\] -\begin{itemize} - \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2} - \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)} -\end{itemize} - -\paragraph{\textsc{Bell}-Zahlen} -Anzahl der Partitionen von $\{1, \ldots, n\}$. -Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$. -\[B_1 = 1 \qquad -B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k} -= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\] - -\paragraph{Partitions} -Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden. -Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. -\begin{align*} - p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\ - p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt] - p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg) -\end{align*} -\begin{itemize} - \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$. - \item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$. -\end{itemize} - -\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}} -\input{math/tables/twelvefold} - -%\input{math/tables/numbers} - -\begin{algorithm}[optional]{Big Integers} - \sourcecode{math/bigint.cpp} -\end{algorithm} diff --git a/math/matrixPower.cpp b/math/matrixPower.cpp deleted file mode 100644 index 05e29f6..0000000 --- a/math/matrixPower.cpp +++ /dev/null @@ -1,16 +0,0 @@ -vector pows; - -void precalc(mat m) { - pows = {mat(1), m}; - for (int i = 1; i < 60; i++) pows.push_back(pows[i] * pows[i]); -} - -ll calc(int x, int y, ll b) { - vector v(pows[0].m.size()); - v[x] = 1; - for (ll i = 1; b > 0; i++) { - if (b & 1) v = pows[i] * v; - b /= 2; - } - return v[y]; -} diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp deleted file mode 100644 index cb27d29..0000000 --- a/math/millerRabin.cpp +++ /dev/null @@ -1,19 +0,0 @@ -constexpr ll bases32[] = {2, 7, 61}; -constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, - 9780504, 1795265022}; -bool isPrime(ll n) { - if (n < 2 || n % 2 == 0) return n == 2; - ll d = n - 1, j = 0; - while (d % 2 == 0) d /= 2, j++; - for (ll a : bases64) { - if (a % n == 0) continue; - ll v = powMod(a, d, n); //with mulmod or int128 - if (v == 1 || v == n - 1) continue; - for (ll i = 1; i <= j; i++) { - v = ((lll)v * v) % n; - if (v == n - 1 || v <= 1) break; - } - if (v != n - 1) return false; - } - return true; -} diff --git a/math/mobius.cpp b/math/mobius.cpp deleted file mode 100644 index 3fb4d9e..0000000 --- a/math/mobius.cpp +++ /dev/null @@ -1,21 +0,0 @@ -ll mu(ll n) { // Laufzeit: O(sqrt(n)); - ll res = 1; - for (ll i = 2; i * i <= n; i++) { - if (n % i == 0) { // Optimierung: Nur Primzahlen - if (n % (i * i) == 0) return 0; - res *= -1; - n /= i; - }} - return n > 1 ? -res : res; -} - -// berechnet Möbiusfunktion. Laufzeit: O(N*log(log(N))) -vector mu(n + 1, 1); -for (ll i = 2; i <= n; i++) { - if (mu[i] == 1) { - for (ll j = i; j <= n; j += i) mu[j] *= -2; - for (ll j = i*i; j <= n; j += i*i) mu[j] = 0; - } - // log2(abs(mu[i])) = number of primes - mu[i] = (mu[i] > 0) - (mu[i] < 0); -} diff --git a/math/modExp.cpp b/math/modExp.cpp deleted file mode 100644 index 2329a94..0000000 --- a/math/modExp.cpp +++ /dev/null @@ -1,6 +0,0 @@ -ll powMod(ll a, ll b, ll n) { - if(b == 0) return 1; - if(b == 1) return a % n; - if(b & 1) return (powMod(a, b - 1, n) * a) % n; - else return powMod((a * a) % n, b / 2, n); -} diff --git a/math/modMulIterativ.cpp b/math/modMulIterativ.cpp deleted file mode 100644 index 611f09a..0000000 --- a/math/modMulIterativ.cpp +++ /dev/null @@ -1,9 +0,0 @@ -ll mulMod(ll a, ll b, ll n) { - ll res = 0; - while (b > 0) { - if (b & 1) res = (a + res) % n; - a = (a * 2) % n; - b /= 2; - } - return res; -} diff --git a/math/modPowIterativ.cpp b/math/modPowIterativ.cpp deleted file mode 100644 index 0dc3fb1..0000000 --- a/math/modPowIterativ.cpp +++ /dev/null @@ -1,9 +0,0 @@ -ll powMod(ll a, ll b, ll n) { - ll res = 1; - while (b > 0) { - if (b & 1) res = (a * res) % n; - a = (a * a) % n; - b /= 2; - } - return res; -} diff --git a/math/modSqrt.cpp b/math/modSqrt.cpp deleted file mode 100644 index 367c6c7..0000000 --- a/math/modSqrt.cpp +++ /dev/null @@ -1,23 +0,0 @@ -ll sqrtMod(ll a, ll p) { - assert(powMod(a, (p + 1)/2, p) == 1); //a ist ein quadrat mod p? - if (p % 4 == 3) return powMod(a, (p + 1)/2, p); - if (p % 8 == 5) return powMod(a, (p + 3)/8, p); - ll s = p - 1; - ll r = 0; - while (s % 2 == 0) s /= 2, r++; - ll n = 2; - while (powMod(n, (p - 1)/2, p) != p - 1) n++; - ll x = powMod(a, (s + 1)/2, p); - ll b = powMod(a, s, p); - ll g = powMod(n, s, p); - while (true) { - ll t = b; - ll m = 0; - for (;m < r && t != 1; m++) t = (t * t) % p; - if (t == 1) return x; - ll gs = powMod(g, 1ll << (r - m - 1), p); - g = (gs * gs) % p; - x = (x * gs) % p; - b = (b * g) % p; - r = m; -}} diff --git a/math/multInv.cpp b/math/multInv.cpp deleted file mode 100644 index 647dc2d..0000000 --- a/math/multInv.cpp +++ /dev/null @@ -1,4 +0,0 @@ -ll multInv(ll x, ll m) { - auto [d, a, b] = extendedEuclid(x, m); // Implementierung von oben. - return ((a % m) + m) % m; -} diff --git a/math/permIndex.cpp b/math/permIndex.cpp deleted file mode 100644 index 4cffc12..0000000 --- a/math/permIndex.cpp +++ /dev/null @@ -1,13 +0,0 @@ -ll permIndex(vector v) { - Tree t; - reverse(all(v)); - for (ll& x : v) { - t.insert(x); - x = t.order_of_key(x); - } - ll res = 0; - for (int i = sz(v); i > 0; i--) { - res = res * i + v[i - 1]; - } - return res; -} diff --git a/math/phi.cpp b/math/phi.cpp deleted file mode 100644 index 482a139..0000000 --- a/math/phi.cpp +++ /dev/null @@ -1,21 +0,0 @@ -ll phi(ll n) { // Laufzeit: O(sqrt(n)) - // Optimierung: Falls n prim, n - 1 zurückgeben - ll result = n; - for(ll i = 2; i * i <= n; ++i) { - if(n % i == 0) { // Optimierung: Nur Primzahlen - while(n % i == 0) n /= i; - result -= result / i; - }} - if(n > 1) result -= result / n; - return result; -} - -// Sieb, falls alle Werte benötigt werden. -// Laufzeit: O(N*log(log(N))) -vector phi(n + 1); -for (int i = 1; i <= n; i++) phi[i] = i; -for (int i = 2; i <= n; i++) if (phi[i] == i) { - for (int j = i; j <= n; j += i) { - phi[j] /= i; - phi[j] *= i - 1; -}} diff --git a/math/piLegendre.cpp b/math/piLegendre.cpp deleted file mode 100644 index 21b974b..0000000 --- a/math/piLegendre.cpp +++ /dev/null @@ -1,23 +0,0 @@ -constexpr ll cache = 500; // requires O(cache^3) -vector> memo(cache * cache, vector(cache)); - -ll pi(ll n); - -ll phi(ll n, ll k) { - if (n <= 1 || k < 0) return 0; - if (n <= primes[k]) return n - 1; - if (n < N && primes[k] * primes[k] > n) return n - pi(n) + k; - bool ok = n < cache * cache; - if (ok && memo[n][k] > 0) return memo[n][k]; - ll res = n/primes[k] - phi(n/primes[k], k - 1) + phi(n, k - 1); - if (ok) memo[n][k] = res; - return res; -} - -ll pi(ll n) { - if (n < N) { // implement this as O(1) lookup for speedup! - return distance(primes.begin(), upper_bound(all(primes), n)); - } else { - ll k = pi(sqrtl(n) + 1); - return n - phi(n, k) + k; -}} diff --git a/math/piLehmer.cpp b/math/piLehmer.cpp deleted file mode 100644 index 56c172d..0000000 --- a/math/piLehmer.cpp +++ /dev/null @@ -1,52 +0,0 @@ -constexpr ll cacheA = 2 * 3 * 5 * 7 * 11 * 13 * 17; -constexpr ll cacheB = 7; -ll memoA[cacheA + 1][cacheB + 1]; -ll memoB[cacheB + 1]; -ll memoC[N]; - -void init() { - primeSieve(); // code from above - for (ll i = 0; i < N; i++) { - memoC[i] = memoC[i - 1]; - if (isPrime(i)) memoC[i]++; - } - memoB[0] = 1; - for(ll i = 0; i <= cacheA; i++) memoA[i][0] = i; - for(ll i = 1; i <= cacheB; i++) { - memoB[i] = primes[i - 1] * memoB[i - 1]; - for(ll j = 1; j <= cacheA; j++) { - memoA[j][i] = memoA[j][i - 1] - memoA[j / - primes[i - 1]][i - 1]; -}}} - -ll phi(ll n, ll k) { - if(k == 0) return n; - if(k <= cacheB) - return memoA[n % memoB[k]][k] + - (n / memoB[k]) * memoA[memoB[k]][k]; - if(n <= primes[k - 1]*primes[k - 1]) return memoC[n] - k + 1; - if(n <= primes[k - 1]*primes[k - 1]*primes[k - 1] && n < N) { - ll b = memoC[(ll)sqrtl(n)]; - ll res = memoC[n] - (b + k - 2) * (b - k + 1) / 2; - for(ll i = k; i < b; i++) res += memoC[n / primes[i]]; - return res; - } - return phi(n, k - 1) - phi(n / primes[k - 1], k - 1); -} - -ll pi(ll n) { - if (n < N) return memoC[n]; - ll a = pi(sqrtl(sqrtl(n))); - ll b = pi(sqrtl(n)); - ll c = pi(cbrtl(n)); - ll res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2; - for (ll i = a; i < b; i++) { - ll w = n / primes[i]; - res -= pi(w); - if (i > c) continue; - ll bi = pi(sqrtl(w)); - for (ll j = i; j < bi; j++) { - res -= pi(w / primes[j]) - j; - }} - return res; -} diff --git a/math/polynomial.cpp b/math/polynomial.cpp deleted file mode 100644 index 44f6207..0000000 --- a/math/polynomial.cpp +++ /dev/null @@ -1,65 +0,0 @@ -struct poly { - vector data; - - poly(int deg = 0) : data(max(1, deg)) {} - poly(initializer_list _data) : data(_data) {} - - int size() const {return sz(data);} - - void trim() { - for (ll& x : data) x = (x % mod + mod) % mod; - while (size() > 1 && data.back() == 0) data.pop_back(); - } - - ll& operator[](int x) {return data[x];} - const ll& operator[](int x) const {return data[x];} - - ll operator()(int x) const { - ll res = 0; - for (int i = size() - 1; i >= 0; i--) - res = (res * x + data[i]) % mod; - return res % mod; - } - - poly& operator+=(const poly& o) { - if (size() < o.size()) data.resize(o.size()); - for (int i = 0; i < o.size(); i++) - data[i] = (data[i] + o[i]) % mod; - return *this; - } - - poly operator*(const poly& o) const { - poly res(size() + o.size() - 1); - for (int i = 0; i < size(); i++) { - for (int j = 0; j < o.size(); j++) { - res[i + j] += (data[i] * o[j]) % mod; - }} - res.trim(); - return res; - } - - //return p(x+a) - poly operator<<(ll a) const { - poly res(size()); - for (int i = size() - 1; i >= 0; i--) { - for (int j = size() - i - 1; j >= 1; j--) - res[j] = (res[j] * a + res[j - 1]) % mod; - res[0] = (res[0] * a + res[i]) % mod; - } - return res; - } - - pair divmod(const poly& d) const { - int i = size() - d.size(); - poly s(i + 1), r = *this; - ll inv = multInv(d.data.back(), mod); - for (; i >= 0; i--) { - s[i] = (r.data.back() * inv) % mod; - r.data.pop_back(); - for (int j = 0; i + j < r.size(); j++) { - r[i + j] = (r.data[i + j] - s[i] * d[j]) % mod; - }} - s.trim(); r.trim(); - return {s, r}; - } -}; diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp deleted file mode 100644 index 1b0f514..0000000 --- a/math/primeSieve.cpp +++ /dev/null @@ -1,16 +0,0 @@ -constexpr ll N = 100'000'000; -bitset isNotPrime; -vector primes = {2}; - -bool isPrime(ll x) { - if (x < 2 || x % 2 == 0) return x == 2; - else return !isNotPrime[x / 2]; -} - -void primeSieve() { - for (ll i = 3; i < N; i += 2) {// i * i < N reicht für isPrime - if (!isNotPrime[i / 2]) { - primes.push_back(i); // optional - for (ll j = i * i; j < N; j+= 2 * i) { - isNotPrime[j / 2] = 1; -}}}} diff --git a/math/primitiveRoot.cpp b/math/primitiveRoot.cpp deleted file mode 100644 index 464bdb3..0000000 --- a/math/primitiveRoot.cpp +++ /dev/null @@ -1,23 +0,0 @@ -bool isPrimitive(ll g, ll n, ll phi, map phiFacs) { - if (g == 1) return n == 2; - for (auto [f, _] : phiFacs) - if (powMod(g, phi / f, n) == 1) return false; - return true; -} - -bool isPrimitive(ll g, ll n) { - ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 - map phiFacs; - factor(phin, phiFacs); - return isPrimitive(g, n, phin, phiFacs); -} - -ll findPrimitive(ll n) { - ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 - map phiFacs; - factor(phin, phiFacs); - //auch zufällige Reihenfolge möglich! - for (ll res = 1; res < n; res++) - if (isPrimitive(res, n, phin, phiFacs)) return res; - return -1; -} diff --git a/math/rho.cpp b/math/rho.cpp deleted file mode 100644 index 7885196..0000000 --- a/math/rho.cpp +++ /dev/null @@ -1,19 +0,0 @@ -using lll = __int128; -ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. - if (n % 2 == 0) return 2; - ll x = 0, y = 0, prd = 2, i = n/2 + 7; - auto f = [&](lll x){return (x * x + i) % n;}; - for (ll t = 30, i = n/2 + 7; t % 40 || gcd(prd, n) == 1; t++) { - if (x == y) x = ++i, y = f(x); - if (ll q = (lll)prd * abs(x-y) % n; q) prd = q; - x = f(x); y = f(f(y)); - } - return gcd(prd, n); -} - -void factor(ll n, map& facts) { - if (n == 1) return; - if (isPrime(n)) {facts[n]++; return;} - ll f = rho(n); - factor(n / f, facts); factor(f, facts); -} diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp deleted file mode 100644 index 244bacf..0000000 --- a/math/shortModInv.cpp +++ /dev/null @@ -1,3 +0,0 @@ -ll multInv(ll x, ll m) { // x^{-1} mod m - return 1 < x ? m - inv(m % x, x) * m / x : 1; -} diff --git a/math/simpson.cpp b/math/simpson.cpp deleted file mode 100644 index a99b911..0000000 --- a/math/simpson.cpp +++ /dev/null @@ -1,12 +0,0 @@ -double f(double x) {return x;} - -double simps(double a, double b) { - return (f(a) + 4.0 * f((a + b) / 2.0) + f(b)) * (b - a) / 6.0; -} - -double integrate(double a, double b) { - double m = (a + b) / 2.0; - double l = simps(a, m), r = simps(m, b), tot = simps(a, b); - if (abs(l + r - tot) < EPS) return tot; - return integrate(a, m) + integrate(m, b); -} diff --git a/math/sqrtModCipolla.cpp b/math/sqrtModCipolla.cpp deleted file mode 100644 index 12bc590..0000000 --- a/math/sqrtModCipolla.cpp +++ /dev/null @@ -1,13 +0,0 @@ -bool isSquare(ll x, ll p){ - return powMod(x, p/2, p) != p-1; -} - -// Teste vorher, ob sqrt(n) mod p existiert! -ll sqrtMod(ll n, ll p){ - if(n == 0) return 0; - ll r0 = 1, r1 = 0, b0 = 1, b1 = 1, w; - while(isSquare(w=(b0*b0-n+p)%p, p)) b0 = rng()%p; - for(ll e = (p+1)/2; e; e /= 2, tie(b0, b1) = pair((b0*b0 + b1*b1%p*w)%p, 2*b0*b1%p)) - if(e & 1) tie(r0, r1) = pair((r0*b0 + r1*b1%p*w)%p, (r0*b1 + b0*r1)%p); - return r0; -} diff --git a/math/squfof.cpp b/math/squfof.cpp deleted file mode 100644 index 1cb97de..0000000 --- a/math/squfof.cpp +++ /dev/null @@ -1,89 +0,0 @@ -using lll = __int128; - -constexpr lll multipliers[] = {1, 3, 5, 7, - 11, 3*5, 3*7, 3*11, - 5*7, 5*11, 7*11, - 3*5*7, 3*5*11, 3*7*11, - 5*7*11, 3*5*7*11}; - -lll root(lll x) { - lll r = sqrtl(x); - while(r*r < x) r++; - while(r*r > x) r--; - return r; -} - -lll croot(lll x) { - lll r = cbrtl(x); - while(r*r*r < x) r++; - while(r*r*r > x) r--; - return r; -} - -lll squfof(lll N) { - lll s = croot(N); - if (s*s*s == N) return s; - s = root(N); - if (s*s == N) return s; - for (lll k : multipliers) { - lll D = k * N; - lll Po, P, Pprev, q, b, r, i; - Po = Pprev = P = root(D); - lll Qprev = 1; - lll Q = D - Po*Po; - lll L = 2 * root(2 * s); - lll B = 3 * L; - for (i = 2; i < B; i++) { - b = (Po + P) / Q; - P = b*Q - P; - q = Q; - Q = Qprev + b * (Pprev - P); - r = root(Q); - if (!(i & 1) && r*r == Q) break; - Qprev = q; - Pprev = P; - } - if (i >= B) continue; - b = (Po - P) / r; - Pprev = P = b*r + P; - Qprev = r; - Q = (D-Pprev*Pprev)/Qprev; - i = 0; - do { - b = (Po + P) / Q; - Pprev = P; - P = b*Q - P; - q = Q; - Q = Qprev + b * (Pprev - P); - Qprev = q; - i++; - } while(P != Pprev); - r = gcd(N, Qprev); - if (r != 1 && r != N) return r; - } - exit(1);//try fallback to pollard rho -} - -constexpr lll trialLim = 5'000; - -void factor(lll n, map& facts) { - for (lll i = 2; i * i <= n && i <= trialLim; i++) { - while (n % i == 0) { - facts[i]++; - n /= i; - }} - if (n > 1 && n < trialLim * trialLim) { - facts[n]++; - } else { - vector todo = {n}; - while (!todo.empty()) { - lll c = todo.back(); - todo.pop_back(); - if (c == 1) continue; - if (isPrime(c)) { - facts[c]++; - } else { - lll d = squfof(c); - todo.push_back(d); - todo.push_back(c / d); -}}}} diff --git a/math/tables.tex b/math/tables.tex deleted file mode 100644 index 53f3758..0000000 --- a/math/tables.tex +++ /dev/null @@ -1,18 +0,0 @@ -\enlargethispage{0.2cm} -\begin{multicols*}{2} - \input{math/tables/binom} - \vfill - \input{math/tables/composite} - \vfill - \input{math/tables/platonic} - \vfill - \input{math/tables/series} - - \columnbreak - - \input{math/tables/probability} - \vfill - \input{math/tables/stuff} - \vfill - \input{math/tables/nim} -\end{multicols*} diff --git a/math/tables/binom.tex b/math/tables/binom.tex deleted file mode 100644 index 878a6b0..0000000 --- a/math/tables/binom.tex +++ /dev/null @@ -1,28 +0,0 @@ -\begin{tabularx}{\linewidth}{|XXXX|} - \hline - \multicolumn{4}{|c|}{Binomialkoeffizienten} \\ - \hline - \multicolumn{4}{|c|}{ - $\frac{n!}{k!(n - k)!} \hfill=\hfill - \binom{n}{k} \hfill=\hfill - \binom{n}{n - k} \hfill=\hfill - \frac{n}{k}\binom{n - 1}{k - 1} \hfill=\hfill - \frac{n-k+1}{k}\binom{n}{k - 1} \hfill=\hfill - \binom{n - 1}{k} + \binom{n - 1}{k - 1} \hfill=\hfill - (-1)^k \binom{k - n - 1}{k} \hfill\approx\hfill - 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$ - } \\ - \grayhline - - $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ & - $\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ & - $\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ & - $\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\ - - $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ & - $\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ & - \multicolumn{2}{l|}{ - $\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ - }\\ - \hline -\end{tabularx} diff --git a/math/tables/composite.tex b/math/tables/composite.tex deleted file mode 100644 index 8e14b2e..0000000 --- a/math/tables/composite.tex +++ /dev/null @@ -1,27 +0,0 @@ - -\begin{tabularx}{\linewidth}{|r||r|r||r|r|r||C|} - \hline - \multicolumn{7}{|c|}{Important Numbers} \\ - \hline - $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & \\ - \hline - 1 & 6 & 4 & $-3$ & $+1$ & 4 & \\ - 2 & 60 & 12 & $-3$ & $+1$ & 25 & \\ - 3 & 840 & 32 & $-3$ & $+9$ & 168 & \\ - 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & \\ - 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & \\ - 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & \\ - 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & \\ - 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & \\ - 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & \\ - 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & \\ - 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & \\ - 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & \\ - 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & \\ - 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & \\ - 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & \\ - 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & \\ - 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & \\ - 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & \\ - \hline -\end{tabularx} diff --git a/math/tables/nim.tex b/math/tables/nim.tex deleted file mode 100644 index 8490d42..0000000 --- a/math/tables/nim.tex +++ /dev/null @@ -1,96 +0,0 @@ -\begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|} - \hline - \multicolumn{2}{|c|}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\ - \hline - Beschreibung & - Strategie \\ - \hline - - $M = [\mathit{pile}_i]$\newline - $[x] := \{1, \ldots, x\}$& - $\mathit{SG} = \oplus_{i = 1}^n \mathit{pile}_i$\newline - \ding{182} Nimm von einem Stapel, sodass $\mathit{SG}$ $0$ wird.\newline - \ding{183} Genauso. - Außer: Bleiben nur noch Stapel der Größe $1$, erzeuge ungerade Anzahl solcher Stapel.\\ - \hline - - $M = \{a^m \mid m \geq 0\}$ & - $a$ ungerade: $\mathit{SG}_n = n \% 2$\newline - $a$ gerade:\newline - $\mathit{SG}_n = 2$, falls $n \equiv a \bmod (a + 1) $\newline - $\mathit{SG}_n = n \% (a + 1) \% 2$, sonst.\\ - \hline - - $M_{\text{\ding{172}}} = \left[\frac{\mathit{pile}_i}{2}\right]$\newline - $M_{\text{\ding{173}}} = - \left\{\left\lceil\frac{\mathit{pile}_i}{2}\right\rceil,~ - \mathit{pile}_i\right\}$ & - \ding{172} - $\mathit{SG}_{2n} = n$, - $\mathit{SG}_{2n+1} = \mathit{SG}_n$\newline - \ding{173} - $\mathit{SG}_0 = 0$, - $\mathit{SG}_n = [\log_2 n] + 1$ \\ - \hline - - $M_{\text{\ding{172}}} = \text{Teiler von $\mathit{pile}_i$}$\newline - $M_{\text{\ding{173}}} = \text{echte Teiler von $\mathit{pile}_i$}$ & - \ding{172} - $\mathit{SG}_0 = 0$, - $\mathit{SG}_n = \mathit{SG}_{\text{\ding{173},n}} + 1$\newline - \ding{173} - $\mathit{ST}_1 = 0$, - $\mathit{SG}_n = \text{\#Nullen am Ende von $n_{bin}$}$\\ - \hline - - $M_{\text{\ding{172}}} = [k]$\newline - $M_{\text{\ding{173}}} = S$, ($S$ endlich)\newline - $M_{\text{\ding{174}}} = S \cup \{\mathit{pile}_i\}$ & - $\mathit{SG}_{\text{\ding{172}}, n} = n \bmod (k + 1)$\newline - \ding{182} Niederlage bei $\mathit{SG} = 0$\newline - \ding{183} Niederlage bei $\mathit{SG} = 1$\newline - $\mathit{SG}_{\text{\ding{174}}, n} = \mathit{SG}_{\text{\ding{173}}, n} + 1$\\ - \hline - - \multicolumn{2}{|l|}{ - Für jedes endliche $M$ ist $\mathit{SG}$ eines Stapels irgendwann periodisch. - } \\ - \hline - - \textsc{Moore}'s Nim:\newline - Beliebige Zahl von maximal $k$ Stapeln. & - \ding{182} - Schreibe $\mathit{pile}_i$ binär. - Addiere ohne Übertrag zur Basis $k + 1$. - Niederlage, falls Ergebnis gleich 0.\newline - \ding{183} - Wenn alle Stapel $1$ sind: - Niederlage, wenn $n \equiv 1 \bmod (k + 1)$. - Sonst wie in \ding{182}.\\ - \hline - - Staircase Nim:\newline - $n$ Stapel in einer Reihe. - Beliebige Zahl von Stapel $i$ nach Stapel $i-1$. & - Niederlage, wenn Nim der ungeraden Spiele verloren ist:\newline - $\oplus_{i = 0}^{(n - 1) / 2} \mathit{pile}_{2i + 1} = 0$\\ - \hline - - \textsc{Lasker}'s Nim:\newline - Zwei mögliche Züge:\newline - 1) Nehme beliebige Zahl.\newline - 2) Teile Stapel in zwei Stapel (ohne Entnahme).& - $\mathit{SG}_n = n$, falls $n \equiv 1,2 \bmod 4$\newline - $\mathit{SG}_n = n + 1$, falls $n \equiv 3 \bmod 4$\newline - $\mathit{SG}_n = n - 1$, falls $n \equiv 0 \bmod 4$\\ - \hline - - \textsc{Kayles}' Nim:\newline - Zwei mögliche Züge:\newline - 1) Nehme beliebige Zahl.\newline - 2) Teile Stapel in zwei Stapel (mit Entnahme).& - Berechne $\mathit{SG}_n$ für kleine $n$ rekursiv.\newline - $n \in [72,83]: \quad 4, 1, 2, 8, 1, 4, 7, 2, 1, 8, 2, 7$\newline - Periode ab $n = 72$ der Länge $12$.\\ - \hline -\end{tabularx} diff --git a/math/tables/numbers.tex b/math/tables/numbers.tex deleted file mode 100644 index 1dc9f38..0000000 --- a/math/tables/numbers.tex +++ /dev/null @@ -1,59 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|l|X|} - \hline - \multicolumn{2}{|c|}{Berühmte Zahlen} \\ - \hline - \textsc{Fibonacci} & - $f(0) = 0 \quad - f(1) = 1 \quad - f(n+2) = f(n+1) + f(n)$ \\ - \grayhline - - \textsc{Catalan} & - $C_0 = 1 \qquad - C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = - \frac{1}{n + 1}\binom{2n}{n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ \\ - \grayhline - - \textsc{Euler} I & - $\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad - \eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\ - \grayhline - - \textsc{Euler} II & - $\eulerII{n}{0} = 1 \quad - \eulerII{n}{n} = 0 \quad$\\ - & $\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\ - \grayhline - - \textsc{Stirling} I & - $\stirlingI{0}{0} = 1 \qquad - \stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad - \stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\ - \grayhline - - \textsc{Stirling} II & - $\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad - \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} = - \frac{1}{k!} \sum\limits_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$\\ - \grayhline - - \textsc{Bell} & - $B_1 = 1 \qquad - B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k} - = \sum\limits_{k = 0}^{n}\stirlingII{n}{k}$\\ - \grayhline - - \textsc{Partitions} & - $p(0,0) = 1 \quad - p(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\ - & $p(n,k) = p(n-k,k) + p(n-1,k-1)$\\ - \grayhline - - \textsc{Partitions} & - $f(0) = 1 \quad f(n) = 0~(n < 0)$ \\ - & $f(n)=\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k+1)}{2})+\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k-1)}{2})$\\ - - \hline -\end{tabularx} -\end{expandtable} diff --git a/math/tables/platonic.tex b/math/tables/platonic.tex deleted file mode 100644 index f4ee554..0000000 --- a/math/tables/platonic.tex +++ /dev/null @@ -1,39 +0,0 @@ -\begin{tabularx}{\linewidth}{|X|CCCX|} - \hline - \multicolumn{5}{|c|}{Platonische Körper} \\ - \hline - Übersicht & Seiten & Ecken & Kanten & dual zu \\ - \hline - Tetraeder & 4 & 4 & 6 & Tetraeder \\ - Würfel/Hexaeder & 6 & 8 & 12 & Oktaeder \\ - Oktaeder & 8 & 6 & 12 & Würfel/Hexaeder\\ - Dodekaeder & 12 & 20 & 30 & Ikosaeder \\ - Ikosaeder & 20 & 12 & 30 & Dodekaeder \\ - \hline - \multicolumn{5}{|c|}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\ - \hline - \multicolumn{3}{|l}{Ecken vom Oktaeder/Seiten vom Würfel} & - \multicolumn{2}{l|}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\ - - \multicolumn{3}{|l}{Ecken vom Würfel/Seiten vom Oktaeder} & - \multicolumn{2}{l|}{$(n^8 + 17n^4 + 6n^2)/24$} \\ - - \multicolumn{3}{|l}{Kanten vom Würfel/Oktaeder} & - \multicolumn{2}{l|}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\ - - \multicolumn{3}{|l}{Ecken/Seiten vom Tetraeder} & - \multicolumn{2}{l|}{$(n^4 + 11n^2)/12$} \\ - - \multicolumn{3}{|l}{Kanten vom Tetraeder} & - \multicolumn{2}{l|}{$(n^6 + 3n^4 + 8n^2)/12$} \\ - - \multicolumn{3}{|l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} & - \multicolumn{2}{l|}{$(n^{12} + 15n^6 + 44n^4)/60$} \\ - - \multicolumn{3}{|l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} & - \multicolumn{2}{l|}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\ - - \multicolumn{3}{|l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} & - \multicolumn{2}{l|}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\ - \hline -\end{tabularx} diff --git a/math/tables/probability.tex b/math/tables/probability.tex deleted file mode 100644 index f265d10..0000000 --- a/math/tables/probability.tex +++ /dev/null @@ -1,27 +0,0 @@ -\begin{tabularx}{\linewidth}{|LICIR|} - \hline - \multicolumn{3}{|c|}{ - Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) - } \\ - \hline - $\E(X + Y) = \E(X) + \E(Y)$ & - $\E(\alpha X) = \alpha \E(X)$ & - $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$\\ - - $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ & - $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ & - $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\ - \hline -\end{tabularx} -\vfill -\begin{tabularx}{\linewidth}{|Xlr|lrX|} - \hline - \multicolumn{6}{|c|}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ - \hline - & $\#A > k\#B$ & $Pr = \frac{a - kb}{a + b}$ & - $\#B - \#A \leq k$ & $Pr = 1 - \frac{a!b!}{(a + k + 1)!(b - k - 1)!}$ & \\ - - & $\#A \geq k\#B$ & $Pr = \frac{a + 1 - kb}{a + 1}$ & - $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ & \\ - \hline -\end{tabularx} diff --git a/math/tables/series.tex b/math/tables/series.tex deleted file mode 100644 index 3042781..0000000 --- a/math/tables/series.tex +++ /dev/null @@ -1,33 +0,0 @@ -\begin{tabularx}{\linewidth}{|XIXIXIX|} - \hline - \multicolumn{4}{|c|}{Reihen} \\ - \hline - $\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ & - $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ & - $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ & - $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ - \grayhline - - $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ & - $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ & - $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ & - $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\ - \grayhline - - \multicolumn{2}{|lI}{ - $\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$ - } & - \multicolumn{2}{l|}{ - $\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$ - } \\ - \grayhline - - \multicolumn{2}{|lI}{ - $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ - } & - \multicolumn{2}{l|}{ - $\sum\limits_{i = 1}^n \binom{i}{m}H_i = - \binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m + 1}\right)$ - } \\ - \hline -\end{tabularx} diff --git a/math/tables/stuff.tex b/math/tables/stuff.tex deleted file mode 100644 index 5b5093e..0000000 --- a/math/tables/stuff.tex +++ /dev/null @@ -1,32 +0,0 @@ -\begin{tabularx}{\linewidth}{|ll|} - \hline - \multicolumn{2}{|C|}{Verschiedenes} \\ - \hline - Türme von Hanoi, minimale Schirttzahl: & - $T_n = 2^n - 1$ \\ - - \#Regionen zwischen $n$ Geraden & - $\frac{n\left(n + 1\right)}{2} + 1$ \\ - - \#abgeschlossene Regionen zwischen $n$ Geraden & - $\frac{n^2 - 3n + 2}{2}$ \\ - - \#markierte, gewurzelte Bäume & - $n^{n-1}$ \\ - - \#markierte, nicht gewurzelte Bäume & - $n^{n-2}$ \\ - - \#Wälder mit $k$ gewurzelten Bäumen & - $\frac{k}{n}\binom{n}{k}n^{n-k}$ \\ - - \#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten& - $\frac{k}{n}n^{n-k}$ \\ - - Dearangements & - $!n = (n - 1)(!(n - 1) + !(n - 2)) = \left\lfloor\frac{n!}{e} + \frac{1}{2}\right\rfloor$ \\ - & - $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ - \hline -\end{tabularx} - diff --git a/math/tables/twelvefold.tex b/math/tables/twelvefold.tex deleted file mode 100644 index 18d3955..0000000 --- a/math/tables/twelvefold.tex +++ /dev/null @@ -1,32 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|C|CICICIC|} - \hline - Bälle & identisch & verschieden & identisch & verschieden \\ - Boxen & identisch & identisch & verschieden & verschieden \\ - \hline - -- & - $p_k(n + k)$ & - $\sum\limits_{i = 0}^k \stirlingII{n}{i}$ & - $\binom{n + k - 1}{k - 1}$ & - $k^n$ \\ - \grayhline - - \makecell{Bälle pro\\Box $\geq 1$} & - $p_k(n)$ & - $\stirlingII{n}{k}$ & - $\binom{n - 1}{k - 1}$ & - $k! \stirlingII{n}{k}$ \\ - \grayhline - - \makecell{Bälle pro\\Box $\leq 1$} & - $[n \leq k]$ & - $[n \leq k]$ & - $\binom{k}{n}$ & - $n! \binom{k}{n}$ \\ - \hline - \multicolumn{5}{|l|}{ - $[\text{Bedingung}]$: \code{return Bedingung ? 1 : 0;} - } \\ - \hline -\end{tabularx} -\end{expandtable} diff --git a/math/transforms/andTransform.cpp b/math/transforms/andTransform.cpp deleted file mode 100644 index 1fd9f5c..0000000 --- a/math/transforms/andTransform.cpp +++ /dev/null @@ -1,8 +0,0 @@ -void fft(vector& a, bool inv = false) { - int n = sz(a); - for (int s = 1; s < n; s *= 2) { - for (int i = 0; i < n; i += 2 * s) { - for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; - tie(u, v) = inv ? pair(v - u, u) : pair(v, u + v); -}}}} diff --git a/math/transforms/bitwiseTransforms.cpp b/math/transforms/bitwiseTransforms.cpp deleted file mode 100644 index 28561da..0000000 --- a/math/transforms/bitwiseTransforms.cpp +++ /dev/null @@ -1,12 +0,0 @@ -void bitwiseConv(vector& a, bool inv = false) { - int n = sz(a); - for (int s = 1; s < n; s *= 2) { - for (int i = 0; i < n; i += 2 * s) { - for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; - tie(u, v) = inv ? pair(v - u, u) : pair(v, u + v); // AND - //tie(u, v) = inv ? pair(v, u - v) : pair(u + v, u); //OR - //tie(u, v) = pair(u + v, u - v); // XOR - }}} - //if (inv) for (ll& x : a) x /= n; // XOR (careful with MOD) -} diff --git a/math/transforms/fft.cpp b/math/transforms/fft.cpp deleted file mode 100644 index 2bd95b2..0000000 --- a/math/transforms/fft.cpp +++ /dev/null @@ -1,23 +0,0 @@ -using cplx = complex; - -void fft(vector& a, bool inv = false) { - int n = sz(a); - for (int i = 0, j = 1; j < n - 1; ++j) { - for (int k = n >> 1; k > (i ^= k); k >>= 1); - if (j < i) swap(a[i], a[j]); - } - static vector ws(2, 1); - for (static int k = 2; k < n; k *= 2) { - ws.resize(n); - cplx w = polar(1.0, acos(-1.0) / k); - for (int i=k; i<2*k; i++) ws[i] = ws[i/2] * (i % 2 ? w : 1); - } - for (int s = 1; s < n; s *= 2) { - for (int j = 0; j < n; j += 2 * s) { - for (int k = 0; k < s; k++) { - cplx u = a[j + k], t = a[j + s + k]; - t *= (inv ? conj(ws[s + k]) : ws[s + k]); - a[j + k] = u + t; - a[j + s + k] = u - t; - if (inv) a[j + k] /= 2, a[j + s + k] /= 2; -}}}} diff --git a/math/transforms/fftMul.cpp b/math/transforms/fftMul.cpp deleted file mode 100644 index eac343c..0000000 --- a/math/transforms/fftMul.cpp +++ /dev/null @@ -1,14 +0,0 @@ -vector mul(vector& a, vector& b) { - vector c(sz(a)), d(sz(a)); - for (int i = 0; i < sz(b); i++) { - c[i] = {real(a[i]), real(b[i])}; - } - fft(c); - for (int i = 0; i < sz(b); i++) { - int j = (sz(a) - i) % sz(a); - cplx x = (c[i] + conj(c[j])) / cplx{2, 0}; //fft(a)[i]; - cplx y = (c[i] - conj(c[j])) / cplx{0, 2}; //fft(b)[i]; - d[i] = x * y; - } - return fft(d, true); -} diff --git a/math/transforms/multiplyBitwise.cpp b/math/transforms/multiplyBitwise.cpp deleted file mode 100644 index 0fa671c..0000000 --- a/math/transforms/multiplyBitwise.cpp +++ /dev/null @@ -1,8 +0,0 @@ -vector mul(vector a, vector b) { - int n = 1 << (__lg(max(sz(a), sz(b)) - 1) + 1); - a.resize(n), b.resize(n); - bitwiseConv(a), bitwiseConv(b); - for (int i=0; i mul(vector& a, vector& b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); - vector a2(all(a)), b2(all(b)); - a2.resize(n), b2.resize(n); - fft(a2), fft(b2); - for (int i=0; i ans(n); - for (int i=0; i mul(vector a, vector b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); - a.resize(n), b.resize(n); - ntt(a), ntt(b); - for (int i=0; i& a, bool inv = false) { - int n = sz(a); - auto b = a; - ll r = inv ? powMod(root, mod - 2, mod) : root; - - for (int s = n / 2; s > 0; s /= 2) { - ll ws = powMod(r, (mod - 1) / (n / s), mod), w = 1; - for (int j = 0; j < n / 2; j += s) { - for (int k = j; k < j + s; k++) { - ll u = a[j + k], t = a[j + s + k] * w % mod; - b[k] = (u + t) % mod; - b[n/2 + k] = (u - t + mod) % mod; - } - w = w * ws % mod; - } - swap(a, b); - } - if (inv) { - ll div = powMod(n, mod - 2, mod); - for (auto& x : a) x = x * div % mod; -}} diff --git a/math/transforms/orTransform.cpp b/math/transforms/orTransform.cpp deleted file mode 100644 index eb1da44..0000000 --- a/math/transforms/orTransform.cpp +++ /dev/null @@ -1,8 +0,0 @@ -void fft(vector& a, bool inv = false) { - int n = sz(a); - for (int s = 1; s < n; s *= 2) { - for (int i = 0; i < n; i += 2 * s) { - for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; - tie(u, v) = inv ? pair(v, u - v) : pair(u + v, u); -}}}} diff --git a/math/transforms/seriesOperations.cpp b/math/transforms/seriesOperations.cpp deleted file mode 100644 index 4743674..0000000 --- a/math/transforms/seriesOperations.cpp +++ /dev/null @@ -1,56 +0,0 @@ -vector poly_inv(const vector& a, int n) { - vector q = {powMod(a[0], mod-2, mod)}; - for (int len = 1; len < n; len *= 2){ - vector a2 = a, q2 = q; - a2.resize(2*len), q2.resize(2*len); - ntt(q2); - for (int j : {0, 1}) { - ntt(a2); - for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; - ntt(a2, true); - for (int i = 0; i < len; i++) a2[i] = 0; - } - for (int i = len; i < min(n, 2*len); i++) { - q.push_back((mod - a2[i]) % mod); - }} - return q; -} - -vector poly_deriv(vector a) { - for (int i = 1; i < sz(a); i++) - a[i-1] = a[i] * i % mod; - a.pop_back(); - return a; -} - -vector poly_integr(vector 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[i] = a[i-1] * powMod(i, mod-2, mod) % mod; - a[0] = 0; - return a; -} - -vector poly_log(vector a, int n) { - a = mul(poly_deriv(a), poly_inv(a, n)); - a.resize(n-1); - a = poly_integr(a); - return a; -} - -vector poly_exp(vector a, int n) { - vector q = {1}; - for (int len = 1; len < n; len *= 2) { - vector 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; - vector q2 = q; - q2.resize(2*len); - ntt(p), ntt(q2); - for (int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; - ntt(p, true); - for (int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); - } - return q; -} diff --git a/math/transforms/xorTransform.cpp b/math/transforms/xorTransform.cpp deleted file mode 100644 index f9d1d82..0000000 --- a/math/transforms/xorTransform.cpp +++ /dev/null @@ -1,10 +0,0 @@ -void fft(vector& a, bool inv = false) { - int n = sz(a); - for (int s = 1; s < n; s *= 2) { - for (int i = 0; i < n; i += 2 * s) { - for (int j = i; j < i + s; j++) { - ll& u = a[j], &v = a[j + s]; - tie(u, v) = pair(u + v, u - v); - }}} - if (inv) for (ll& x : a) x /= n; -} -- cgit v1.2.3