updated tcr

61 files changed, 1910 insertions, 1023 deletions

diff --git a/math/berlekampMassey.cpp b/math/berlekampMassey.cpp
new file mode 100644
index 0000000..4999254
--- /dev/null
+++ b/math/berlekampMassey.cpp
@@ -0,0 +1,30 @@
+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;
+		B = T;
+		b = d;
+		m = 0;
+	}
+
+	C.resize(L + 1);
+	C.erase(C.begin());
+	for (auto& x : C) x = (mod - x) % mod;
+	return C;
+}
\ No newline at end of file
diff --git a/math/bigint.cpp b/math/bigint.cpp
index e25ebe3..1753200 100644
--- a/math/bigint.cpp
+++ b/math/bigint.cpp
@@ -1,240 +1,276 @@
-// Bislang keine Division. Multiplikation nach Schulmethode.
-#define PLUS    0
-#define MINUS   1
-#define BASE    1000000000 
-#define EXPONET 9
-
+// base and base_digits must be consistent
+constexpr ll base = 1000000;
+constexpr ll base_digits = 6;
 struct bigint {
-  int sign;
-  vector<ll> digits;
-
-  // Initialisiert mit 0.
-  bigint(void) { sign = PLUS; }
-
-  // Initialisiert mit kleinem Wert.
-  bigint(ll value) {
-    if (value == 0) sign = PLUS;
-    else {
-      sign = value >= 0 ? PLUS : MINUS;
-      value = abs(value);
-      while (value) {
-        digits.push_back(value % BASE);
-        value /= BASE;
-  }}}
-
-  // Initialisiert mit C-String. Kann nicht mit Vorzeichen umgehen.
-  bigint(char *str, int length) {
-    int base = 1;
-    ll digit = 0;
-    for (int i = length - 1; i >= 0; i--) {
-      digit += base * (str[i] - '0');
-      if (base * 10 == BASE) {
-        digits.push_back(digit);
-        digit = 0;
-        base = 1;
-      } else base *= 10;
-    }
-    if (digit != 0) digits.push_back(digit);
-    sign = PLUS;
-  }
-
-  // Löscht führende Nullen und macht -0 zu 0.
-  void trim() {
-    while (digits.size() > 0 && digits[digits.size() - 1] == 0)
-        digits.pop_back();
-    if (digits.size() == 0 && sign == MINUS) sign = PLUS;
-  }
-
-  // Gibt die Zahl aus.
-  void print() {
-    if (digits.size() == 0) { printf("0"); return; }
-    if (sign == MINUS) printf("-");
-    printf("%lld", digits[digits.size() - 1]);
-    for (int i = digits.size() - 2; i >= 0; i--) {
-      printf("%09lld", digits[i]); // Anpassen, wenn andere Basis gewählt wird.
-  }}
-};
-
-// Kleiner-oder-gleich-Vergleich.
-bool operator<=(bigint &a, bigint &b) {
-  if (a.digits.size() == b.digits.size()) {
-    int idx = a.digits.size() - 1;
-    while (idx >= 0) {
-      if (a.digits[idx] < b.digits[idx]) return true;
-      else if (a.digits[idx] > b.digits[idx]) return false;
-      idx--;
-    }
-    return true;
-  }
-  return a.digits.size() < b.digits.size();
-}
-
-// Kleiner-Vergeleich.
-bool operator<(bigint &a, bigint &b) {
-  if (a.digits.size() == b.digits.size()) {
-    int idx = a.digits.size() - 1;
-    while (idx >= 0) {
-      if (a.digits[idx] < b.digits[idx]) return true;
-      else if (a.digits[idx] > b.digits[idx]) return false;
-      idx--;
-    }
-    return false;
-  }
-  return a.digits.size() < b.digits.size();
-}
-
-void sub(bigint *a, bigint *b, bigint *c);
-
-// a + b = c. a, b, c dürfen gleich sein.
-void add(bigint *a, bigint *b, bigint *c) {
-  if (a->sign == b->sign) c->sign = a->sign;
-  else {
-    if (a->sign == MINUS) {
-      a->sign ^= 1;
-      sub(b, a, c);
-      a->sign ^= 1;
-    } else {
-      b->sign ^= 1;
-      sub(a, b, c);
-      b->sign ^= 1;
-    }
-    return;
-  }
-
-  c->digits.resize(max(a->digits.size(), b->digits.size()));
-  ll carry = 0;
-  int i = 0;
-  for (; i < (int)min(a->digits.size(), b->digits.size()); i++) {
-    ll sum = carry + a->digits[i] + b->digits[i];
-    c->digits[i] = sum % BASE;
-    carry = sum / BASE;
-  }
-  if (i < (int)a->digits.size()) {
-    for (; i< (int)a->digits.size(); i++) {
-      ll sum = carry + a->digits[i];
-      c->digits[i] = sum % BASE;
-      carry = sum / BASE;
-    }
-  } else {
-    for (; i< (int)b->digits.size(); i++) {
-      ll sum = carry + b->digits[i];
-      c->digits[i] = sum % BASE;
-      carry = sum / BASE;
-  }}
-  if (carry) c->digits.push_back(carry);
-}
-
-// a - b = c. c darf a oder b sein. a und b müssen verschieden sein.
-void sub(bigint *a, bigint *b, bigint *c) {
-  if (a->sign == MINUS || b->sign == MINUS) {
-    b->sign ^= 1;
-    add(a, b, c);
-    b->sign ^= 1;
-    return;
-  }
-
-  if (a < b) {
-    sub(b, a, c);
-    c->sign = MINUS;
-    c->trim();
-    return;
-  }
-
-  c->digits.resize(a->digits.size());
-  ll borrow = 0;
-  int i = 0;
-  for (; i < (int)b->digits.size(); i++) {
-    ll diff = a->digits[i] - borrow - b->digits[i];
-    if (a->digits[i] > 0) borrow = 0;
-    if (diff < 0) {
-      diff += BASE;
-      borrow = 1;
-    }
-    c->digits[i] = diff % BASE;
-  }
-  for (; i < (int)a->digits.size(); i++) {
-    ll diff = a->digits[i] - borrow;
-    if (a->digits[i] > 0) borrow = 0;
-    if (diff < 0) {
-      diff += BASE;
-      borrow = 1;
-    }
-    c->digits[i] = diff % BASE;
-  }
-  c->trim();
-}
-
-// Ziffernmultiplikation a * b = c. b und c dürfen gleich sein.
-// a muss kleiner BASE sein.
-void digitMul(ll a, bigint *b, bigint *c) {
-  if (a == 0) {
-    c->digits.clear();
-    c->sign = PLUS;
-    return;
-  }
-  c->digits.resize(b->digits.size());
-  ll carry = 0;
-  for (int i = 0; i < (int)b->digits.size(); i++) {
-    ll prod = carry + b->digits[i] * a;
-    c->digits[i] = prod % BASE;
-    carry = prod / BASE;
-  }
-  if (carry) c->digits.push_back(carry);
-  c->sign = (a > 0) ? b->sign : 1 ^ b->sign;
-  c->trim();
-}
-
-// Zifferndivision b / a = c. b und c dürfen gleich sein.
-// a muss kleiner BASE sein.
-void digitDiv(ll a, bigint *b, bigint *c) {
-  c->digits.resize(b->digits.size());
-  ll carry = 0;
-  for (int i = (int)b->digits.size() - 1; i>= 0; i--) {
-    ll quot = (carry * BASE + b->digits[i]) / a;
-    carry = carry * BASE + b->digits[i] - quot * a;
-    c->digits[i] = quot;
-  }
-  c->sign = b->sign ^ (a < 0);
-  c->trim();
-} 
-
-// a * b = c. c darf weder a noch b sein. a und b dürfen gleich sein.
-void mult(bigint *a, bigint *b, bigint *c) {
-  bigint row = *a, tmp;
-  c->digits.clear();
-  for (int i = 0; i < (int)b->digits.size(); i++) {
-    digitMul(b->digits[i], &row, &tmp);
-    add(&tmp, c, c);
-    row.digits.insert(row.digits.begin(), 0);
-  }
-  c->sign = a->sign != b->sign;
-  c->trim();
-}
-
-// Berechnet eine kleine Zehnerpotenz.
-inline ll pow10(int n) {
-  ll res = 1;
-  for (int i = 0; i < n; i++) res *= 10;
-  return res;
-}
-
-// Berechnet eine große Zehnerpotenz.
-void power10(ll e, bigint *out) {
-  out->digits.assign(e / EXPONET + 1, 0);
-  if (e % EXPONET)
-    out->digits[out->digits.size() - 1] = pow10(e % EXPONET);
-  else out->digits[out->digits.size() - 1] = 1;
-}
-
-// Nimmt eine Zahl module einer Zehnerpotenz 10^e.
-void mod10(int e, bigint *a) {
-  int idx = e / EXPONET;
-  if ((int)a->digits.size() < idx + 1) return;
-  if (e % EXPONET) {
-    a->digits.resize(idx + 1);
-    a->digits[idx] %= pow10(e % EXPONET);
-  } else {
-    a->digits.resize(idx);
-  }
-  a->trim();
-}
+	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 < (ll)max(a.size(), v.a.size()) || carry; ++i) {
+				if (i == (ll)res.a.size())
+					res.a.push_back(0);
+				res.a[i] += carry + (i < (ll)a.size() ? 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 < (ll)v.a.size() || carry; ++i) {
+					res.a[i] -= carry + (i < (ll)v.a.size() ? 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 < (ll)a.size() || carry; ++i) {
+			if (i == (ll)a.size()) 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(a.a.size());
+		for (ll i = (ll)a.a.size() - 1; i >= 0; i--) {
+			r *= base;
+			r += a.a[i];
+			ll s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
+			ll s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 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 = (ll)a.size() - 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 = (ll)a.size() - 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 (a.size() != v.a.size())
+			return a.size() * sign < v.a.size() * v.sign;
+		for (ll i = (ll)a.size() - 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() || (a.size() == 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 = (ll)a.size() - 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 < (ll)s.size() && (s[pos] == '-' || s[pos] == '+')) {
+			if (s[pos] == '-') sign = -sign;
+			++pos;
+		}
+		for (ll i = (ll)s.size() - 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 = (ll)v.a.size() - 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 = a.size();
+		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 < (ll)a1b1.size(); i++) r[i] -= a1b1[i];
+		for (ll i = 0; i < (ll)a2b2.size(); i++) r[i] -= a2b2[i];
+		for (ll i = 0; i < (ll)r.size(); i++) res[i + k] += r[i];
+		for (ll i = 0; i < (ll)a1b1.size(); i++) res[i] += a1b1[i];
+		for (ll i = 0; i < (ll)a2b2.size(); 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 (a.size() < b.size()) a.push_back(0);
+		while (b.size() < a.size()) b.push_back(0);
+		while (a.size() & (a.size() - 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 < (ll)c.size(); i++) {
+			ll cur = c[i] + carry;
+			res.a.push_back(cur % base);
+			carry = cur / base;
+		}
+		res.trim();
+		return res;
+	}
+};
\ No newline at end of file
diff --git a/math/binomial.cpp b/math/binomial.cpp
index 9605820..fc6d980 100644
--- a/math/binomial.cpp
+++ b/math/binomial.cpp
@@ -1,10 +1,10 @@
-// Laufzeit: O(k)
-ll calc_binom(ll n, ll k) { // Sehr sicher gegen Overflows.
-   ll r = 1, d;
-   if (k > n) return 0;
-   for (d = 1; d <= k; d++) { // Reihenfolge garantiert Teilbarkeit.
-      r *= n--;
-      r /= d;
-   }
-   return r;
+ll calc_binom(ll n, ll k) {
+	ll r = 1, d;
+	if (k > n) return 0;
+	// Reihenfolge garantiert Teilbarkeit
+	for (d = 1; d <= k; d++) {
+		r *= n--;
+		r /= d;
+	}
+	return r;
 }
diff --git a/math/binomial2.cpp b/math/binomial2.cpp
new file mode 100644
index 0000000..2ddcfe9
--- /dev/null
+++ b/math/binomial2.cpp
@@ -0,0 +1,32 @@
+constexpr ll mod = 1000000009;
+
+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
new file mode 100644
index 0000000..760f2eb
--- /dev/null
+++ b/math/binomial3.cpp
@@ -0,0 +1,9 @@
+ll calc_binom(ll n, ll k, ll p) {
+	if (n >= p || 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
index ac1b71e..2308836 100644
--- a/math/chineseRemainder.cpp
+++ b/math/chineseRemainder.cpp
@@ -1,15 +1,16 @@
 // Laufzeit: O(n * log(n)), n := Anzahl der Kongruenzen
-// Nur für teilerfremde Moduli. Berechnet das kleinste, nicht negative x,
-// das alle Kongruenzen simultan löst. Alle Lösungen sind kongruent zum
-// kgV der Moduli (Produkt, falls alle teilerfremd sind).
+// Nur für teilerfremde Moduli. Berechnet das kleinste, 
+// nicht negative x, das alle Kongruenzen simultan löst. 
+// Alle Lösungen sind kongruent zum kgV der Moduli
+// (Produkt, falls alle teilerfremd sind).
 struct ChineseRemainder {
-	typedef __int128 lll;
+	using lll = __int128;
 	vector<lll> lhs, rhs, mods, inv;
 	lll M; // Produkt über die Moduli. Kann leicht überlaufen.
 
 	ll g(vector<lll> &vec) {
 		lll res = 0;
-		for (int i = 0; i < (int)vec.size(); i++) {
+		for (int i = 0; i < sz(vec); i++) {
 			res += (vec[i] * inv[i]) % M;
 			res %= M;
 		}
@@ -25,9 +26,10 @@ struct ChineseRemainder {
 
 	// Löst das System.
 	ll solve() {
-		M = accumulate(mods.begin(), mods.end(), lll(1), multiplies<lll>());
-		inv.resize(lhs.size());
-		for (int i = 0; i < (int)lhs.size(); i++) {
+		M = accumulate(mods.begin(), mods.end(), lll(1), 
+									 multiplies<lll>());
+		inv.resize(sz(lhs));
+		for (int i = 0; i < sz(lhs); i++) {
 			lll x = (M / mods[i]) % mods[i];
 			inv[i] = (multInv(x, mods[i]) * (M / mods[i]));
 		}
diff --git a/math/cycleDetection.cpp b/math/cycleDetection.cpp
new file mode 100644
index 0000000..621af82
--- /dev/null
+++ b/math/cycleDetection.cpp
@@ -0,0 +1,16 @@
+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
index 6d3f656..d9227b9 100644
--- a/math/discreteLogarithm.cpp
+++ b/math/discreteLogarithm.cpp
@@ -1,13 +1,14 @@
-// Bestimmt Lösung x für a^x=b mod m.
-ll solve (ll a, ll b, ll m) { // Laufzeit: O(sqrt(m)*log(m))
-  ll n = (ll)sqrt((double)m) + 1;
-  map<ll,ll> vals;
-  for (int i = n; i >= 1; i--) vals[powMod(a, i * n, m)] = i;
-  for (int i = 0; i <= n; i++) {
-    ll cur = (powMod(a, i, m) * b) % m;
-    if (vals.count(cur)) {
-      ll ans = vals[cur] * n - i;
-      if (ans < m) return ans;
-  }}
-  return -1;
+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
new file mode 100644
index 0000000..9249f73
--- /dev/null
+++ b/math/discreteNthRoot.cpp
@@ -0,0 +1,5 @@
+ll root(ll a, ll b, ll m) {
+	ll g = findPrimitive(m);
+	ll c = dlog(powMod(g, a, m), b, m); //diskreter logarithmus
+	return c < 0 ? -1 : powMod(g, c, m);
+}
diff --git a/math/divisors.cpp b/math/divisors.cpp
new file mode 100644
index 0000000..638c87c
--- /dev/null
+++ b/math/divisors.cpp
@@ -0,0 +1,11 @@
+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;
+}
\ No newline at end of file
diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp
index 66a6d93..d016a63 100644
--- a/math/extendedEuclid.cpp
+++ b/math/extendedEuclid.cpp
@@ -1,5 +1,6 @@
-ll extendedEuclid(ll a, ll b, ll &x, ll &y) { // a*x + b*y = ggt(a, b).
-	if (a == 0) { x = 0; y = 1; return b; }
+// a*x + b*y = ggt(a, b)
+ll extendedEuclid(ll a, ll b, ll& x, ll& y) {
+	if (a == 0) {x = 0; y = 1; return b;}
 	ll x1, y1, d = extendedEuclid(b % a, a, x1, y1);
 	x = y1 - (b / a) * x1; y = x1;
 	return d;
diff --git a/math/fft.cpp b/math/fft.cpp
deleted file mode 100644
index f09b7e3..0000000
--- a/math/fft.cpp
+++ /dev/null
@@ -1,34 +0,0 @@
-// Laufzeit: O(n log(n)).
-typedef complex<double> cplx; // Eigene Implementierung ist schneller.
-
-// a.size() muss eine Zweierpotenz sein!
-vector<cplx> fft(const vector<cplx> &a, bool inverse = 0) {
-	int logn = 1, n = a.size();
-	vector<cplx> A(n);
-	while ((1 << logn) < n) logn++;
-	for (int i = 0; i < n; i++) {
-		int j = 0;
-		for (int k = 0; k < logn; k++) j = (j << 1) | ((i >> k) & 1);
-		A[j] = a[i];
-	}
-	for (int s = 2; s <= n; s <<= 1) {
-		double angle = 2 * PI / s * (inverse ? -1 : 1);
-		cplx ws(cos(angle), sin(angle));
-		for (int j = 0; j < n; j+= s) {
-			cplx w = 1;
-			for (int k = 0; k < s / 2; k++) {
-				cplx u = A[j + k], t = A[j + s / 2 + k];
-				A[j + k] = u + w * t;
-				A[j + s / 2 + k] = u - w * t;
-				if (inverse) A[j + k] /= 2,	A[j + s / 2 + k] /= 2;
-				w *= ws;
-	}}}
-	return A;
-}
-
-// Polynome: a[0] = a_0, a[1] = a_1, ... und b[0] = b_0, b[1] = b_1, ...
-// Bei Integern: Runde Koeffizienten: (int)round(a[i].real()) 
-vector<cplx> a = {0,0,0,0,1,2,3,4}, b = {0,0,0,0,2,3,0,1};
-a = fft(a); b = fft(b);
-for (int i = 0; i < (int)a.size(); i++) a[i] *= b[i];
-a = fft(a,1); // a = a * b
diff --git a/math/gauss.cpp b/math/gauss.cpp
index b8e43d4..0c7ab03 100644
--- a/math/gauss.cpp
+++ b/math/gauss.cpp
@@ -1,8 +1,3 @@
-// Laufzeit: O(n^3)
-void swapLines(int n, int l1, int l2) {
-	for (int i = 0; i <= n; i++) swap(mat[l1][i], mat[l2][i]);
-}
-
 void normalLine(int n, int line) {
 	double factor = mat[line][line];
 	for (int i = 0; i <= n; i++) {
@@ -17,7 +12,7 @@ void takeAll(int n, int line) {
 			mat[i][j] -= diff * mat[line][j];
 }}}
 
-int gauss(int n) { // Gibt zurück, ob das System (eindeutig) lösbar ist.
+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.
@@ -25,12 +20,13 @@ int gauss(int n) { // Gibt zurück, ob das System (eindeutig) lösbar ist.
 			if (done[j]) continue;
 			if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j;
 		}
-		swapLines(n, i, swappee);
+		swap(mat[i], mat[swappee]);
 		if (abs(mat[i][i]) > EPSILON) {
 			normalLine(n, i);
 			takeAll(n, i);
 			done[i] = true;	
-	}} // Ab jetzt nur noch checks bzgl. Eindeutigkeit/Existenz der Lösung.
+	}}
+	// 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++)
diff --git a/math/gcd-lcm.cpp b/math/gcd-lcm.cpp
index 2f09b7c..a1c63c8 100644
--- a/math/gcd-lcm.cpp
+++ b/math/gcd-lcm.cpp
@@ -1,3 +1,2 @@
-// Laufzeiten: O(log(a) + log(b))
-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)); }
+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
new file mode 100644
index 0000000..2be8c2d
--- /dev/null
+++ b/math/goldenSectionSearch.cpp
@@ -0,0 +1,14 @@
+ld gss(ld l, ld r, function<ld(ld)> f) {
+	ld r = (sqrtl(5.0l)-1)/2;
+	ld x1 = b - r*(b-a), x2 = a + r*(b-a);
+	ld f1 = f(x1), f2 = f(x2);
+	for (int i = 0; i < 200; i++) {
+		if (f1 < f2) { //change to > to find maximum
+			b = x2; x2 = x1; f2 = f1;
+			x1 = b - r*(b-a); f1 = f(x1);
+		} else {
+			a = x1; x1 = x2; f1 = f2;
+			x2 = a + r*(b-a); f2 = f(x2);
+	}}
+	return a;
+}
diff --git a/math/inversions.cpp b/math/inversions.cpp
index 0720407..02256ca 100644
--- a/math/inversions.cpp
+++ b/math/inversions.cpp
@@ -1,27 +1,9 @@
-// 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 < (int)left.size() && b < (int)right.size()) {
-    if (left[a] < right[b]) v[i++] = left[a++];
-    else {
-      inv += left.size() - a;
-      v[i++] = right[b++];
-    }
-  }
-  while (a < (int)left.size()) v[i++] = left[a++];
-  while (b < (int)right.size()) v[i++] = right[b++];
-  return inv;
-}
-
-ll mergeSort(vector<ll> &v) { // Sortiert v und gibt Inversionszahl zurück.
-  int n = v.size();
-  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 (left.size() > 1) result += mergeSort(left);
-  if (right.size() > 1) result += mergeSort(right);
-  return result + merge(v, left, right);
+ll inversions(const vector<ll>& v) {
+	Tree<pair<ll, ll>> t; //ordered statistics tree
+	ll res = 0;
+	for (ll i = 0; i < (ll)v.size(); 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
new file mode 100644
index 0000000..1ea2ada
--- /dev/null
+++ b/math/inversionsMerge.cpp
@@ -0,0 +1,27 @@
+// 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 < (int)left.size() && b < (int)right.size()) {
+		if (left[a] < right[b]) v[i++] = left[a++];
+		else {
+			inv += left.size() - a;
+			v[i++] = right[b++];
+		}
+	}
+	while (a < (int)left.size()) v[i++] = left[a++];
+	while (b < (int)right.size()) v[i++] = right[b++];
+	return inv;
+}
+
+ll mergeSort(vector<ll> &v) { // Sortiert v und gibt Inversionszahl zurück.
+	int n = v.size();
+	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 (left.size() > 1) result += mergeSort(left);
+	if (right.size() > 1) result += mergeSort(right);
+	return result + merge(v, left, right);
+}
diff --git a/math/kthperm.cpp b/math/kthperm.cpp
new file mode 100644
index 0000000..899dff1
--- /dev/null
+++ b/math/kthperm.cpp
@@ -0,0 +1,14 @@
+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
index adfd3c6..f08755f 100644
--- a/math/legendre.cpp
+++ b/math/legendre.cpp
@@ -1,17 +1,4 @@
-int legendre(ll a, ll p) {
-  a %= p;
-  if (a == 0) return 0;
-  if (a == 1 || p == 2) return 1;
-  if (a == 2) return (((p * p - 1) / 8) & 1) ? -1 : 1;
-  if (isPrime(a)) {
-    return legendre(p, a) * ((((p - 1) * (a - 1) / 4) & 1) ? -1 : 1);
-  } else {
-    map<ll, int> facts;
-    factor(a, facts);
-    int res = 1;
-    for (auto f : facts)
-      if (f.second & 1)
-        res *= legendre(f.first, p);
-    return res;
-  }
+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
index 14549b7..52442c6 100644
--- a/math/lgsFp.cpp
+++ b/math/lgsFp.cpp
@@ -1,10 +1,5 @@
-// Laufzeit: O(n^3)
-void swapLines(int n, int l1, int l2) {
-	for (int i = 0; i <= n; i++) swap(mat[l1][i], mat[l2][i]);
-}
-
 void normalLine(int n, int line, ll p) {
-	ll factor = multInv(mat[line][line], p); // Implementierung von oben.
+	ll factor = multInv(mat[line][line], p);
 	for (int i = 0; i <= n; i++) {
 		mat[line][i] *= factor;
 		mat[line][i] %= p;
@@ -23,8 +18,10 @@ void takeAll(int n, int line, ll p) {
 void gauss(int n, ll p) { // nx(n+1)-Matrix, Körper F_p.
 	for (int line = 0; line < n; line++) {
 		int swappee = line;
-		while (mat[swappee][line] == 0) swappee++;
-		swapLines(n, line, swappee);
+		while (swappee < n && mat[swappee][line] == 0) swappee++;
+		if (swappee == n) continue;
+		swap(mat[line], mat[swappee]);
 		normalLine(n, line, p);
 		takeAll(n, line, p);
+		// für Eindeutigkeit, Existenz etc. siehe LGS
 }}
diff --git a/math/linearCongruence.cpp b/math/linearCongruence.cpp
new file mode 100644
index 0000000..b4f172d
--- /dev/null
+++ b/math/linearCongruence.cpp
@@ -0,0 +1,5 @@
+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);
+}
\ No newline at end of file
diff --git a/math/longestIncreasingSubsequence.cpp b/math/longestIncreasingSubsequence.cpp
index 388e394..357ebcd 100644
--- a/math/longestIncreasingSubsequence.cpp
+++ b/math/longestIncreasingSubsequence.cpp
@@ -1,23 +1,23 @@
-vector<int> longestIncreasingSubsequence(vector<int> &seq) {
-  int n = seq.size(), lisLength = 0, lisEnd = 0;
-  vector<int> L(n), L_id(n), parents(n);
-  for (int i = 0; i < n; i++) {
-    int pos =
-      lower_bound(L.begin(), L.begin() + lisLength, seq[i]) - L.begin();
-    L[pos] = seq[i];
-    L_id[pos] = i;
-    parents[i] = pos ? L_id[pos - 1] : -1;
-    if (pos + 1 > lisLength) {
-      lisLength = pos + 1;
-      lisEnd = i;
-  }}
-  // Ab hier Rekonstruktion der Sequenz.
-  vector<int> result(lisLength);
-  int pos = lisLength - 1, x = lisEnd;
-  while (parents[x] >= 0) {
-    result[pos--] = x;
-    x = parents[x];
-  }
-  result[0] = x;
-  return result; // Liste mit Indizes einer LIS.
+vector<int> lis(vector<int> &seq) {
+	int n = seq.size(), lisLength = 0, lisEnd = 0;
+	vector<int> L(n), L_id(n), parents(n);
+	for (int i = 0; i < n; i++) {
+		int pos = upper_bound(L.begin(), L.begin() + lisLength, 
+													seq[i]) - L.begin();
+		L[pos] = seq[i];
+		L_id[pos] = i;
+		parents[i] = pos ? L_id[pos - 1] : -1;
+		if (pos + 1 > lisLength) {
+			lisLength = pos + 1;
+			lisEnd = i;
+	}}
+	// Ab hier Rekonstruktion der Sequenz.
+	vector<int> result(lisLength);
+	int pos = lisLength - 1, x = lisEnd;
+	while (parents[x] >= 0) {
+		result[pos--] = x;
+		x = parents[x];
+	}
+	result[0] = x;
+	return result; // Liste mit Indizes einer LIS.
 }
diff --git a/math/math.tex b/math/math.tex
index 1f372e5..4545927 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,58 +1,187 @@
 \section{Mathe}
 
-\subsection{ggT, kgV, erweiterter euklidischer Algorithmus}
-\lstinputlisting{math/gcd-lcm.cpp}
-\lstinputlisting{math/extendedEuclid.cpp}
+\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}{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}
 
 \paragraph{Lemma von \textsc{Bézout}}
-Sei $(x, y)$ eine Lösung für $ax + by = d$.
+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)
+\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
 \]
 
-\paragraph{Multiplikatives Inverses von $x$ in $\mathbb{Z}/n\mathbb{Z}$}
-Sei $0 \leq x < n$. Definiere $d := \ggT(x, n)$.\newline
-\textbf{Falls $d = 1$:}
-\begin{itemize}[nosep]
-	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
-	$\alpha x + \beta n = 1$.
-	\item Nach Kongruenz gilt $\alpha x + \beta n \equiv \alpha x \equiv 1 \mod n$.
-	\item $x^{-1} :\equiv \alpha \mod n$
-	\end{itemize}
-\textbf{Falls $d \neq 1$:} Es existiert kein $x^{-1}$.
-\lstinputlisting{math/multInv.cpp}
+\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*}
 
-\subsection{Mod-Exponent über $\mathbb{F}_p$}
-\lstinputlisting{math/modExp.cpp}
-Iterativ:
-\lstinputlisting{math/modPowIterativ.cpp}
+\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
+	\runtime{\log(a) + \log(b)}
+	\sourcecode{math/gcd-lcm.cpp}
+	\sourcecode{math/extendedEuclid.cpp}
+\end{algorithm}
 
-\subsection{Chinesischer Restsatz}
+\subsection{Multiplikatives Inverses von $\boldsymbol{n}$ in $\boldsymbol{\mathbb{Z}/p\mathbb{Z}}$}
+\textbf{Falls $\boldsymbol{p}$ prim:}\quad $x^{-1} \equiv x^{p-2} \bmod p$
+
+\textbf{Falls $\boldsymbol{\ggT(n, p) = 1}$:}
 \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 \mod n$, $x \equiv b \mod m$:
-	\[
-		x \equiv a - y * n * \frac{a - b}{d} \mod \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 \mod \ggT(m, n)$.
-	In diesem Fall sind keine Faktoren
-	auf der linken Seite erlaubt.
+	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
+	$\alpha n + \beta p = 1$.
+	\item Nach Kongruenz gilt $\alpha n + \beta p \equiv \alpha n \equiv 1 \bmod p$.
+	\item $n^{-1} :\equiv \alpha \bmod p$
+	\end{itemize}
+\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
+\sourcecode{math/multInv.cpp}
+
+\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}
+
+\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}
-\lstinputlisting{math/chineseRemainder.cpp}
-
-\subsection{Primzahltest \& Faktorisierung}
-\lstinputlisting{math/primes.cpp}
 
-\subsection{Primzahlsieb von \textsc{Eratosthenes}}
-\lstinputlisting{math/primeSieve.cpp}
+\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}{Berlekamp-Massey}
+	\begin{methods}
+		\method{BerlekampMassey}{Berechnet ein lineare Recurenz $n$-ter Ordnung}{n^2}
+		\method{}{aus den ersten $2n$ Werte}{}
+	\end{methods}
+	\sourcecode{math/berlekampMassey.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lineare-Recurenz}
+	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine Lineare Recurenz. Dann kann das \mbox{$k$-te} folgenglid in \runtime{n^3\log(k)} brechnet 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} \\
+		0 & \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}{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}
 
-\subsection{\textsc{Euler}sche $\varphi$-Funktion}
-\begin{itemize}[nosep]
+\begin{algorithm}{Primzahltest \& Faktorisierung}
+	\begin{itemize}
+		\item für $n > 10^9$ \texttt{BigInteger} benutzten order \texttt{modMul}! 
+	\end{itemize}
+	\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}3]{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}{Primzahlsieb von \textsc{Eratosthenes}}
+	\begin{itemize}
+		\item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
+		\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}{Teiler}
+	\begin{methods}
+		\method{countDivisors}{Zählt teiler von $n$}{n^\frac{1}{3}}
+		\method{isPrime}{prüft ob Zahl prim ist}{1}
+	\end{methods}
+	\sourcecode{math/divisors.cpp}
+\end{algorithm}
+
+\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}
+
+\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
+\begin{itemize}
 	\item Zählt die relativ primen Zahlen $\leq n$.
 
 	\item Multiplikativ:
@@ -61,67 +190,136 @@ Iterativ:
 	\item $p$ prim, $k \in \mathbb{N}$:
 	$~\varphi(p^k) = p^k - p^{k - 1}$
 
-	\item $n = p_1^{a_1} \cdot \ldots \cdot p_k^{a_k}$:
-	$~\varphi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right)$
-	Evtl. ist es sinnvoll obgien Code zum Faktorisieren zu benutzen und dann diese Formel anzuwenden.
-
 	\item \textbf{\textsc{Euler}'s Theorem:}
-	Seien $a$ und $m$ teilerfremd. Dann:
-	$a^{\varphi(m)} \equiv 1 \mod m$\newline
+		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 \mod m$
+	$a^{m} \equiv a \pmod{m}$
 \end{itemize}
-\lstinputlisting{math/phi.cpp}
-
-\subsection{Primitivwurzeln}
-\begin{itemize}[nosep]
-	\item Primitivwurzel modulo $n$ existiert genau dann wenn:
-	\begin{itemize}[nosep]
-		\item $n$ ist $1$, $2$ oder $4$, oder
-		\item $n$ ist Potenz einer ungeraden Primzahl, oder
-		\item $n$ ist das Doppelte einer Potenz einer ungeraden Primzahl.
+\sourcecode{math/phi.cpp}
+
+\begin{algorithm}{\textsc{Möbius}-Funktion und \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}
-
-	\item Sei $g$ Primitivwurzel modulo $n$.
-	Dann gilt:\newline
-	Das kleinste $k$, sodass $g^k \equiv 1 \mod n$, ist $k = \varphi(n)$.
-\end{itemize}
-\lstinputlisting{math/primitiveRoot.cpp}
-
-\subsection{Diskreter Logarithmus}
-\lstinputlisting{math/discreteLogarithm.cpp}
-
-\subsection{Binomialkoeffizienten}
-\lstinputlisting{math/binomial.cpp}
-
-\subsection{LGS über $\mathbb{F}_p$}
-\lstinputlisting{math/lgsFp.cpp}
-
-\subsection{LGS über $\mathbb{R}$}
-\lstinputlisting{math/gauss.cpp}
-
-\subsection{Polynome \& FFT}
+	\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^{cnt[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}
+
+\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}{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}
+
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
+
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\sourcecode{math/gauss.cpp}
+
+\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 Multipliziert Polynome $A$ und $B$.
-\begin{itemize}[nosep]
-	\item $\deg(A * B) = \deg(A) + \deg(B)$
-	\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
-	$\deg(A * B) + 1$ haben.
-	Größe muss eine Zweierpotenz sein.
-	\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
-\end{itemize}
-\lstinputlisting{math/fft.cpp}
-
-\subsection{Numerisch Integrieren, Simpsonregel}
-\lstinputlisting{math/simpson.cpp}
-
-\subsection{3D-Kugeln}
-\lstinputlisting{math/spheres.cpp}
-
-\subsection{Longest Increasing Subsequence}
-\lstinputlisting{math/longestIncreasingSubsequence.cpp}
-
-\subsection{Inversionszahl und Mergesort}
-\lstinputlisting{math/inversions.cpp}
+	\begin{itemize}
+		\item $\deg(A \cdot B) = \deg(A) + \deg(B)$
+		\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
+		$\deg(A \cdot B) + 1$ haben.
+		Größe muss eine Zweierpotenz sein.
+		\item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
+		\item xor, or und 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/all.cpp}
+	\columnbreak
+	Für sehr viele transforms kann die Vertauschung vorberechnet werden:
+	\sourcecode{math/transforms/fftPerm.cpp}
+	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
+	\sourcecode{math/transforms/fftMul.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+	\sourcecode{math/simpson.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+	\sourcecode{math/goldenSectionSearch.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}{Inversionszahl}
+	\sourcecode{math/inversions.cpp}
+\end{algorithm}
+
+\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}
 
 \subsection{Satz von \textsc{Sprague-Grundy}}
 Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
@@ -131,98 +329,22 @@ Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu
 		\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.\\\\
+$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{\textsc{Legendre}-Symbol}
-Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
-\begin{align*}
-	\legendre{a}{p} &=
-	\begin{cases*}
-		 0 & falls $p~\vert~a$ \\[-1ex]
-		 1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \mod p$ \\[-1ex]
-		-1 & sonst
-	\end{cases*} \\
-	\legendre{-1}{p} &= (-1)^{\frac{p - 1}{2}} =
-	\begin{cases*}
-		 1 & falls $p \equiv 1 \mod 4$ \\[-1ex]
-		-1 & falls $p \equiv 3 \mod 4$
-	\end{cases*} \\
-	\legendre{2}{p} &= (-1)^{\frac{p^2 - 1}{8}} =
-	\begin{cases*}
-		 1 & falls $p \equiv \pm 1 \mod 8$ \\[-1ex]
-		-1 & falls $p \equiv \pm 3 \mod 8$
-	\end{cases*} \\
-	\legendre{p}{q} \cdot \legendre{q}{p} &=
-	(-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}}
-\end{align*}
-\lstinputlisting{math/legendre.cpp}
-
-\subsection{\textsc{Möbius}-Funktion und \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_{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^{cnt[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)$.
-\lstinputlisting{math/mobius.cpp}
-
 \subsection{Kombinatorik}
 
-\begin{flushleft}
-	\begin{tabular}{ll}
-		\toprule
-		\multicolumn{2}{c}{Berühmte Zahlen} \\
-		\midrule 
-		\textsc{Fibonacci}	&
-		$f(0) = 0 \quad
-		f(1) = 1 \quad
-		f(n+2) = f(n+1) + f(n)$ \\
-
-		\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}$ \\
-
-		\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} $ \\
-
-		\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}$ \\
-
-		\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}$ \\
-
-		\textsc{Stirling} II &
-		$\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
-		\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1}$ \\
-
-		\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}$\\
-
-		\textsc{Partitions} &
-		$f(0,0) = 1 \quad
-		f(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\
-		& $f(n,k) = f(n-k,k) + f(n-1,k-1)$ \\
-		\bottomrule
-	\end{tabular}
-\end{flushleft}
+\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
@@ -231,340 +353,124 @@ 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}.
+\]
+
+\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
+\input{math/tables/twelvefold}
+
 \paragraph{\textsc{Catalan}-Zahlen}
