normalize newlines

3 files changed, 973 insertions, 973 deletions

diff --git a/content/math/math.tex b/content/math/math.tex
index bcb4275..1bcf85d 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -1,595 +1,595 @@
-\section{Mathe}

-

-\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}

-\columnbreak

-

-\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}

-\columnbreak

-

-\subsection{Potenzen in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$}

-	\begin{methods}

-		\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}

-	\end{methods}

-	\sourcecode{math/modPowIterativ.cpp}

-	\begin{itemize}

-		\item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!

-	\end{itemize}

-

-\optional{

-\subsection{Multiplikation in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$ \opthint}

-	\begin{methods}

-		\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}

-	\end{methods}

-	\sourcecode{math/modMulIterativ.cpp}

-}

-

-\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}

-	\runtime{\log(a) + \log(b)}

-	\sourcecode{math/extendedEuclid.cpp}

-\end{algorithm}

-

-\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$}

-\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$

-

-\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:}

-\begin{itemize}

-	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit

-	$\alpha x + \beta m = 1$.

-	\item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$.

-	\item $x^{-1} :\equiv \alpha \bmod m$

-\end{itemize}

-\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$.

-% \sourcecode{math/multInv.cpp}

-\sourcecode{math/shortModInv.cpp}

-

-\paragraph{Lemma von \textsc{Bézout}}

-Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.

-Dann lassen sich wie folgt alle Lösungen berechnen:

-\[

-\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)

-\]

-

-\paragraph{\textsc{Pell}-Gleichungen}

-Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.

-Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen

-sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:

-\begin{align*}

-	x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\

-	x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k

-\end{align*}

-

-\begin{algorithm}{Lineare Kongruenz}

-	\begin{itemize}

-		\item Kleinste Lösung $x$ für $ax\equiv b\pmod{m}$.

-		\item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt

-		also $g$ Lösungen modulo $m$.

-	\end{itemize}

-	\sourcecode{math/linearCongruence.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Chinesischer Restsatz}

-	\begin{itemize}

-		\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.

-		\item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:

-		\[

-		x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}

-		\qquad \text{mit} \qquad

-		d := \ggT(n, m) = yn + zm

-		\]

-		Formel kann auch für nicht teilerfremde Moduli verwendet werden.

-		Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,

-		wenn $a\equiv~b \bmod \ggT(m, n)$.

-		In diesem Fall sind keine Faktoren

-		auf der linken Seite erlaubt.

- 	\end{itemize}

- 	\sourcecode{math/chineseRemainder.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Primzahltest \& Faktorisierung}

-	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}

-	\sourcecode{math/millerRabin.cpp}

-	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}

-	\sourcecode{math/rho.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Teiler}

-	\begin{methods}

-		\method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}}

-	\end{methods}

-	\sourcecode{math/divisors.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Matrix-Exponent}

-	\begin{methods}

-		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}

-		\method{calc}{berechnet $m^b \cdot v$}{\log(b)\cdot n^2}

-	\end{methods}

-	\textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$.

-	\sourcecode{math/matrixPower.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Lineare Rekurrenz}

-	\begin{methods}

-		\method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2}

-		\method{}{aus den ersten $2n$ Werte}{}

-	\end{methods}

-	\sourcecode{math/berlekampMassey.cpp}

-	Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz.

-	

-	\begin{methods}

-		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)}

-	\end{methods}

-	Die Polynom-Multiplikation kann auch mit NTT gemacht werden!

-	\sourcecode{math/linearRecurrence.cpp}

-	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:

-	$$\renewcommand\arraystretch{1.5}

-	\setlength\arraycolsep{3pt}

-	\begin{pmatrix}

-		c_{0} & c_{1} & \smash{\cdots} & \smash{\cdots} & c_{n-1} \\

-		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\

-		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\

-		\smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\

-		0 & \smash{\cdots} & 0 & 1 & 0 \\

-	\end{pmatrix}^k

-	\times~~

-	\begin{pmatrix}

-		f(n-1) \\

-		f(n-2) \\

-		\smash{\vdots} \\

-		\smash{\vdots} \\

-		f(0) \\

-	\end{pmatrix}

-	~~=~~

-	\begin{pmatrix}

-		f(n-1+k) \\

-		f(n-2+k) \\

-		\smash{\vdots} \\

-		\smash{\vdots} \\

-		f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\

-	\end{pmatrix}

-	$$

-\end{algorithm}

-

-\begin{algorithm}{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}

-

-\begin{algorithm}{Diskrete Quadratwurzel}

-	\begin{methods}

-		\method{sqrtMod}{bestimmt Lösung $x$ für $x^2=a \bmod p$ }{\log(p)}

-	\end{methods}

-	\textbf{Wichtig:} $p$ muss prim sein!

-	\sourcecode{math/sqrtModCipolla.cpp}

-\end{algorithm}

-%\columnbreak

-

-\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}{Diskrete \textrm{\textit{n}}-te Wurzel}

-	\begin{methods}

-		\method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}

-	\end{methods}

-	Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$

-	\sourcecode{math/discreteNthRoot.cpp}

-\end{algorithm}

-

-\begin{algorithm}{\textsc{Legendre}-Symbol}

-	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:

-	\vspace{-0.15cm}\begin{align*}

-		\hspace*{3cm}\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*}

-	\vspace{-0.05cm}

-	\sourcecode{math/legendre.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Lineares Sieb und multiplikative Funktionen}

-	Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.

-	

-	$\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen.

-	

-	\begin{methods}

-		\method{sieve}{berechnet Primzahlen und co.}{N}

-		\method{sieved}{Wert der entsprechenden multiplikativen Funktion}{1}

-		

-		\method{naive}{Wert der entsprechenden multiplikativen Funktion}{\sqrt{n}}

-	\end{methods}

-	\textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!

-	

-	\sourcecode{math/linearSieve.cpp}

-	\textbf{\textsc{Möbius} Funktion:}

-	\begin{itemize}

-		\item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat

-		\item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat

-		\item $\mu(n)=0$, falls $n$ nicht quadratfrei ist

-	\end{itemize}

-

-	\textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:}

-	\begin{itemize}

-		\item Zählt die relativ primen Zahlen $\leq n$.			

-		\item $p$ prim, $k \in \mathbb{N}$:

-		$~\varphi(p^k) = p^k - p^{k - 1}$

-		

-		\item \textbf{\textsc{Euler}'s Theorem:}

-		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.

-		Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:

-		$a^{m} \equiv a \pmod{m}$

-	\end{itemize}

-\end{algorithm}

-

-\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}

-	\begin{itemize}

-		\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)

-	\end{itemize}

-	\begin{methods}

-		\method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))}

-		\method{isPrime}{prüft ob Zahl prim ist}{1}

-	\end{methods}

-	\sourcecode{math/primeSieve.cpp}

-\end{algorithm}

-

-\begin{algorithm}{\textsc{Möbius}-Inversion}

-	\begin{itemize}

-		\item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und  $g(n) := \sum_{d \vert n}f(d)$.

-		Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.

-		\item $\sum\limits_{d \vert n}\mu(d) =

-		\begin{cases*}

-			1 & falls $n = 1$\\

-			0 & sonst

-		\end{cases*}$

-	\end{itemize}

-	\textbf{Beispiel Inklusion/Exklusion:}

-	Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline

-	\textbf{Lösung}:

-	Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$.

-	Es gibt $2^{[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten.

-	Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.

-\end{algorithm}

-

-\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}

-\method{gauss}{löst LGS}{n^3}

-\sourcecode{math/lgsFp.cpp}

-

-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}

-\method{gauss}{löst LGS}{n^3}

-\sourcecode{math/gauss.cpp}

-

-\begin{algorithm}{Inversionszahl}

-	\vspace{-2pt}

-	\sourcecode{math/inversions.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Numerisch Extremstelle bestimmen}

-	\sourcecode{math/goldenSectionSearch.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}

-	\sourcecode{math/simpson.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}

-	\label{fft}

-	Multipliziert Polynome $A$ und $B$.

-	\ifthenelse{\isundefined{\srclink}}{}{%

-		\hfill

-		\begin{ocg}[printocg=never]{Source links}{srclinks}{1}%

-			\href{\srclink{math/transforms/}}{\faExternalLink}%

-		\end{ocg}%

-	}

-	\begin{itemize}

-		\item $\deg(A \cdot B) = \deg(A) + \deg(B)$

-		\item Vektoren \code{a} und \code{b} müssen mindestens Größe

