diff options
Diffstat (limited to 'math')
67 files changed, 0 insertions, 2265 deletions
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<ll> BerlekampMassey(const vector<ll>& s) { - int n = sz(s), L = 0, m = 0; - vector<ll> 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<bigint, bigint> 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 f37aea5..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 (fac[n] * inv[n-k] % mod) * inv[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<ll(ll)> 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<ll, ll> 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<ll, 3> 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<bool> 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<ld(ld)> 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<ll>& v) { - Tree<pair<ll, ll>> 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<ll>& v, vector<ll>& left, vector<ll>& 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<ll> &v) { // Sortiert v und gibt Inversionszahl zurück. - int n = sz(v); - vector<ll> 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<ll> kthperm(ll k, ll n) { - Tree<ll> t; - vector<ll> 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<bool> done(n, false); - for (int i = 0; i < n; i++) { - int j = 0; - while (j < n && (done[j] || mat[j][i] == 0)) j++; - if (j == n) continue; - swap(mat[i], mat[j]); - normalLine(i, mod); - takeAll(n, i, mod); - done[i] = true; -}} -// für Eindeutigkeit, Existenz etc. siehe LGS über R 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/linearRecurrence.cpp b/math/linearRecurrence.cpp deleted file mode 100644 index 2501e64..0000000 --- a/math/linearRecurrence.cpp +++ /dev/null @@ -1,33 +0,0 @@ -constexpr ll mod = 1'000'000'007; -vector<ll> modMul(const vector<ll>& a, const vector<ll>& b, - const vector<ll>& c) { - ll n = sz(c); - vector<ll> 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<ll>& f, const vector<ll>& c, ll k) { - assert(sz(f) == sz(c)); - vector<ll> 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<ll> 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<int> lis(vector<ll>& a) { - int n = sz(a), len = 0; - vector<ll> 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<int> 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 f5fbdca..0000000 --- a/math/math.tex +++ /dev/null @@ -1,539 +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}
-\columnbreak
-
-\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}[optional]{Square root modulo prime}
- \sourcecode{math/modSqrt.cpp}
- \sourcecode{math/sqrtModCipolla.cpp}
-\end{algorithm}
-
-\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}{Lineares Sieb 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 entsprechenden multiplikativen Funktion}{1}
-
- \method{naive}{Wert der entsprechenden 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} Funktion:}
- \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{\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}
-\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/linearRecurrence.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{\textsc{Wilson}'s 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{Zeckendorf}'s 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}'s 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<mat> 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<ll> 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<int> 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<ll> v) { - Tree<ll> 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<ll> 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<vector<ll>> memo(cache * cache, vector<ll>(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<ll> data; - - poly(int deg = 0) : data(max(1, deg)) {} - poly(initializer_list<ll> _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<poly, poly> 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<N / 2> isNotPrime; -vector<ll> 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<ll, int> 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<ll, int> 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<ll, int> 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<ll, int>& 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 f696cce..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 - multInv(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<lll, int>& 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<lll> 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 c422d73..0000000 --- a/math/tables.tex +++ /dev/null @@ -1,22 +0,0 @@ -\enlargethispage{0.2cm} -\begin{multicols*}{2} - \refstepcounter{subsection} - \subsectionmark{Tables} - \addcontentsline{toc}{subsection}{\protect\numberline{\thesubsection}Tables} - - \input{math/tables/binom} - \vfill - \input{math/tables/prime-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/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/prime-composite.tex b/math/tables/prime-composite.tex deleted file mode 100644 index 4c32c7d..0000000 --- a/math/tables/prime-composite.tex +++ /dev/null @@ -1,26 +0,0 @@ -\begin{tabularx}{\linewidth}{|r|rIr|rIrIr|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/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 3cf8b4c..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}$ \\ - - Derangements & - $!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/test/binomial0.cpp b/math/test/binomial0.cpp deleted file mode 100644 index d6c3a03..0000000 --- a/math/test/binomial0.cpp +++ /dev/null @@ -1,21 +0,0 @@ -constexpr ll mod = 1'000'000'007; - -#include "../shortModInv.cpp" -#include "../binomial0.cpp" - -int main() { - precalc(); - assert(calc_binom(5, -1) == 0); - assert(calc_binom(5, 0) == 1); - assert(calc_binom(5, 1) == 5); - assert(calc_binom(5, 2) == 10); - assert(calc_binom(5, 3) == 10); - assert(calc_binom(5, 4) == 5); - assert(calc_binom(5, 5) == 1); - assert(calc_binom(5, 6) == 0); - assert(calc_binom(0, 0) == 1); - assert(calc_binom(-1, 0) == 0); - assert(calc_binom(-1, -1) == 0); - assert(calc_binom(-1, -2) == 0); - assert(calc_binom(100'000, 50'000) == 149033233); -} 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<ll>& 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<ll>& 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<double>; - -void fft(vector<cplx>& 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<cplx> 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<cplx> mul(vector<cplx>& a, vector<cplx>& b) { - vector<cplx> 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<ll> mul(vector<ll> a, vector<ll> 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<n; i++) a[i] *= b[i]; // MOD? - bitwiseConv(a, true); - return a; -} diff --git a/math/transforms/multiplyFFT.cpp b/math/transforms/multiplyFFT.cpp deleted file mode 100644 index 0022d1f..0000000 --- a/math/transforms/multiplyFFT.cpp +++ /dev/null @@ -1,12 +0,0 @@ -vector<ll> mul(vector<ll>& a, vector<ll>& b) { - int n = 1 << (__lg(sz(a) + sz(b) - 1) + 1); - vector<cplx> a2(all(a)), b2(all(b)); - a2.resize(n), b2.resize(n); - fft(a2), fft(b2); - for (int i=0; i<n; i++) a2[i] *= b2[i]; - fft(a2, true); - - vector<ll> ans(n); - for (int i=0; i<n; i++) ans[i] = llround(a2[i].real()); - return ans; -} diff --git a/math/transforms/multiplyNTT.cpp b/math/transforms/multiplyNTT.cpp deleted file mode 100644 index 806d124..0000000 --- a/math/transforms/multiplyNTT.cpp +++ /dev/null @@ -1,8 +0,0 @@ -vector<ll> mul(vector<ll> a, vector<ll> 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<n; i++) a[i] = a[i] * b[i] % mod; - ntt(a, true); - return a; -} diff --git a/math/transforms/ntt.cpp b/math/transforms/ntt.cpp deleted file mode 100644 index ca605d3..0000000 --- a/math/transforms/ntt.cpp +++ /dev/null @@ -1,23 +0,0 @@ -constexpr ll mod = 998244353, root = 3; - -void ntt(vector<ll>& 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<ll>& 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<ll> poly_inv(const vector<ll>& a, int n) { - vector<ll> q = {powMod(a[0], mod-2, mod)}; - for (int len = 1; len < n; len *= 2){ - vector<ll> 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<ll> poly_deriv(vector<ll> a) { - for (int i = 1; i < sz(a); i++) - a[i-1] = a[i] * i % mod; - a.pop_back(); - return a; -} - -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[i] = a[i-1] * powMod(i, mod-2, mod) % mod; - a[0] = 0; - return a; -} - -vector<ll> poly_log(vector<ll> a, int n) { - a = mul(poly_deriv(a), poly_inv(a, n)); - a.resize(n-1); - a = poly_integr(a); - return a; -} - -vector<ll> poly_exp(vector<ll> a, int n) { - vector<ll> q = {1}; - 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; - vector<ll> 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<ll>& 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; -} |