-\begin{itemize}[nosep]
-	\item Die erste und dritte angegebene Formel sind relativ sicher gegen Overflows.
-	\item Die erste Formel kann auch zur Berechnung der \textsc{Catalan}-Zahlen
-	bezüglich eines Moduls genutzt werden.
-	\item Die \textsc{Catalan}-Zahlen geben an: $C_n =$
-	\begin{itemize}[nosep]
+\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 der Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken in
-		Dreiecke zu zerlegen.
+		\item Anzahl der Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken in Dreiecke zu zerlegen.
 		\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{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 Ansteig 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}
 
 \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{Striling}-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}
 
-\paragraph{Integer Partitions}
-Anzahl der Teilmengen von $\mathbb{N}$, die sich zu $n$ aufaddieren mit maximalem Elment $\leq k$.\\
-
-\begin{tabular}{lcr}
-	\toprule
-	\multicolumn{3}{c}{Binomialkoeffizienten} \\
-	\midrule
-	$\binom{n}{k} = \frac{n!}{k!(n - k)!}$ &
-	$\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}$ &
-	$\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$ \\
-
-	$\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ &
-	$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ &
-	$\binom{n}{k} = (-1)^k \binom{k - n - 1}{k}$ \\
-
-	$\binom{n}{k} = \binom{n}{n - k}$ &
-	$\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}$ \\
-
-	$\binom{n}{k} = \frac{n}{k}\binom{n - 1}{k - 1}$ &
-	$\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ &
-	$\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{tabular}{l|l|l}
-	\toprule
-	\multicolumn{3}{c}{Reihen} \\
-	\midrule
-	$\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ &
-	$\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(n + 2)}{6}$ & 
-	$\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\
-
-	$\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$ \\
-
-	\multicolumn{2}{l|}{
-		$\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$
-	} &
-	$\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\
-
-	$H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ &
-	\multicolumn{2}{l}{
-		$\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$
-	} \\
-
-	$\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)$
-	} \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{tabular}{l|r}
-	\toprule
-	\multicolumn{2}{c}{
-		Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen)
-	} \\
-	\midrule
-	$\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]}$ \\
-
-	$\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ &
-	$\Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{tabular}{lr|lr}
-	\toprule
-	\multicolumn{4}{c}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\
-	\midrule
-	$\#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}$ \\
-	\bottomrule
-\end{tabular}
-\vspace{5mm}
-
-\begin{tabular}{c|cccc}
-	\toprule
-	\multicolumn{5}{c}{The Twelvefold Way (verteile $n$ Bälle auf $k$ Boxen)} \\
-	\midrule
-	Bälle & identisch & unterscheidbar & identisch      & unterscheidbar \\
-	Boxen & identisch & identisch      & unterscheidbar & unterscheidbar \\
-	\midrule
-	- &
-	$p_k(n)$ &
-	$\sum\limits_{i = 0}^k \stirlingII{n}{i}$ &
-	$\binom{n + k - 1}{k - 1}$ &
-	$k^n$ \\
-
-	size $\geq 1$ &
-	$p(n, k)$ &
-	$\stirlingII{n}{k}$ &
-	$\binom{n - 1}{k - 1}$ &
-	$k! \stirlingII{n}{k}$ \\
-
-	size $\leq 1$ &
-	$[n \leq k]$ &
-	$[n \leq k]$ &
-	$\binom{k}{n}$ &
-	$n! \binom{k}{n}$ \\
-	\midrule
-	\multicolumn{5}{l}{
-		$p_k(n)$: \#Anzahl der Partitionen von $n$ in $\leq k$ positive Summanden.
-	} \\
-	\multicolumn{5}{l}{
-		$p(n, k)$: \#Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
-	} \\
-	\multicolumn{5}{l}{
-		$[\text{Bedingung}]$: \lstinline{return Bedingung ? 1 : 0;}
-	} \\
-	\bottomrule
-\end{tabular}
-\vspace{1mm}
-
-\begin{flushleft}
-	\begin{tabular}{l|cccl}
-		\toprule
-		\multicolumn{5}{c}{Platonische Körper} \\
-		\midrule
-		Übersicht       & Seiten & Ecken & Kanten & dual zu \\
-		\midrule
-		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 \\
-		\midrule
-		\multicolumn{5}{c}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\
-		\midrule
-		\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$} \\
-		\bottomrule
-	\end{tabular}
-\end{flushleft}
-\vspace{1mm}
-
-\begin{tabular}{p{4.3cm}|p{7cm}}
-	\toprule
-	\multicolumn{2}{c}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\
-	\midrule
-	Beschreibung &
-	Strategie \\
-	\midrule
-
-	$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.\\
-	\midrule
-
-	$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 \mod (a + 1) $\newline
-	$\mathit{SG}_n = n \% (a + 1) \% 2$, sonst.\\
-	\midrule
-
-	$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$ \\
-	\midrule
-
-	$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}$}$\\
-	\midrule
-
-	$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 \mod (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$\\
-	\midrule
-
-	\multicolumn{2}{l}{
-		Für jedes endliche $M$ ist $\mathit{SG}$ eines Stapels irgendwann periodisch.
-	} \\
-	\midrule
-
-	\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 \mod (k + 1)$.
-	Sonst wie in \ding{182}.\\
-	\midrule
-
-	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$\\
-	\midrule
-
-	\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 \mod 4$\newline
-	$\mathit{SG}_n = n + 1$, falls $n \equiv 3 \mod 4$\newline
-	$\mathit{SG}_n = n - 1$, falls $n \equiv 0 \mod 4$\\
-	\midrule
-
-	\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$.\\
-	\bottomrule
-\end{tabular}
-
-\begin{tabular}{ll}
-	\toprule
-	\multicolumn{2}{c}{Verschiedenes} \\
-	\midrule
-	Türme von Hanoi, minimale Schirttzahl: &
-	$T_n = 2^n - 1$ \\
-
-	\#Regionen zwischen $n$ Gearden	&
-	$\frac{n\left(n + 1\right)}{2} + 1$ \\
-
-	\#geschlossene 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}$ \\
-
-	Derangements &
-	$!n = (n - 1)(!(n - 1) + !(n - 2))$ \\
-	&
-	$!n = \left\lfloor\frac{n!}{e} + \frac{1}{2}\right\rfloor$ \\
-	&
-	$\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\
-	\bottomrule
-\end{tabular}
-
-% \subsection{Big Integers}
-% \lstinputlisting{math/bigint.cpp}
+\paragraph{Binomialkoeffizienten}
+Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
+
+\textbf{WICHTIG:} Binomialkoeffizient in \runtime{1} berechnen indem man $x!$ vorberechnet.
+
+%\begin{algorithm}{Binomialkoeffizienten}
+	\begin{methods}
+		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
+	\end{methods}
+	\sourcecode{math/binomial.cpp}
+
+\columnbreak
+	\begin{methods}
+		\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
+	\end{methods}
+	\textbf{Wichtig:} $p > n$
+	\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}
+
+%\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
new file mode 100644
index 0000000..d3c1b63
--- /dev/null
+++ b/math/matrixPower.cpp
@@ -0,0 +1,16 @@
+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];
+}
\ No newline at end of file
diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp
new file mode 100644
index 0000000..fc9385a
--- /dev/null
+++ b/math/millerRabin.cpp
@@ -0,0 +1,20 @@
+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);
+		if(v == 1 || v == n - 1) continue;
+		for(ll i = 1; i <= j; i++) {
+			v = (v * v) % n; //mulmod or int128
+			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
index 7830eb1..3fb4d9e 100644
--- a/math/mobius.cpp
+++ b/math/mobius.cpp
@@ -1,4 +1,21 @@
-// Laufzeit: O(N*log(log(N)))
-int mu[N+1]; mu[1] = 1;
-for (int i = 1; i <= N; i++) {
-  for (int j = 2 * i; j <= N; j += i) mu[j] -= mu[i];
+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
index d74eca0..2329a94 100644
--- a/math/modExp.cpp
+++ b/math/modExp.cpp
@@ -1,7 +1,6 @@
-// Laufzeit: O(log(b))
 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);
+	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
new file mode 100644
index 0000000..611f09a
--- /dev/null
+++ b/math/modMulIterativ.cpp
@@ -0,0 +1,9 @@
+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
index f06b4bd..0dc3fb1 100644
--- a/math/modPowIterativ.cpp
+++ b/math/modPowIterativ.cpp
@@ -1,11 +1,9 @@
-// Laufzeit: O(log (b))
 ll powMod(ll a, ll b, ll n) {
-  if (b == 0) return 1;
-  ll res = 1;
-  while (b > 1) {
-    if (b & 1) res = (a * res) % n;
-    a = (a * a) % n;
-    b /= 2;
-  }
-  return (a * res) % 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
new file mode 100644
index 0000000..367c6c7
--- /dev/null
+++ b/math/modSqrt.cpp
@@ -0,0 +1,23 @@
+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
index 4e388b8..87603f3 100644
--- a/math/multInv.cpp
+++ b/math/multInv.cpp
@@ -1,7 +1,5 @@
-// Laufzeit: O(log (n) + log(p))
 ll multInv(ll n, ll p) {
 	ll x, y;
 	extendedEuclid(n, p, x, y); // Implementierung von oben.
-	x = ((x % p) + p) % p;
-	return x % p;
+	return ((x % p) + p) % p;
 }
diff --git a/math/permIndex.cpp b/math/permIndex.cpp
new file mode 100644
index 0000000..09ff7f7
--- /dev/null
+++ b/math/permIndex.cpp
@@ -0,0 +1,14 @@
+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 (ll i = sz(v); i > 0; i--) {
+		res *= i;
+		res += v[i - 1];
+	}
+	return res;
+}
diff --git a/math/phi.cpp b/math/phi.cpp
index f568bba..482a139 100644
--- a/math/phi.cpp
+++ b/math/phi.cpp
@@ -1,20 +1,21 @@
 ll phi(ll n) { // Laufzeit: O(sqrt(n))
-  // Optimierung: Falls n prim, n - 1 zurückgeben (Miller-Rabin/Sieb).
-  ll result = n;
-  for(int i = 2; i * i <= n; ++i) {
-    if(n % i == 0) {  // Optimierung: Nur über Primzahlen iterieren.
-      while(n % i == 0)n /= i;
-      result -= result / i;
-    }
-  }
-  if(n > 1) result -= result / n;
-  return result;
+	// 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)))
-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;
+// 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
new file mode 100644
index 0000000..f45ee85
--- /dev/null
+++ b/math/piLegendre.cpp
@@ -0,0 +1,23 @@
+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(primes.begin(), primes.end(), n));

+	} else {

+		ll k = pi(sqrtl(n) + 1);

+		return n - phi(n, k) + k;

+}}