-		$\deg(A \cdot B) + 1$ haben.

-		Größe muss eine Zweierpotenz sein.

-		\item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))}

-		\item \emph{or} Transform berechnet sum over subsets

-			$\rightarrow$ inverse für inclusion/exclusion

-	\end{itemize}

-	\sourcecode{math/transforms/fft.cpp}

-	\sourcecode{math/transforms/ntt.cpp}

-	\sourcecode{math/transforms/bitwiseTransforms.cpp}

-	Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!)

-	\sourcecode{math/transforms/fftMul.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Operations on Formal Power Series}

-    \sourcecode{math/transforms/seriesOperations.cpp}

-\end{algorithm}

-

-\subsection{Kombinatorik}

-

-\paragraph{\textsc{Wilson}'s Theorem}

-A number $n$ is prime if and only if

-$(n-1)!\equiv -1\bmod{n}$.\\

-($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)

-\begin{align*}

-	(n-1)!\equiv\begin{cases}

-		-1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\

-		\hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\

-		\hphantom{-}0\bmod{n},&\mathrm{sonst}

-	\end{cases}

-\end{align*}

-

-\paragraph{\textsc{Zeckendorf}'s Theorem}

-Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer

-verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei

-aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\

-\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch

-hineinpasst.

-

-\paragraph{\textsc{Lucas}'s Theorem}

-Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),

-so gilt

-\vspace{-0.75\baselineskip}

-\[

-	\binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}.

-\]

-

-%\begin{algorithm}{Binomialkoeffizienten}

-\paragraph{Binomialkoeffizienten}

-	Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.

-	

-	\input{math/tables/binom}

-	

-	\begin{methods}

-		\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}

-		\method{binom}{berechnet Binomialkoeffizient}{1}

-	\end{methods}

-	\sourcecode{math/binomial0.cpp}

-	Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$

-

-    \begin{methods}

-		\method{binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}

-	\end{methods}

-	\sourcecode{math/binomial1.cpp}

-

-	\optional{

-	\begin{methods}

-		\method{binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n\*\log(n)}

-	\end{methods}

-	\opthint \\

-	\textbf{WICHTIG:} braucht alle Primzahlen $\leq n$

-	\sourcecode{math/binomial2.cpp}

-	}

-

-    \begin{methods}

-		\method{binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}

-	\end{methods}

-	\sourcecode{math/binomial3.cpp}

-%\end{algorithm}

-

-\paragraph{\textsc{Catalan}-Zahlen:}

-$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$

-\begin{itemize}

-	\item Die \textsc{Catalan}-Zahl $C_n$ gibt an:

-	\begin{itemize}

-		\item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.

-		\item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.

-		\item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.

-		\item Anzahl Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren.

-		\item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in

-		einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.

-	\end{itemize}

-\end{itemize}

-\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =

-\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\]

-\begin{itemize}

-	\item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n}

-\end{itemize}

-

-\paragraph{\textsc{Catalan}-Convolution}

-\begin{itemize}

-	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen.

-\end{itemize}

-\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =

-\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\]

-

-\paragraph{\textsc{Euler}-Zahlen:}

-$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$

-

-Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.

-Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.

-Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.

-\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad

-\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}\]

-\[

-\eulerI{n}{k} = [x^k]

-	\left(\sum_{i=0}^\infty (i+1)^n x^i\right)

-	\left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right)

-\]

-

-\paragraph{\textsc{Stirling}-Zahlen 1. Art:}

-$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$

-

-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 eigenen Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.

-\[\stirlingI{0}{0} = 1 \qquad

-\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad

-\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]

-\[

-\stirlingI{n}{k}

-= [x^k]\prod_{i=0}^{n-1} (x+i)

-= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k

-\]

-

-\paragraph{\textsc{Stirling}-Zahlen 2. Art:}

-$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$

-

-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}

-\]

-\[

-\stirlingII{n}{k}

-= [x^k]

-	\left(\sum_{i=0}^\infty \frac{i^n}{i!}x^i\right)

-	\left(\sum_{i=0}^\infty \frac{(-1)^i}{i!}x^i\right)

-= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k

-\]

-

-\paragraph{\textsc{Bell}-Zahlen:}

-$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$

-

-Anzahl der Partitionen von $\{1, \ldots, n\}$.

-Wie \textsc{Stirling}-Zahlen 2. Art 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}

-= n! [x^n] e^{e^x-1}

-\qquad

-B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]

-

-\paragraph{$\boldsymbol{k}$ Partitions:}

-$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$

-

-Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.

-Die Anzahl der Partitionen von $n$ mit größtem Elementen $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)\\

-\end{align*}

-

-\paragraph{Partitions:}

-$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$

-

-\begin{align*}

-	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] \\

-	p(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1}

-	  \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right)

-\end{align*}

-\begin{itemize}

-	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.

-		$\rightarrow$ \runtime{n \sqrt{n}}

-	\item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.

-\end{itemize}

-

-\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}

-\input{math/tables/twelvefold}

-

-\subsection{Platonische Körper}

-\input{math/tables/platonic}

-

-\input{math/tables/probability}

-

-\subsection{Satz von \textsc{Sprague-Grundy}}

-Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:

-\[

-g\left(X\right) := \min\left\{

-\mathbb{Z}_0^+ \setminus

-\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}

-\right\}

-\]

-$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\

-Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.

-

-\subsection{Nim-Spiele}

-\begin{itemize}

-	\item[\ding{182}] letzter gewinnt (normal)

-	\item[\ding{183}] letzter verliert

-\end{itemize}

-\input{math/tables/nim}

-

-\subsection{Verschiedenes}

-\input{math/tables/stuff}

-

-\begin{algorithm}{Div Sum}

-	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m}  \right\rfloor$}{\log(n)}

-	\textbf{Wichtig:} $b$ darf nicht negativ sein!

-	\sourcecode{math/divSum.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Min Mod}

-	\begin{methods}

-		\method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)}

-		\method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{}

-		\method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}

-	\end{methods}

-	\textbf{Wichtig:} $0 \leq a, b, l, r < m$

-	\sourcecode{math/minMod.cpp}

-\end{algorithm}

-

-\subsection{Reihen}

-\input{math/tables/series}

-

-\subsection{Wichtige Zahlen}

-\input{math/tables/prime-composite}

-

-\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }

-\method{recover}{findet $x$ und $y$ für $c=x\*y^{-1}\bmod m$}{\log(m)}

-\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!

-\sourcecode{math/recover.cpp}

-

-\optional{

-\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}

-\begin{methods}

-	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}

-	\method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}

-	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}

-\end{methods}

-\sourcecode{math/piLehmer.cpp}

-

-\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}

-\sourcecode{math/piLegendre.cpp}

-}

-

-\begin{algorithm}[optional]{Big Integers}

-	\sourcecode{math/bigint.cpp}

-\end{algorithm}

+\section{Mathe}
+
+\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}
+\columnbreak
+
+\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}
+\columnbreak
+
+\subsection{Potenzen in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$}
+	\begin{methods}
+		\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
+	\end{methods}
+	\sourcecode{math/modPowIterativ.cpp}
+	\begin{itemize}
+		\item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
+	\end{itemize}
+
+\optional{
+\subsection{Multiplikation in $\boldsymbol{\mathbb{Z}/n\mathbb{Z}}$ \opthint}
+	\begin{methods}
+		\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
+	\end{methods}
+	\sourcecode{math/modMulIterativ.cpp}
+}
+
+\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
+	\runtime{\log(a) + \log(b)}
+	\sourcecode{math/extendedEuclid.cpp}
+\end{algorithm}
+
+\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$}
+\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$
+
+\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:}
+\begin{itemize}
+	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit
+	$\alpha x + \beta m = 1$.
+	\item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$.
+	\item $x^{-1} :\equiv \alpha \bmod m$
+\end{itemize}
+\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$.
+% \sourcecode{math/multInv.cpp}
+\sourcecode{math/shortModInv.cpp}
+
+\paragraph{Lemma von \textsc{Bézout}}
+Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
+Dann lassen sich wie folgt alle Lösungen berechnen:
+\[
+\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
+\]
+
+\paragraph{\textsc{Pell}-Gleichungen}
+Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
+Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
+sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
+\begin{align*}
+	x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
+	x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
+\end{align*}
+
+\begin{algorithm}{Lineare Kongruenz}
+	\begin{itemize}
+		\item Kleinste Lösung $x$ für $ax\equiv b\pmod{m}$.
+		\item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
+		also $g$ Lösungen modulo $m$.
+	\end{itemize}
+	\sourcecode{math/linearCongruence.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Chinesischer Restsatz}
+	\begin{itemize}
+		\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
+		\item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:
+		\[
+		x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
+		\qquad \text{mit} \qquad
+		d := \ggT(n, m) = yn + zm
+		\]
+		Formel kann auch für nicht teilerfremde Moduli verwendet werden.
+		Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
+		wenn $a\equiv~b \bmod \ggT(m, n)$.
+		In diesem Fall sind keine Faktoren
+		auf der linken Seite erlaubt.
+ 	\end{itemize}
+ 	\sourcecode{math/chineseRemainder.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Primzahltest \& Faktorisierung}
+	\method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
+	\sourcecode{math/millerRabin.cpp}
+	\method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
+	\sourcecode{math/rho.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Teiler}
+	\begin{methods}
+		\method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
+	\end{methods}
+	\sourcecode{math/divisors.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Matrix-Exponent}
+	\begin{methods}
+		\method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
+		\method{calc}{berechnet $m^b \cdot v$}{\log(b)\cdot n^2}
+	\end{methods}
+	\textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$.
+	\sourcecode{math/matrixPower.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lineare Rekurrenz}
+	\begin{methods}
+		\method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2}
+		\method{}{aus den ersten $2n$ Werte}{}
+	\end{methods}
+	\sourcecode{math/berlekampMassey.cpp}
+	Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz.
+	
+	\begin{methods}
+		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)}
+	\end{methods}
+	Die Polynom-Multiplikation kann auch mit NTT gemacht werden!
+	\sourcecode{math/linearRecurrence.cpp}
+	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
+	$$\renewcommand\arraystretch{1.5}
+	\setlength\arraycolsep{3pt}
+	\begin{pmatrix}
+		c_{0} & c_{1} & \smash{\cdots} & \smash{\cdots} & c_{n-1} \\
+		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
+		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
+		\smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
+		0 & \smash{\cdots} & 0 & 1 & 0 \\
+	\end{pmatrix}^k
+	\times~~
+	\begin{pmatrix}
+		f(n-1) \\
+		f(n-2) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(0) \\
+	\end{pmatrix}
+	~~=~~
+	\begin{pmatrix}
+		f(n-1+k) \\
+		f(n-2+k) \\
+		\smash{\vdots} \\
+		\smash{\vdots} \\
+		f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
+	\end{pmatrix}
+	$$
+\end{algorithm}
+
+\begin{algorithm}{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}
+
+\begin{algorithm}{Diskrete Quadratwurzel}
+	\begin{methods}
+		\method{sqrtMod}{bestimmt Lösung $x$ für $x^2=a \bmod p$ }{\log(p)}
+	\end{methods}
+	\textbf{Wichtig:} $p$ muss prim sein!
+	\sourcecode{math/sqrtModCipolla.cpp}
+\end{algorithm}
+%\columnbreak
+
+\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}{Diskrete \textrm{\textit{n}}-te Wurzel}
+	\begin{methods}
+		\method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
+	\end{methods}
+	Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
+	\sourcecode{math/discreteNthRoot.cpp}
+\end{algorithm}
+
+\begin{algorithm}{\textsc{Legendre}-Symbol}
+	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
+	\vspace{-0.15cm}\begin{align*}
+		\hspace*{3cm}\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*}
+	\vspace{-0.05cm}
+	\sourcecode{math/legendre.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lineares Sieb und multiplikative Funktionen}
+	Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.
+	
+	$\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen.
+	
+	\begin{methods}
+		\method{sieve}{berechnet Primzahlen und co.}{N}
+		\method{sieved}{Wert der entsprechenden multiplikativen Funktion}{1}
+		
+		\method{naive}{Wert der entsprechenden multiplikativen Funktion}{\sqrt{n}}
+	\end{methods}
+	\textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!
+	
+	\sourcecode{math/linearSieve.cpp}
+	\textbf{\textsc{Möbius} Funktion:}
+	\begin{itemize}
+		\item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat
+		\item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat
+		\item $\mu(n)=0$, falls $n$ nicht quadratfrei ist
+	\end{itemize}
+
+	\textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:}
+	\begin{itemize}
+		\item Zählt die relativ primen Zahlen $\leq n$.			
+		\item $p$ prim, $k \in \mathbb{N}$:
+		$~\varphi(p^k) = p^k - p^{k - 1}$
+		
+		\item \textbf{\textsc{Euler}'s Theorem:}
+		Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
+		Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
+		$a^{m} \equiv a \pmod{m}$
+	\end{itemize}
+\end{algorithm}
+
+\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
+	\begin{itemize}
+		\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
+	\end{itemize}
+	\begin{methods}
+		\method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))}
+		\method{isPrime}{prüft ob Zahl prim ist}{1}
+	\end{methods}
+	\sourcecode{math/primeSieve.cpp}
+\end{algorithm}
+
+\begin{algorithm}{\textsc{Möbius}-Inversion}
+	\begin{itemize}
+		\item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und  $g(n) := \sum_{d \vert n}f(d)$.
+		Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
+		\item $\sum\limits_{d \vert n}\mu(d) =
+		\begin{cases*}
+			1 & falls $n = 1$\\
+			0 & sonst
+		\end{cases*}$
+	\end{itemize}
+	\textbf{Beispiel Inklusion/Exklusion:}
+	Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline
+	\textbf{Lösung}:
+	Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$.
+	Es gibt $2^{[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten.
+	Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
+\end{algorithm}
+
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
+
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/gauss.cpp}
+
+\begin{algorithm}{Inversionszahl}
+	\vspace{-2pt}
+	\sourcecode{math/inversions.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+	\sourcecode{math/goldenSectionSearch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+	\sourcecode{math/simpson.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
+	\label{fft}
+	Multipliziert Polynome $A$ und $B$.
+	\ifthenelse{\isundefined{\srclink}}{}{%
+		\hfill
+		\begin{ocg}[printocg=never]{Source links}{srclinks}{1}%
+			\href{\srclink{math/transforms/}}{\faExternalLink}%
+		\end{ocg}%
+	}
+	\begin{itemize}
+		\item $\deg(A \cdot B) = \deg(A) + \deg(B)$
+		\item Vektoren \code{a} und \code{b} müssen mindestens Größe
+		$\deg(A \cdot B) + 1$ haben.
+		Größe muss eine Zweierpotenz sein.
+		\item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))}
+		\item \emph{or} Transform berechnet sum over subsets
+			$\rightarrow$ inverse für inclusion/exclusion
+	\end{itemize}
+	\sourcecode{math/transforms/fft.cpp}
+	\sourcecode{math/transforms/ntt.cpp}
+	\sourcecode{math/transforms/bitwiseTransforms.cpp}
+	Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!)
+	\sourcecode{math/transforms/fftMul.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Operations on Formal Power Series}
+    \sourcecode{math/transforms/seriesOperations.cpp}
+\end{algorithm}
+
+\subsection{Kombinatorik}
+
+\paragraph{\textsc{Wilson}'s Theorem}
+A number $n$ is prime if and only if
+$(n-1)!\equiv -1\bmod{n}$.\\
+($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)
+\begin{align*}
+	(n-1)!\equiv\begin{cases}
+		-1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\
+		\hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\
+		\hphantom{-}0\bmod{n},&\mathrm{sonst}
+	\end{cases}
+\end{align*}
+
+\paragraph{\textsc{Zeckendorf}'s Theorem}
+Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer
+verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei
+aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\
+\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch
+hineinpasst.
+
+\paragraph{\textsc{Lucas}'s Theorem}
+Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),
+so gilt
+\vspace{-0.75\baselineskip}
+\[
+	\binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}.
+\]
+
+%\begin{algorithm}{Binomialkoeffizienten}
+\paragraph{Binomialkoeffizienten}
+	Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
+	
+	\input{math/tables/binom}
+	
+	\begin{methods}
+		\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
+		\method{binom}{berechnet Binomialkoeffizient}{1}
+	\end{methods}
+	\sourcecode{math/binomial0.cpp}
+	Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$
+
+    \begin{methods}
+		\method{binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
+	\end{methods}
+	\sourcecode{math/binomial1.cpp}
+
+	\optional{
+	\begin{methods}
+		\method{binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n\*\log(n)}
+	\end{methods}
+	\opthint \\
+	\textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
+	\sourcecode{math/binomial2.cpp}
+	}
+
+    \begin{methods}
+		\method{binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
+	\end{methods}
+	\sourcecode{math/binomial3.cpp}
+%\end{algorithm}
+
+\paragraph{\textsc{Catalan}-Zahlen:}
+$1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~16796,~58786,~208012,~742900$
+\begin{itemize}
+	\item Die \textsc{Catalan}-Zahl $C_n$ gibt an:
+	\begin{itemize}
+		\item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.
+		\item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.
+		\item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.
+		\item Anzahl Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren.
+		\item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
+		einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
+	\end{itemize}
+\end{itemize}
+\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
+\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} C_{n-1} \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}\]
+\begin{itemize}
+	\item Formel $1$ ohne Division in \runtime{n^2}, Formel $2$ und $3$ in \runtime{n}
+\end{itemize}
+
+\paragraph{\textsc{Catalan}-Convolution}
+\begin{itemize}
+	\item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $\texttt{(}^k$ beginnen.
+\end{itemize}
+\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =
+\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)(2n+k)}{n(n+k+1)} C_{n-1}\]
+
+\paragraph{\textsc{Euler}-Zahlen:}
+$|~1~|~1~|~1,~1~|~1,~4,~1~|~1,~11,~11,~1~|~1,~26,~66,~26,~1~|$
+
+Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
+Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
+Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
+\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad
+\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}\]
+\[
+\eulerI{n}{k} = [x^k]
+	\left(\sum_{i=0}^\infty (i+1)^n x^i\right)
+	\left(\sum_{i=0}^\infty (-1)^i \binom{n+1}{i} x^i\right)
+\]
+
+\paragraph{\textsc{Stirling}-Zahlen 1. Art:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~2,~3,~1~|~0,~6,~11,~6,~1~|$
+
+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 eigenen Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
+\[\stirlingI{0}{0} = 1 \qquad
+\stirlingI{n}{0} = \stirlingI{0}{k} = 0 \qquad
+\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
+\[
+\stirlingI{n}{k}
+= [x^k]\prod_{i=0}^{n-1} (x+i)
+= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{i+1}x^i\right)^k
+\]
+
+\paragraph{\textsc{Stirling}-Zahlen 2. Art:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~3,~1~|~0,~1,~7,~6,~1~|$
+
+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}
+\]
+\[
+\stirlingII{n}{k}
+= [x^k]
+	\left(\sum_{i=0}^\infty \frac{i^n}{i!}x^i\right)
+	\left(\sum_{i=0}^\infty \frac{(-1)^i}{i!}x^i\right)
+= n! [x^{n-k}] \frac{1}{k!} \left(\sum_{i=0}^\infty \frac{1}{(i+1)!}x^i\right)^k
+\]
+
+\paragraph{\textsc{Bell}-Zahlen:}
+$1,~1,~2,~5,~15,~52,~203,~877,~4140,~21147,~115975,~678570,~4213597$
+
+Anzahl der Partitionen von $\{1, \ldots, n\}$.
+Wie \textsc{Stirling}-Zahlen 2. Art 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}
+= n! [x^n] e^{e^x-1}
+\qquad
+B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
+
+\paragraph{$\boldsymbol{k}$ Partitions:}
+$|~1~|~0,~1~|~0,~1,~1~|~0,~1,~1,~1~|~0,~1,~2,~1,~1~|~0,~1,~2,~2,~1,~1~|~0,~1,~3,~3,~2,~1,~1~|$
+
+Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
+Die Anzahl der Partitionen von $n$ mit größtem Elementen $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)\\
+\end{align*}
+
+\paragraph{Partitions:}
+$1,~1,~2,~3,~5,~7,~11,~15,~22,~30,~42,~56,~77,~101,~135,~176,~231,~297,~385,~490,~627$
+
+\begin{align*}
+	p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg] \\
+	p(n)&=[x^n] \left(\sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}\right)^{-1}
+	  \sim \frac{1}{4 \sqrt{3} n} \exp\left(\pi \sqrt{\frac{2n}{3}}\right)
+\end{align*}
+\begin{itemize}
+	\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
+		$\rightarrow$ \runtime{n \sqrt{n}}
+	\item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.
+\end{itemize}
+
+\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
+\input{math/tables/twelvefold}
+
+\subsection{Platonische Körper}
+\input{math/tables/platonic}
+
+\input{math/tables/probability}
+
+\subsection{Satz von \textsc{Sprague-Grundy}}
+Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
+\[
+g\left(X\right) := \min\left\{
+\mathbb{Z}_0^+ \setminus
+\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
+\right\}
+\]
+$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\
+Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
+
+\subsection{Nim-Spiele}
+\begin{itemize}
+	\item[\ding{182}] letzter gewinnt (normal)
+	\item[\ding{183}] letzter verliert
+\end{itemize}
+\input{math/tables/nim}
+
+\subsection{Verschiedenes}
+\input{math/tables/stuff}
+
+\begin{algorithm}{Div Sum}
+	\method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m}  \right\rfloor$}{\log(n)}
+	\textbf{Wichtig:} $b$ darf nicht negativ sein!
+	\sourcecode{math/divSum.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Min Mod}
+	\begin{methods}
+		\method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)}
+		\method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{}
+		\method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
+	\end{methods}
+	\textbf{Wichtig:} $0 \leq a, b, l, r < m$
+	\sourcecode{math/minMod.cpp}
+\end{algorithm}
+
+\subsection{Reihen}
+\input{math/tables/series}
+
+\subsection{Wichtige Zahlen}
+\input{math/tables/prime-composite}
+
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $c=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{math/recover.cpp}
+
+\optional{
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\begin{methods}
+	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
+	\method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
+	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
+\end{methods}
+\sourcecode{math/piLehmer.cpp}
+
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\sourcecode{math/piLegendre.cpp}
+}
+
+\begin{algorithm}[optional]{Big Integers}
+	\sourcecode{math/bigint.cpp}
+\end{algorithm}
diff --git a/content/math/piLehmer.cpp b/content/math/piLehmer.cpp
index adef16d..83e1b95 100644
--- a/content/math/piLehmer.cpp
+++ b/content/math/piLehmer.cpp
@@ -1,52 +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(); // @\sourceref{math/primeSieve.cpp}@