diff --git a/math/piLehmer.cpp b/math/piLehmer.cpp
new file mode 100644
index 0000000..37eff6b
--- /dev/null
+++ b/math/piLehmer.cpp
@@ -0,0 +1,52 @@
+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;

+}
\ No newline at end of file
diff --git a/math/polynomial.cpp b/math/polynomial.cpp
new file mode 100644
index 0000000..f7d9a89
--- /dev/null
+++ b/math/polynomial.cpp
@@ -0,0 +1,65 @@
+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
index 286aa1d..68f7fcb 100644
--- a/math/primeSieve.cpp
+++ b/math/primeSieve.cpp
@@ -1,22 +1,17 @@
-// Laufzeit: O(n * log log n)
-// Kann erweitert werden: Für jede Zahl den kleinsten Primfaktor.
-// Dabei vorsicht: Nicht kleinere Faktoren überschreiben.
-#define N 100000000 // Bis 10^8 in unter 64MB Speicher.
+constexpr ll N = 100000000;
 bitset<N / 2> isNotPrime;
+vector<ll> primes = {2};
 
-inline bool isPrime(int x) { // Diese Methode zum Lookup verwenden.
-  if (x < 2) return false;
-  else if (x == 2) return true;
-  else if (!(x & 1)) return false;
-  else return !isNotPrime[x / 2];
+bool isPrime(ll x) {
+	if (x < 2 || x % 2 == 0) return x == 2;
+	else return !isNotPrime[x / 2];
 }
 
-inline int primeSieve() { // Rückgabe: Anzahl der Primzahlen < N.
-  int counter = 1; // Die 2, die sonst vergessen würde.
-  for (int i = 3; i < N; i += 2) {
-    if (!isNotPrime[i / 2]) {
-      for (int j = i * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1;
-      counter++;
-  }}
-  return counter;
-}
+void primeSieve() {
+	// i * i < N is enough for isPrime
+	for (ll i = 3; i < N; i += 2) {
+		if (!isNotPrime[i / 2]) {
+			primes.push_back(i);
+			for (ll j = i * i; j < N; j+= 2 * i) {
+				isNotPrime[j / 2] = 1;
+}}}}
diff --git a/math/primes.cpp b/math/primes.cpp
deleted file mode 100644
index 79e0001..0000000
--- a/math/primes.cpp
+++ /dev/null
@@ -1,39 +0,0 @@
-bool isPrime(ll n) { // Miller Rabin Primzahltest. O(log n)
-	if(n == 2) return true;
-	if(n < 2 || n % 2 == 0) return false;
-	ll d = n - 1, j = 0;
-	while(d % 2 == 0) d >>= 1, j++;
-	for(int a = 2; a <= min((ll)37, n - 1); a++) {
-		ll v = powMod(a, d, n); // Implementierung von oben.
-		if(v == 1 || v == n - 1) continue;
-		for(int i = 1;  i <= j; i++) {
-			v = (v * v) % n;
-			if(v == n - 1 || v <= 1) break;
-		}
-		if(v != n - 1) return false;
-	}
-	return true;
-}
-
-ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
-  if (~n & 1) return 2;
-  ll c = rand() % n, x = rand() % n, y = x, d = 1;
-  while (d == 1) {
-    x = ((x * x) % n + c) % n;
-    y = ((y * y) % n + c) % n;
-    y = ((y * y) % n + c) % n;
-    d = gcd(abs(x - y), n); // Implementierung von oben.
-  }
-  return d == n ? rho(n) : d;
-}
-
-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/primitiveRoot.cpp b/math/primitiveRoot.cpp
index 3ad828d..36a9367 100644
--- a/math/primitiveRoot.cpp
+++ b/math/primitiveRoot.cpp
@@ -1,23 +1,23 @@
-// Ist g Primitivwurzel modulo p. Teste zufällige g, um eine zu finden.
-bool is_primitive(ll g, ll p) {
-  map<ll, int> facs;
-  factor(p - 1, facs);
-  for (auto &f : facs)
-    if (1 == powMod(g, (p - 1) / f.first, p)) return false;
-  return true;
+bool isPrimitive(ll g, ll n, ll phi, map<ll, int> phiFacs) {
+	if (g == 1) return n == 2;
+	for (auto& f : phiFacs)
+		if (1 == powMod(g, phi / f.first, n)) return false;
+	return true;
 }
 
-// Alternativ: Generator zum Finden. -1 falls keine existiert.
-ll generator (ll p) { // Laufzeit: O(ans*log(phi(n))*log(n))
-	map<ll, int> facs;
-	factor(n, facs);
-  ll phi = phi(p),  n = phi;
-
-  for (ll res = 2; res <= p; res++) {
-    bool ok = true;
-    for (auto &f : facs)
-    	ok &= powMod(res, phi / f.first, p) != 1;
-    if (ok)  return res;
-  }
-  return -1;
+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;
+}
\ No newline at end of file
diff --git a/math/rho.cpp b/math/rho.cpp
new file mode 100644
index 0000000..bd30902
--- /dev/null
+++ b/math/rho.cpp
@@ -0,0 +1,22 @@
+ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
+	if (n % 2 == 0) return 2;
+	ll c = rand() % n, x = rand() % n, y = x, d = 1;
+														 // mulmod or int128
+	auto f = [&](ll x){return ((x * x) % n + c) % n;};
+	while (d == 1) {
+		x = f(x); y = f(f(y));
+		d = gcd(abs(x - y), n);
+	}
+	return d == n ? rho(n) : d;
+}
+
+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/simpson.cpp b/math/simpson.cpp
index dd887e2..a99b911 100644
--- a/math/simpson.cpp
+++ b/math/simpson.cpp
@@ -1,12 +1,12 @@
-double f(double x) { return x; }
+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;
+	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) < EPSILON) return tot;
-  return integrate(a, m) + integrate(m, 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/spheres.cpp b/math/spheres.cpp
deleted file mode 100644
index 324eb00..0000000
--- a/math/spheres.cpp
+++ /dev/null
@@ -1,24 +0,0 @@
-// Great Cirlce Distance mit Längen- und Breitengrad.
-double gcDist(
-    double pLat, double pLon, double qLat, double qLon, double radius) {
-  pLat *= PI / 180; pLon *= PI / 180; qLat *= PI / 180; qLon *= PI / 180;
-  return radius * acos(cos(pLat) * cos(pLon) * cos(qLat) * cos(qLon) +
-                       cos(pLat) * sin(pLon) * cos(qLat) * sin(qLon) +
-                       sin(pLat) * sin(qLat));
-}
-
-// Great Cirlce Distance mit kartesischen Koordinaten.
-double gcDist(point p, point q) {
-  return acos(p.x * q.x + p.y * q.y + p.z * q.z);
-}
-
-// 3D Punkt in kartesischen Koordinaten.
-struct point{
-  double x, y, z;
-  point() {}
-  point(double x, double y, double z) : x(x), y(y), z(z) {}
-  point(double lat, double lon) {
-    lat *= PI / 180.0; lon *= PI / 180.0;
-    x = cos(lat) * sin(lon); y = cos(lat) * cos(lon); z = sin(lat);
-  }
-};
diff --git a/math/squfof.cpp b/math/squfof.cpp
new file mode 100644
index 0000000..8a11a77
--- /dev/null
+++ b/math/squfof.cpp
@@ -0,0 +1,89 @@
+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 = 5000;

+

+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
new file mode 100644
index 0000000..53f3758
--- /dev/null
+++ b/math/tables.tex
@@ -0,0 +1,18 @@
+\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
new file mode 100644
index 0000000..878a6b0
--- /dev/null
+++ b/math/tables/binom.tex
@@ -0,0 +1,28 @@
+\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
new file mode 100644
index 0000000..b4c8294
--- /dev/null
+++ b/math/tables/composite.tex
@@ -0,0 +1,26 @@
+\begin{tabularx}{\linewidth}{|r|r|r|CICICICICICICICICICICIC|}
+	\hline
+	\multicolumn{15}{|c|}{Highly Composite Numbers} \\
+	\hline
+	$10^x$ & Zahl & Teiler & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 \\
+	\hline
+	1 & 6 & 4 & 1 & 1 & & & & & & & & & & \\
+	2 & 60 & 12 & 2 & 1 & 1 & & & & & & & & & \\
+	3 & 840 & 32 & 3 & 1 & 1 & 1 & & & & & & & &\\
+	4 & 7560 & 64 & 3 & 3 & 1 & 1 & & & & & & & & \\
+	5 & 83160 & 128 & 3 & 3 & 1 & 1 & 1 & & & & & & & \\
+	6 & 720720 & 240 & 4 & 2 & 1 & 1 & 1 & 1 & & & & & & \\
+	7 & 8648640 & 448 & 6 & 3 & 1 & 1 & 1 & 1 & & & & & & \\
+	8 & 73513440 & 768 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & & & & & \\
+	9 & 735134400 & 1344 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & & & & & \\
+	10 & 6983776800 & 2304 & 5 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & & & & \\
+	11 & 97772875200 & 4032 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & & & & \\
+	12 & 963761198400 & 6720 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & & \\
+	13 & 9316358251200 & 10752 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & \\
+	14 & 97821761637600 & 17280 & 5 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & \\
+	15 & 866421317361600 & 26880 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\
+	16 & 8086598962041600 & 41472 & 8 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\
+	17 & 74801040398884800 & 64512 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
+	18 & 897612484786617600 & 103680 & 8 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
+	\hline
+\end{tabularx}
diff --git a/math/tables/nim.tex b/math/tables/nim.tex
new file mode 100644
index 0000000..75585f4
--- /dev/null
+++ b/math/tables/nim.tex
@@ -0,0 +1,96 @@
+\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}
\ No newline at end of file
diff --git a/math/tables/numbers.tex b/math/tables/numbers.tex
new file mode 100644
index 0000000..1dc9f38
--- /dev/null
+++ b/math/tables/numbers.tex
@@ -0,0 +1,59 @@
+\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
new file mode 100644
index 0000000..f4ee554
--- /dev/null
+++ b/math/tables/platonic.tex
@@ -0,0 +1,39 @@
+\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
new file mode 100644
index 0000000..4f72707
--- /dev/null
+++ b/math/tables/probability.tex
@@ -0,0 +1,27 @@
+\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]}$ &
+	$\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
new file mode 100644
index 0000000..13af68f
--- /dev/null
+++ b/math/tables/series.tex
@@ -0,0 +1,33 @@
+\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}
\ No newline at end of file
diff --git a/math/tables/stuff.tex b/math/tables/stuff.tex
new file mode 100644
index 0000000..5b5093e
--- /dev/null
+++ b/math/tables/stuff.tex
@@ -0,0 +1,32 @@
+\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
new file mode 100644
index 0000000..7f7e27a
--- /dev/null
+++ b/math/tables/twelvefold.tex
@@ -0,0 +1,32 @@
+\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}]$: \lstinline{return Bedingung ? 1 : 0;}
+	} \\
+	\hline
+\end{tabularx}
+\end{expandtable}
\ No newline at end of file
diff --git a/math/transforms/all.cpp b/math/transforms/all.cpp
new file mode 100644
index 0000000..4f4d83b
--- /dev/null
+++ b/math/transforms/all.cpp
@@ -0,0 +1,62 @@
+/*constexpr ll mod = 998244353; @\hl{NTT only}@
+constexpr ll root = 3;*/
+
+using cplx = complex<double>;
+
+@\hl{NTT, xor, or, and}@
+//void fft(vector<ll> &a, bool inverse = 0) {
+void fft(vector<cplx>& a, bool inverse = 0) {
+	int n = a.size();
+	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]);
+	}
+	for (int s = 1; s < n; s *= 2) {
+		/*ll ws = powMod(root, (mod - 1) / s >> 1, mod); @\hl{NTT only}@
+		if (inverse) ws = powMod(ws, mod - 2, mod);*/
+		double angle = PI / s * (inverse ? -1 : 1);
+		cplx ws(cos(angle), sin(angle));
+		for (int j = 0; j < n; j+= 2 * s) {
+			//ll w = 1; @\hl{NTT only}@
+			cplx w = 1;
+			for (int k = 0; k < s; k++) {
+				/*ll u = a[j + k], t = a[j + s + k] * w; @\hl{NTT only}@
+				t %= mod;
+				a[j + k] = (u + t) % mod;
+				a[j + s + k] = (u - t + mod) % mod;
+				w *= ws;
+				w %= mod;*/
+				/*ll u = a[j + k], t = a[j + s + k]; @\hl{xor only}@
+				a[j + k] = u + t;
+				a[j + s + k] = u - t;*/
+				/*if (!inverse) { @\hl{or only}@
+					a[j + k] = u + t;
+					a[j + s + k] = u;
+				} else {
+					a[j + k] = t;
+					a[j + s + k] = u - t;
+				}*/
+				/*if (!inverse) { @\hl{and only}@
+					a[j + k] = t;
+					a[j + s + k] = u + t;
+				} else {
+					a[j + k] = t - u;
+					a[j + s + k] = u;
+				}*/
+				cplx u = a[j + k], t = a[j + s + k] * w;
+				a[j + k] = u + t;
+				a[j + s + k] = u - t;
+				if (inverse) a[j + k] /= 2, a[j + s + k] /= 2;
+				w *= ws;
+	}}}
+	/*if (inverse) { @\hl{NTT only}@
+		ll div = powMod(n, mod - 2, mod);
+		for (ll i = 0; i < n; i++) {
+			a[i] *= div;
+			a[i] %= mod;
+	}}*/
+	/*if (inverse) { @\hl{xor only}@
+		for (ll i = 0; i < n; i++) {
+			a[i] /= n;
+	}}*/
+}
diff --git a/math/transforms/andTransform.cpp b/math/transforms/andTransform.cpp
new file mode 100644
index 0000000..cdc7b22
--- /dev/null
+++ b/math/transforms/andTransform.cpp
@@ -0,0 +1,17 @@
+void fft(vector<cplx>& a, bool inverse = 0) {
+	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]);
+	}
+	for (int s = 1; s < n; s *= 2) {
+		for (int j = 0; j < n; j+= 2 * s) {
+			for (int k = 0; k < s; k++) {
+				ll u = a[j + k], t = a[j + s + k];
+				if (!inverse) {
+					a[j + k] = t;
+					a[j + s + k] = u + t;
+				} else {
+					a[j + k] = t - u;
+					a[j + s + k] = u;
+}}}}
\ No newline at end of file
diff --git a/math/transforms/fft.cpp b/math/transforms/fft.cpp
new file mode 100644
index 0000000..4540ed8
--- /dev/null
+++ b/math/transforms/fft.cpp
@@ -0,0 +1,20 @@
+using cplx = complex<double>; // Eigene Implementierung ist schneller.
+
+void fft(vector<cplx>& a, bool inverse = 0) {
+	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]);
+	}
+	for (int s = 1; s < n; s *= 2) {
+		double angle = PI / s * (inverse ? -1 : 1);
+		cplx ws(cos(angle), sin(angle));
+		for (int j = 0; j < n; j+= 2 * s) {
+			cplx w = 1;
+			for (int k = 0; k < s; k++) {
+				cplx u = a[j + k], t = a[j + s + k] * w;
+				a[j + k] = u + t;
+				a[j + s + k] = u - t;
+				if (inverse) a[j + k] /= 2, a[j + s + k] /= 2;
+				w *= ws;
+}}}}
diff --git a/math/transforms/fftMul.cpp b/math/transforms/fftMul.cpp
new file mode 100644
index 0000000..dc19412
--- /dev/null
+++ b/math/transforms/fftMul.cpp
@@ -0,0 +1,14 @@
+vector<cplx> mul(vector<cplx>& a, vector<cplx>& b) {
+	vector<cplx> c(a.size()), d(a.size());
+	for (int i = 0; i < b.size(); i++) {
+		c[i] = {real(a[i]), real(b[i])};
+	}
+	c = fft(c);
+	for (int i = 0; i < b.size(); i++) {
+		int j = (a.size() - i) % a.size();
+		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/fftPerm.cpp b/math/transforms/fftPerm.cpp
new file mode 100644
index 0000000..2b6fb10
--- /dev/null
+++ b/math/transforms/fftPerm.cpp
@@ -0,0 +1,8 @@
+int perm[MAXN]; //perm[i] = j in Zeile 10
+void genPerm(int n){
+	ull mask = ~0ull << (__lg(n) - 1);
+	for (int i = 0, j = 0; i < n; i++) {
+		perm[i] = j; //if (i < j) swap(a[i], a[j]);
+		ull y = mask >> __builtin_ctz(~i);
+		j ^= y & (n - 1);
+}}
diff --git a/math/transforms/ntt.cpp b/math/transforms/ntt.cpp
new file mode 100644
index 0000000..e1e4588
--- /dev/null
+++ b/math/transforms/ntt.cpp
@@ -0,0 +1,28 @@
+constexpr ll mod = 998244353;
+constexpr ll root = 3;
+
+void fft(vector<ll>& a, bool inverse = 0) {
+	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]);
+	}
+	for (int s = 1; s < n; s *= 2) {
+		ll ws = powMod(root, (mod - 1) / s >> 1, mod);
+		if (inverse) ws = powMod(ws, mod - 2, mod);
+		for (int j = 0; j < n; j+= 2 * s) {
+			ll w = 1;
+			for (int k = 0; k < s; k++) {
+				ll u = a[j + k], t = a[j + s + k] * w;
+				t %= mod;
+				a[j + k] = (u + t) % mod;
+				a[j + s + k] = (u - t + mod) % mod;
+				w *= ws;
+				w %= mod;
+	}}}
+	if (inverse) {
+		ll div = powMod(n, mod - 2, mod);
+		for (ll i = 0; i < n; i++) {
+			a[i] *= div;
+			a[i] %= mod;
+}}}
diff --git a/math/transforms/orTransform.cpp b/math/transforms/orTransform.cpp
new file mode 100644
index 0000000..fdb5bb8
--- /dev/null
+++ b/math/transforms/orTransform.cpp
@@ -0,0 +1,17 @@
+void fft(vector<ll>& a, bool inverse = 0) {
+	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]);
+	}
+	for (int s = 1; s < n; s *= 2) {
+		for (int j = 0; j < n; j+= 2 * s) {
+			for (int k = 0; k < s; k++) {
+				ll u = a[j + k], t = a[j + s + k];
+				if (!inverse) {
+					a[j + k] = u + t;
+					a[j + s + k] = u;
+				} else {
+					a[j + k] = t;
+					a[j + s + k] = u - t;
+}}}}}
diff --git a/math/transforms/xorTransform.cpp b/math/transforms/xorTransform.cpp
new file mode 100644
index 0000000..48e4df2
--- /dev/null
+++ b/math/transforms/xorTransform.cpp
@@ -0,0 +1,17 @@
+void fft(vector<ll>& a, bool inverse = 0) {
+	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]);
+	}
+	for (int s = 1; s < n; s *= 2) {
+		for (int j = 0; j < n; j+= 2 * s) {
+			for (int k = 0; k < s; k++) {
+				ll u = a[j + k], t = a[j + s + k];
+				a[j + k] = u + t;
+				a[j + s + k] = u - t;
+	}}}
+	if (inverse) {
+		for (ll i = 0; i < n; i++) {
+			a[i] /= n;
+}}}