-	for (ll i = 1; 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;

-}

+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(); // @\sourceref{math/primeSieve.cpp}@
+	for (ll i = 1; i < N; i++) {
+		memoC[i] = memoC[i - 1];
+		if (isPrime(i)) memoC[i]++;
+	}
+	memoB[0] = 1;
+	for(ll i = 0; i <= cacheA; i++) memoA[i][0] = i;
+	for(ll i = 1; i <= cacheB; i++) {
+		memoB[i] = primes[i - 1] * memoB[i - 1];
+		for(ll j = 1; j <= cacheA; j++) {
+			memoA[j][i] = memoA[j][i - 1] - memoA[j /
+			              primes[i - 1]][i - 1];
+}}}
+
+ll phi(ll n, ll k) {
+	if(k == 0) return n;
+	if(k <= cacheB) 
+		return memoA[n % memoB[k]][k] + 
+					 (n / memoB[k]) * memoA[memoB[k]][k];
+	if(n <= primes[k - 1]*primes[k - 1]) return memoC[n] - k + 1;
+	if(n <= primes[k - 1]*primes[k - 1]*primes[k - 1] && n < N) {
+		ll b = memoC[(ll)sqrtl(n)];
+		ll res = memoC[n] - (b + k - 2) * (b - k + 1) / 2;
+		for(ll i = k; i < b; i++) res += memoC[n / primes[i]];
+		return res;
+	}
+	return phi(n, k - 1) - phi(n / primes[k - 1], k - 1);
+}
+
+ll pi(ll n) {
+	if (n < N) return memoC[n];
+	ll a = pi(sqrtl(sqrtl(n)));
+	ll b = pi(sqrtl(n));
+	ll c = pi(cbrtl(n));
+	ll res = phi(n, a) + (b + a - 2) * (b - a + 1) / 2;
+	for (ll i = a; i < b; i++) {
+		ll w = n / primes[i];
+		res -= pi(w);
+		if (i > c) continue;
+		ll bi = pi(sqrtl(w));
+		for (ll j = i; j < bi; j++) {
+			res -= pi(w / primes[j]) - j;
+	}}
+	return res;
+}
diff --git a/content/other/other.tex b/content/other/other.tex
index d8726d4..a43aa35 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -1,326 +1,326 @@
-\section{Sonstiges}

-

-\begin{algorithm}{Compiletime}

-	\begin{itemize}

-		\item überprüfen ob Compilezeit Berechnungen erlaubt sind!

-		\item braucht \code{c++14} oder höher!

-	\end{itemize}

-	\sourcecode{other/compiletime.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Timed}

-	Kann benutzt werden um randomisierte Algorithmen so lange wie möglich laufen zu lassen.

-	\sourcecode{other/timed.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Overflow-sichere arithmetische Operationen}

-	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.

-	\begin{expandtable}

-		\begin{tabularx}{\linewidth}{|lR|}

-			\hline

-			Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\

-			Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\

-			Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\

-			\hline

-		\end{tabularx}

-	\end{expandtable}

-\end{algorithm}

-

-\begin{algorithm}{Bit Operations}

-	\begin{expandtable}

-	\begin{tabularx}{\linewidth}{|Ll|}

-		\hline

-		Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\

-		Bit an Position j setzen & \code{x |= (1 << j)} \\

-		Bit an Position j löschen & \code{x \&= ~(1 << j)} \\

-		Bit an Position j flippen & \code{x ^= (1 << j)} \\

-		Anzahl an führenden nullen	($x \neq 0$) & \code{__builtin_clzll(x)} \\

-		Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\

-		Anzahl an \code{1} bits & \code{__builtin_popcountll(x)} \\

-		$i$-te Zahl eines Graycodes & \code{i ^ (i >> 1)} \\

-		\hline

-	\end{tabularx}\\

-	\end{expandtable}

-	\sourcecode{other/bitOps.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Pragmas}

-	\sourcecode{other/pragmas.cpp}

-\end{algorithm}

-

-\begin{algorithm}{DP Optimizations}

-	Aufgabe: Partitioniere Array in genau $m$ zusammenhängende Teile mit minimalen Kosten:

-	$dp[i][j] = \min_{k<j}\{dp[i-1][k-1]+C[k][j]\}$. Es sei $A[i][j]$ das \emph{minimale} optimale

-	$k$ bei der Berechnung von $dp[i][j]$.

-	

-	\paragraph{\textsc{Knuth}-Optimization} Vorbedingung: $A[i - 1][j] \leq A[i][j] \leq A[i][j + 1]$

-	

-	\method{calc}{berechnet das DP}{n^2}

-	\sourcecode{other/knuth.cpp}

-	

-	\paragraph{Divide and Conquer}

-	Vorbedingung: $A[i][j - 1] \leq A[i][j]$.

-	

-	\method{calc}{berechnet das DP}{m\*n\*\log(n)}

-	\sourcecode{other/divideAndConquer.cpp}

-	

-	\paragraph{Quadrangle inequality} Die Bedingung  $\forall a\leq b\leq c\leq d:

-	C[a][d] + C[b][c] \geq C[a][c] + C[b][d]$ ist hinreichend für beide Optimierungen.

-	

-	\paragraph{Sum over Subsets DP} Siehe \emph{or} Transform, Seite \pageref{fft}.

-\end{algorithm}

-

-\begin{algorithm}{Fast Subset Sum}

-	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}

-	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.

-	\sourcecode{other/fastSubsetSum.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Parallel Binary Search}

-	\sourcecode{other/pbs.cpp}

-\end{algorithm}

-

-\columnbreak

-\begin{algorithm}{Josephus-Problem}

-	$n$ Personen im Kreis, jeder $k$-te wird erschossen.

-	\begin{description}

-		\item[Spezialfall $\boldsymbol{k=2}$:] Betrachte $n$ Binär.

-		Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n0$ die Position des letzten Überlebenden.

-	\end{description}

-	\sourcecode{other/josephus2.cpp}

-	

-	\begin{description}

-		\item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden.

-		Nummeriere die Personen mit $0, 1, \ldots, n-1$.

-		Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$.

-		Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$.

-	\end{description}

-	\sourcecode{other/josephusK.cpp}

-\end{algorithm}

-

-\begin{algorithm}[optional]{Zeileneingabe}

-	\sourcecode{other/split.cpp}

-\end{algorithm}

-

-\begin{algorithm}[optional]{Fast IO}

-	\sourcecode{other/fastIO.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Sonstiges}

-	\sourcecode{other/stuff.cpp}

-\end{algorithm}

-

-\begin{algorithm}{Stress Test}

-	\sourcecode{other/stress.sh}

-\end{algorithm}

-

-\clearpage

-\subsection{Gemischtes}

-\begin{itemize}

-	\item \textbf{(Minimum) Flow mit Demand \textit{d}:}

-	Erstelle neue Quelle $s'$ und Senke $t'$ und setzte die folgenden Kapazitäten:

-	\begin{align*}

-		c'(s',v)&=\sum_{u\in{}V}d(u,v)&c'(v,t')&=\sum_{u\in{}V}d(v,u)\\[-0.5ex]

-		c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x

-	\end{align*}

-	Löse Fluss auf $G'$ mit \textsc{Dinitz's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).

-	\item \textbf{\textsc{Johnson}s Reweighting Algorithm:}

-	Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen.

-	Falls es einen negativen Zyklus gibt abrrechen.

-	Sonst ändere die Gewichte von allen Kanten \texttt{(u,v)} im ursprünglichen Graphen zu \texttt{d[u]+w[u,v]-d[v]}.

-	Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden.

-

-	\item \textbf{System von Differenzbeschränkungen:}

-	Ändere alle Bedingungen in die Form $a-b \leq c$.

-	Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gewicht \texttt{c} ein.

-	Füge Quelle \texttt{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0.

-	Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \texttt{s} aus zu finden.

-	\texttt{d[v]} ist mögliche Lösung für \texttt{v}.

-

-	\item \textbf{Min-Weight-Vertex-Cover im Bipartiten Graph:}

-	Partitioniere in \texttt{A, B} und füge Kanten \texttt{s}\,$\rightarrow$\,\texttt{A} mit Gewicht \texttt{w(A)} und Kanten  \texttt{B}\,$\rightarrow$\,\texttt{t} mit Gewicht \texttt{w(B)} hinzu.

-	Füge Kanten mit Kapazität $\infty$ von \texttt{A} nach \texttt{B} hinzu, wo im originalen Graphen Kanten waren.

-	Max-Flow ist die Lösung.\newline

-	Im Residualgraphen:

-	\begin{itemize}

-		\item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder}

-		\item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{s} erreichbar sind.

-	\end{itemize}

-

-	\item \textbf{Allgemeiner Graph:}

-	Das Komplement eines Vertex-Cover ist ein Independent Set.

-	$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.

-

-	\item \textbf{Bipartiter Graph (Satz von \textsc{König}):}

-	Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching.

-	Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$.

-

-	\item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:}

-	Minimiere Matchinggewicht.

-	Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normalen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn})

-

-	\item \textbf{Satz von \textsc{Pick}:}

-	Sei $A$ der Flächeninhalt eines einfachen Gitterpolygons, $I$ die Anzahl der Gitterpunkte im Inneren und $R$ die Anzahl der Gitterpunkte auf dem Rand.

-	Es gilt:\vspace*{-\baselineskip}

-	\[

-		A = I + \frac{R}{2} - 1

-	\]

-

-	\item \textbf{Lemma von \textsc{Burnside}:}

-	Sei $G$ eine endliche Gruppe, die auf der Menge $X$ operiert.

-	Für jedes $g \in G$ sei $X^g$ die Menge der Fixpunkte bei Operation durch $g$, also $X^g = \{x \in X \mid g \bullet x = x\}$.

-	Dann gilt für die Anzahl der Bahnen $[X/G]$ der Operation:

-	\[

-		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} \vert X^g \vert

-	\]

-

-	\item \textbf{\textsc{Polya} Counting:}

-	Sei $\pi$ eine Permutation der Menge $X$.

-	Die Elemente von $X$ können mit einer von $m$ Farben gefärbt werden.

-	Die Anzahl der Färbungen, die Fixpunkte von $\pi$ sind, ist $m^{\#(\pi)}$, wobei $\#(\pi)$ die Anzahl der Zyklen von $\pi$ ist.

-	Die Anzahl der Färbungen von Objekten einer Menge $X$ mit $m$ Farben unter einer Symmetriegruppe $G$ is gegeben durch:

-	\[

-		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} m^{\#(g)}

-	\]

-

-	\item \textbf{\textsc{Bertrand}sches Postulat:}

-	Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$.

-

-	\item \textbf{Satz von \textsc{Kirchhoff} (Anzahl Spannbäume):}

-	Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten.

-	Sei $A$ die Adjazenzmatrix von~$G$.

-	Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$.

-	Sei $B$ eine Diagonalmatrix mit $b_{ii}$ Grad von Knoten $i$.

-	Definiere $R = B - A$.

-	Entferne $k$-te Zeile und $k$-te Spalte ($k$ beliebig) und berechne Betrag der Determinante.

-	Das Ergebnis ist die Anzahl der Spannbäume von $G$.

-	\newline

-	Funktioniert auch für gerichtete Graphen: $b_{ii}$ ist der Outdegree und man

-	berechnet die Determinante nach Entfernen der $k$-ten Zeile und Spalte.

-	Das Ergebnis ist die Anzahl an gerichteten Spannbäumen mit Wurzel $k$,

-	sodass jeder Knoten einen Pfad zu $k$ hat.

-

-	\item \textbf{\textsc{Dilworth}'s Theorem:}

-	Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).

-	Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$.

-	Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist.

-	Eine \emph{Antikette} ist eine Menge von Elementen, die paarweise nicht vergleichbar sind.

-	\newline

-	Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition.

-	$\Rightarrow$ \emph{Weite} des Poset.

-	\newline

-	Berechnung der minimalen Partition: Maximales Matching in bipartitem Graphen.

-	Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.

-	Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.

-	Wenn $u_x$ mit $v_y$ gematched wird, sind $x$ und $y$ in derselben Kette.

-	\newline

-	Berechnung der maximalen Antikette: Verwende Satz von König, um ein

-	minimales Vertexcover des bipartiten Graphen zu finden.

-	Ersetze $u_x, v_x$ durch $x$ und erhalte so minimales Vertexcover vom Poset.

-	Das Komplement davon ist eine maximale Antikette.

-	

-	\item \textbf{\textsc{Tur\'an}'s Theorem:}

-	Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist:

-	\begin{align*}

-	ext(n, K_{x+1}) &= \binom{n}{2} - \left[\left(x - (n \bmod x)\right) \cdot \binom{\floor{\frac{n}{x}}}{2} + \left(n\bmod x\right)  \cdot \binom{\ceil{\frac{n}{x}}}{2}\right]

-	\end{align*}

-	

-	\item \textbf{\textsc{Euler}scher Polyedersatz:}

-	In planaren Graphen gilt $n-m+f-c=1$.

-	

-	\item \textbf{\textsc{Pythagoreische Tripel}:}

-	Sei $m>n>0,~k>0$ und $m\not\equiv n \bmod 2$ dann beschreibt diese Formel alle Pythagoreischen Tripel eindeutig:

-	\[k~\cdot~\Big(~a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2~\Big)\]

-	

-	\item \textbf{Centroids of a Tree:}

-	Ein \emph{Centroid} ist ein Knoten, der einen Baum in Komponenten der maximalen Größe $\frac{\abs{V}}{2}$ splitted.

-	Es kann $2$ Centroids geben!

-	

-	\item \textbf{Centroid Decomposition:}

-	Wähle zufälligen Knoten und mache DFS.

-	Verschiebe ausgewählten Knoten in Richtung des tiefsten Teilbaums, bis Centroid gefunden. Entferne Knoten, mache rekursiv in Teilbäumen weiter. Laufzeit:~\runtime{\abs{V} \cdot \log(\abs{V})}.

-	\item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres ist alle $400$ Jahre gleich.

-

-	\item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:}

-	Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von

-	$\runtime{n^2}$ zu $\runtime{n\log n}$ zu verbessern.

-	

-	\item \textbf{\textsc{Mo}'s Algorithm:}

-	SQRT-Decomposition auf $n$ Intervall Queries $[l,r]$.

-	Gruppiere Queries in $\sqrt{n}$ Blöcke nach linker Grenze $l$.

-	Sortiere nach Block und bei gleichem Block nach rechter Grenze $r$.

-	Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls.

-	Laufzeit:~\runtime{n\cdot\sqrt{n}}.

-	(Anzahl der Blöcke als Konstante in Code schreiben.)

-	

-	\item \textbf{SQRT Techniques:}

-	\begin{itemize}

-		\item Aufteilen in \emph{leichte} (wert $\leq\sqrt{x}$) und \emph{schwere} (höchsten $\sqrt{x}$ viele) Objekte.

-		\item Datenstruktur in Blöcke fester Größe (z.b. 256 oder 512) aufteilen.

-		\item Datenstruktur nach fester Anzahl Updates komplett neu bauen.

-		\item Wenn die Summe über $x_i$ durch $X$ beschränkt ist, dann gibt es nur $\sqrt{2X}$ verschiedene Werte von $x_i$ (z.b. Längen von Strings).

-		\item Wenn $w\cdot h$ durch $X$ beschränkt ist, dann ist $\min(w,h)\leq\sqrt{X}$.

-	\end{itemize}

-

-	\item \textbf{Partition:}

-	Gegeben Gewichte $w_0+w_1+\cdots+w_k=W$, existiert eine Teilmenge mit Gewicht $x$?

-	Drei gleiche Gewichte $w$ können zu $w$ und $2w$ kombiniert werden ohne die Lösung zu ändern $\Rightarrow$ nur $2\sqrt{W}$ unterschiedliche Gewichte.

-	Mit bitsets daher selbst für $10^5$ lösbar.

-\end{itemize}

-

-\subsection{Tipps \& Tricks}

-

-\begin{itemize}

-	\item \textbf{Run Time Error:}

-	\begin{itemize}

-		\item Stack Overflow? Evtl. rekursive Tiefensuche auf langem Pfad?

-		\item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen?

-		\item Abbruchbedingung bei Rekursion?

-		\item Evtl. Memory Limit Exceeded? Mit \code{/usr/bin/time -v} erhält man den maximalen Speicherverbrauch bei der Ausführung (Maximum resident set size).

-	\end{itemize}

-	

-	\item \textbf{Strings:}

-	\begin{itemize}

-		\item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?

-		\item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.

-	\end{itemize}

-

-	\item \textbf{Zeilenbasierte Eingabe}:

-	\begin{itemize}

-		\item \code{getline(cin, str)} liest Zeile ein.

-		\item Wenn vorher \code{cin >> ...} benutzt, lese letztes \code{\\n} mit \code{getline(cin, x)}.

-	\end{itemize}

-	

-	\item \textbf{Gleitkommazahlen:}

-	\begin{itemize}

-		\item \code{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\code{acos(1.00000000000001)}}?

-		\item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!

-		\item genügend Präzision oder Output in wissenschaftlicher Notation (\code{1e-25})?

-		\item Kann \code{-0.000} ausgegeben werden?

-	\end{itemize}

-

-	\item \textbf{Wrong Answer:}

-	\begin{itemize}

-		\item Lies Aufgabe erneut. Sorgfältig!

-		\item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander.

-		\item Integer Overflow? Teste maximale Eingabegrößen und mache Überschlagsrechnung.

-		\item Ausgabeformat im 'unmöglich'-Fall überprüfen.

-		\item Ist das Ergebnis modulo einem Wert?

-		\item Integer Division rundet zur $0$ $\neq$ abrunden.

-		\item Eingabegrößen überprüfen. Sonderfälle ausprobieren.

-		\begin{itemize}

-			\item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31}$

-			\item $n$ gerade/ungerade

-			\item Graph ist leer/enthält nur einen Knoten.

-			\item Liste ist leer/enthält nur ein Element.

-			\item Graph ist Multigraph (enthält Schleifen/Mehrfachkanten).

-			\item Sind Kanten gerichtet/ungerichtet?

-			\item Kolineare Punkte existieren.

-			\item Polygon ist konkav/selbstschneidend.

-		\end{itemize}

-		\item Bei DP/Rekursion: Stimmt Basisfall?

-		\item Unsicher bei benutzten STL-Funktionen?

-	\end{itemize}

-\end{itemize}

-

-%\input{other/simd}

+\section{Sonstiges}
+
+\begin{algorithm}{Compiletime}
+	\begin{itemize}
+		\item überprüfen ob Compilezeit Berechnungen erlaubt sind!
+		\item braucht \code{c++14} oder höher!
+	\end{itemize}
+	\sourcecode{other/compiletime.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Timed}
+	Kann benutzt werden um randomisierte Algorithmen so lange wie möglich laufen zu lassen.
+	\sourcecode{other/timed.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Overflow-sichere arithmetische Operationen}
+	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
+	\begin{expandtable}
+		\begin{tabularx}{\linewidth}{|lR|}
+			\hline
+			Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\
+			Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\
+			Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\
+			\hline
+		\end{tabularx}
+	\end{expandtable}
+\end{algorithm}
+
+\begin{algorithm}{Bit Operations}
+	\begin{expandtable}
+	\begin{tabularx}{\linewidth}{|Ll|}
+		\hline
+		Bit an Position j lesen & \code{(x \& (1 << j)) != 0} \\
+		Bit an Position j setzen & \code{x |= (1 << j)} \\
+		Bit an Position j löschen & \code{x \&= ~(1 << j)} \\
+		Bit an Position j flippen & \code{x ^= (1 << j)} \\
+		Anzahl an führenden nullen	($x \neq 0$) & \code{__builtin_clzll(x)} \\
+		Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\
+		Anzahl an \code{1} bits & \code{__builtin_popcountll(x)} \\
+		$i$-te Zahl eines Graycodes & \code{i ^ (i >> 1)} \\
+		\hline
+	\end{tabularx}\\
+	\end{expandtable}
+	\sourcecode{other/bitOps.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Pragmas}
+	\sourcecode{other/pragmas.cpp}
+\end{algorithm}
+
+\begin{algorithm}{DP Optimizations}
+	Aufgabe: Partitioniere Array in genau $m$ zusammenhängende Teile mit minimalen Kosten:
+	$dp[i][j] = \min_{k<j}\{dp[i-1][k-1]+C[k][j]\}$. Es sei $A[i][j]$ das \emph{minimale} optimale
+	$k$ bei der Berechnung von $dp[i][j]$.
+	
+	\paragraph{\textsc{Knuth}-Optimization} Vorbedingung: $A[i - 1][j] \leq A[i][j] \leq A[i][j + 1]$
+	
+	\method{calc}{berechnet das DP}{n^2}
+	\sourcecode{other/knuth.cpp}
+	
+	\paragraph{Divide and Conquer}
+	Vorbedingung: $A[i][j - 1] \leq A[i][j]$.
+	
+	\method{calc}{berechnet das DP}{m\*n\*\log(n)}
+	\sourcecode{other/divideAndConquer.cpp}
+	
+	\paragraph{Quadrangle inequality} Die Bedingung  $\forall a\leq b\leq c\leq d:
+	C[a][d] + C[b][c] \geq C[a][c] + C[b][d]$ ist hinreichend für beide Optimierungen.
+	
+	\paragraph{Sum over Subsets DP} Siehe \emph{or} Transform, Seite \pageref{fft}.
+\end{algorithm}
+
+\begin{algorithm}{Fast Subset Sum}
+	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
+	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+	\sourcecode{other/fastSubsetSum.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Parallel Binary Search}
+	\sourcecode{other/pbs.cpp}
+\end{algorithm}
+
+\columnbreak
+\begin{algorithm}{Josephus-Problem}
+	$n$ Personen im Kreis, jeder $k$-te wird erschossen.
+	\begin{description}
+		\item[Spezialfall $\boldsymbol{k=2}$:] Betrachte $n$ Binär.
+		Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n0$ die Position des letzten Überlebenden.
+	\end{description}
+	\sourcecode{other/josephus2.cpp}
+	
+	\begin{description}
+		\item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden.
+		Nummeriere die Personen mit $0, 1, \ldots, n-1$.
+		Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$.
+		Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$.
+	\end{description}
+	\sourcecode{other/josephusK.cpp}
+\end{algorithm}
+
+\begin{algorithm}[optional]{Zeileneingabe}
+	\sourcecode{other/split.cpp}
+\end{algorithm}
+
+\begin{algorithm}[optional]{Fast IO}
+	\sourcecode{other/fastIO.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Sonstiges}
+	\sourcecode{other/stuff.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Stress Test}
+	\sourcecode{other/stress.sh}
+\end{algorithm}
+
+\clearpage
+\subsection{Gemischtes}
+\begin{itemize}
+	\item \textbf{(Minimum) Flow mit Demand \textit{d}:}
+	Erstelle neue Quelle $s'$ und Senke $t'$ und setzte die folgenden Kapazitäten:
+	\begin{align*}
+		c'(s',v)&=\sum_{u\in{}V}d(u,v)&c'(v,t')&=\sum_{u\in{}V}d(v,u)\\[-0.5ex]
+		c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x
+	\end{align*}
+	Löse Fluss auf $G'$ mit \textsc{Dinitz's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst).
+	\item \textbf{\textsc{Johnson}s Reweighting Algorithm:}
+	Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen.
+	Falls es einen negativen Zyklus gibt abrrechen.
+	Sonst ändere die Gewichte von allen Kanten \texttt{(u,v)} im ursprünglichen Graphen zu \texttt{d[u]+w[u,v]-d[v]}.
+	Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden.
+
+	\item \textbf{System von Differenzbeschränkungen:}
+	Ändere alle Bedingungen in die Form $a-b \leq c$.
+	Für jede Bedingung füge eine Kante \texttt{(b,a)} mit Gewicht \texttt{c} ein.
+	Füge Quelle \texttt{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0.
+	Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \texttt{s} aus zu finden.
+	\texttt{d[v]} ist mögliche Lösung für \texttt{v}.
+
+	\item \textbf{Min-Weight-Vertex-Cover im Bipartiten Graph:}
+	Partitioniere in \texttt{A, B} und füge Kanten \texttt{s}\,$\rightarrow$\,\texttt{A} mit Gewicht \texttt{w(A)} und Kanten  \texttt{B}\,$\rightarrow$\,\texttt{t} mit Gewicht \texttt{w(B)} hinzu.
+	Füge Kanten mit Kapazität $\infty$ von \texttt{A} nach \texttt{B} hinzu, wo im originalen Graphen Kanten waren.
+	Max-Flow ist die Lösung.\newline
+	Im Residualgraphen:
+	\begin{itemize}
+		\item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder}
+		\item Die Knoten in \texttt{A}, die \emph{nicht} von \texttt{s} erreichbar sind und die Knoten in \texttt{B}, die von \texttt{s} erreichbar sind.
+	\end{itemize}
+
+	\item \textbf{Allgemeiner Graph:}
+	Das Komplement eines Vertex-Cover ist ein Independent Set.
+	$\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover.
+
+	\item \textbf{Bipartiter Graph (Satz von \textsc{König}):}
+	Min Vertex Cover (kleinste Menge Knoten, die alle Kanten berühren) = Max Matching.
+	Richte Kanten im Matching von $B$ nach $A$ und sonst von $A$ nach $B$, markiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die markierten Knoten aus $B$ und die unmarkierten Knoten aus $A$.
+
+	\item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:}
+	Minimiere Matchinggewicht.
+	Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normalen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn})
+
+	\item \textbf{Satz von \textsc{Pick}:}
+	Sei $A$ der Flächeninhalt eines einfachen Gitterpolygons, $I$ die Anzahl der Gitterpunkte im Inneren und $R$ die Anzahl der Gitterpunkte auf dem Rand.
+	Es gilt:\vspace*{-\baselineskip}
+	\[
+		A = I + \frac{R}{2} - 1
+	\]
+
+	\item \textbf{Lemma von \textsc{Burnside}:}
+	Sei $G$ eine endliche Gruppe, die auf der Menge $X$ operiert.
+	Für jedes $g \in G$ sei $X^g$ die Menge der Fixpunkte bei Operation durch $g$, also $X^g = \{x \in X \mid g \bullet x = x\}$.
+	Dann gilt für die Anzahl der Bahnen $[X/G]$ der Operation:
+	\[
+		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} \vert X^g \vert
+	\]
+
+	\item \textbf{\textsc{Polya} Counting:}
+	Sei $\pi$ eine Permutation der Menge $X$.
+	Die Elemente von $X$ können mit einer von $m$ Farben gefärbt werden.
+	Die Anzahl der Färbungen, die Fixpunkte von $\pi$ sind, ist $m^{\#(\pi)}$, wobei $\#(\pi)$ die Anzahl der Zyklen von $\pi$ ist.
+	Die Anzahl der Färbungen von Objekten einer Menge $X$ mit $m$ Farben unter einer Symmetriegruppe $G$ is gegeben durch:
+	\[
+		[X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} m^{\#(g)}
+	\]
+
+	\item \textbf{\textsc{Bertrand}sches Postulat:}
+	Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$.
+
+	\item \textbf{Satz von \textsc{Kirchhoff} (Anzahl Spannbäume):}
+	Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten.
+	Sei $A$ die Adjazenzmatrix von~$G$.
+	Dabei ist $a_{ij}$ die Anzahl der Kanten zwischen Knoten $i$ und $j$.
+	Sei $B$ eine Diagonalmatrix mit $b_{ii}$ Grad von Knoten $i$.
+	Definiere $R = B - A$.
+	Entferne $k$-te Zeile und $k$-te Spalte ($k$ beliebig) und berechne Betrag der Determinante.
+	Das Ergebnis ist die Anzahl der Spannbäume von $G$.
+	\newline
+	Funktioniert auch für gerichtete Graphen: $b_{ii}$ ist der Outdegree und man
+	berechnet die Determinante nach Entfernen der $k$-ten Zeile und Spalte.
+	Das Ergebnis ist die Anzahl an gerichteten Spannbäumen mit Wurzel $k$,
+	sodass jeder Knoten einen Pfad zu $k$ hat.
+
+	\item \textbf{\textsc{Dilworth}'s Theorem:}
+	Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset).
+	Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$.
+	Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist.
+	Eine \emph{Antikette} ist eine Menge von Elementen, die paarweise nicht vergleichbar sind.
+	\newline
+	Es gilt: Die Größe der längsten Antikette gleicht der Größe der kleinsten Partition.
+	$\Rightarrow$ \emph{Weite} des Poset.
+	\newline
+	Berechnung der minimalen Partition: Maximales Matching in bipartitem Graphen.
+	Dupliziere jedes $s \in S$ in $u_s$ und $v_s$.
+	Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu.
+	Wenn $u_x$ mit $v_y$ gematched wird, sind $x$ und $y$ in derselben Kette.
+	\newline
+	Berechnung der maximalen Antikette: Verwende Satz von König, um ein
+	minimales Vertexcover des bipartiten Graphen zu finden.
+	Ersetze $u_x, v_x$ durch $x$ und erhalte so minimales Vertexcover vom Poset.
+	Das Komplement davon ist eine maximale Antikette.
+	
+	\item \textbf{\textsc{Tur\'an}'s Theorem:}
+	Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist:
+	\begin{align*}
+	ext(n, K_{x+1}) &= \binom{n}{2} - \left[\left(x - (n \bmod x)\right) \cdot \binom{\floor{\frac{n}{x}}}{2} + \left(n\bmod x\right)  \cdot \binom{\ceil{\frac{n}{x}}}{2}\right]
+	\end{align*}
+	
+	\item \textbf{\textsc{Euler}scher Polyedersatz:}
+	In planaren Graphen gilt $n-m+f-c=1$.
+	
+	\item \textbf{\textsc{Pythagoreische Tripel}:}
+	Sei $m>n>0,~k>0$ und $m\not\equiv n \bmod 2$ dann beschreibt diese Formel alle Pythagoreischen Tripel eindeutig:
+	\[k~\cdot~\Big(~a=m^2-n^2,\quad b=2mn,\quad c=m^2+n^2~\Big)\]
+	
+	\item \textbf{Centroids of a Tree:}
+	Ein \emph{Centroid} ist ein Knoten, der einen Baum in Komponenten der maximalen Größe $\frac{\abs{V}}{2}$ splitted.
+	Es kann $2$ Centroids geben!
+	
+	\item \textbf{Centroid Decomposition:}
+	Wähle zufälligen Knoten und mache DFS.
+	Verschiebe ausgewählten Knoten in Richtung des tiefsten Teilbaums, bis Centroid gefunden. Entferne Knoten, mache rekursiv in Teilbäumen weiter. Laufzeit:~\runtime{\abs{V} \cdot \log(\abs{V})}.
+	\item \textbf{Gregorian Calendar:} Der Anfangstag des Jahres ist alle $400$ Jahre gleich.
+
+	\item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:}
+	Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von
+	$\runtime{n^2}$ zu $\runtime{n\log n}$ zu verbessern.
+	
+	\item \textbf{\textsc{Mo}'s Algorithm:}
+	SQRT-Decomposition auf $n$ Intervall Queries $[l,r]$.
+	Gruppiere Queries in $\sqrt{n}$ Blöcke nach linker Grenze $l$.
+	Sortiere nach Block und bei gleichem Block nach rechter Grenze $r$.
+	Beantworte Queries offline durch schrittweise Vergrößern/Verkleinern des aktuellen Intervalls.
+	Laufzeit:~\runtime{n\cdot\sqrt{n}}.
+	(Anzahl der Blöcke als Konstante in Code schreiben.)
+	
+	\item \textbf{SQRT Techniques:}
+	\begin{itemize}
+		\item Aufteilen in \emph{leichte} (wert $\leq\sqrt{x}$) und \emph{schwere} (höchsten $\sqrt{x}$ viele) Objekte.
+		\item Datenstruktur in Blöcke fester Größe (z.b. 256 oder 512) aufteilen.
+		\item Datenstruktur nach fester Anzahl Updates komplett neu bauen.
+		\item Wenn die Summe über $x_i$ durch $X$ beschränkt ist, dann gibt es nur $\sqrt{2X}$ verschiedene Werte von $x_i$ (z.b. Längen von Strings).
+		\item Wenn $w\cdot h$ durch $X$ beschränkt ist, dann ist $\min(w,h)\leq\sqrt{X}$.
+	\end{itemize}
+
+	\item \textbf{Partition:}
+	Gegeben Gewichte $w_0+w_1+\cdots+w_k=W$, existiert eine Teilmenge mit Gewicht $x$?
+	Drei gleiche Gewichte $w$ können zu $w$ und $2w$ kombiniert werden ohne die Lösung zu ändern $\Rightarrow$ nur $2\sqrt{W}$ unterschiedliche Gewichte.
+	Mit bitsets daher selbst für $10^5$ lösbar.
+\end{itemize}
+
+\subsection{Tipps \& Tricks}
+
+\begin{itemize}
+	\item \textbf{Run Time Error:}
+	\begin{itemize}
+		\item Stack Overflow? Evtl. rekursive Tiefensuche auf langem Pfad?
+		\item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen?
+		\item Abbruchbedingung bei Rekursion?
+		\item Evtl. Memory Limit Exceeded? Mit \code{/usr/bin/time -v} erhält man den maximalen Speicherverbrauch bei der Ausführung (Maximum resident set size).
+	\end{itemize}
+	
+	\item \textbf{Strings:}
+	\begin{itemize}
+		\item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?
+		\item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.
+	\end{itemize}
+
+	\item \textbf{Zeilenbasierte Eingabe}:
+	\begin{itemize}
+		\item \code{getline(cin, str)} liest Zeile ein.
+		\item Wenn vorher \code{cin >> ...} benutzt, lese letztes \code{\\n} mit \code{getline(cin, x)}.
+	\end{itemize}
+	
+	\item \textbf{Gleitkommazahlen:}
+	\begin{itemize}
+		\item \code{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\code{acos(1.00000000000001)}}?
+		\item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!
+		\item genügend Präzision oder Output in wissenschaftlicher Notation (\code{1e-25})?
+		\item Kann \code{-0.000} ausgegeben werden?
+	\end{itemize}
+
+	\item \textbf{Wrong Answer:}
+	\begin{itemize}
+		\item Lies Aufgabe erneut. Sorgfältig!
+		\item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander.
+		\item Integer Overflow? Teste maximale Eingabegrößen und mache Überschlagsrechnung.
+		\item Ausgabeformat im 'unmöglich'-Fall überprüfen.
+		\item Ist das Ergebnis modulo einem Wert?
+		\item Integer Division rundet zur $0$ $\neq$ abrunden.
+		\item Eingabegrößen überprüfen. Sonderfälle ausprobieren.
+		\begin{itemize}
+			\item $n = 0$, $n = -1$, $n = 1$, $n = 2^{31}-1$, $n = -2^{31}$
+			\item $n$ gerade/ungerade
+			\item Graph ist leer/enthält nur einen Knoten.
+			\item Liste ist leer/enthält nur ein Element.
+			\item Graph ist Multigraph (enthält Schleifen/Mehrfachkanten).
+			\item Sind Kanten gerichtet/ungerichtet?
+			\item Kolineare Punkte existieren.
+			\item Polygon ist konkav/selbstschneidend.
+		\end{itemize}
+		\item Bei DP/Rekursion: Stimmt Basisfall?
+		\item Unsicher bei benutzten STL-Funktionen?
+	\end{itemize}
+\end{itemize}
+
+%\input{other/simd}