From 9906aa7bbf98bee5cdb91e80f6a2311e43129c7d Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Wed, 20 Mar 2024 21:33:18 +0100
Subject: improve aho corasick

---
 string/string.tex | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

(limited to 'string/string.tex')

diff --git a/string/string.tex b/string/string.tex
index c36ec69..526faa2 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -49,16 +49,18 @@
 
 \begin{algorithm}{\textsc{Aho-Corasick}-Automat}
 	\begin{methods}[ll]
-		sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}+\abs{matches}}
+		sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}}
 	\end{methods}
 	\begin{enumerate}
-		\item mit \code{addString(pattern, idx);} Patterns hinzufügen.
+		\item mit \code{addString(pattern, idx)} Patterns hinzufügen.
+        \item rufe \code{buildGraph()} auf
 		\item mit \code{state = go(state, idx)} in nächsten Zustand wechseln.
-		\item mit \code{state = getExit(state)} den exit Kanten folgen bis \code{state == 0}
-		\item dabei mit \code{aho[state].patterns} die Matches zählen
+        \item erhöhe dabei \code{dp[state]++}
+        \item rufe \code{dfs()} auf. In dp[pattern state] stehen die Anzahl der Matches
 	\end{enumerate}
 	\sourcecode{string/ahoCorasick.cpp}
 \end{algorithm}
+\clearpage
 
 \begin{algorithm}{Lyndon und De-Bruijn}
 	\begin{itemize}
-- 
cgit v1.2.3


From 36ba8589fa0154d73354bd8e0101213f2d5f9ba4 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Fri, 22 Mar 2024 12:21:56 +0100
Subject: reorder to improve spacing

---
 datastructures/datastructures.tex |  62 ++++++-------
 geometry/geometry.tex             |  17 ++--
 graph/graph.tex                   | 133 +++++++++++++++------------
 math/math.tex                     | 189 +++++++++++++++++++-------------------
 string/string.tex                 |   1 +
 tcr.pdf                           | Bin 667178 -> 664992 bytes
 tcr.tex                           |   3 +-
 7 files changed, 208 insertions(+), 197 deletions(-)

(limited to 'string/string.tex')

diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 4139219..1ccefaa 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -14,6 +14,15 @@
 	\sourcecode{datastructures/lazyPropagation.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Wavelet Tree}
+	\begin{methods}
+		\method{Constructor}{baut den Baum auf}{n\*\log(n)}
+		\method{kth}{sort $[l, r)[k]$}{\log(n)}
+		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)}
+	\end{methods}
+	\sourcecode{datastructures/waveletTree.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Fenwick Tree}
 	\begin{methods}
 		\method{init}{baut den Baum auf}{n\*\log(n)}
@@ -29,11 +38,11 @@
 	\end{methods}
 	\sourcecode{datastructures/fenwickTree2.cpp}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{STL-Rope (Implicit Cartesian Tree)}
 	\sourcecode{datastructures/stlRope.cpp}
 \end{algorithm}
+\columnbreak
 
 \begin{algorithm}{(Implicit) Treap (Cartesian Tree)}
 	\begin{methods}
@@ -54,15 +63,6 @@
 	\sourcecode{datastructures/sparseTable.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Wavelet Tree}
-	\begin{methods}
-		\method{Constructor}{baut den Baum auf}{n\*\log(n)}
-		\method{kth}{sort $[l, r)[k]$}{\log(n)}
-		\method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)}
-	\end{methods}
-	\sourcecode{datastructures/waveletTree.cpp}
-\end{algorithm}
-
 \begin{algorithm}{STL-Bitset}
 	\sourcecode{datastructures/bitset.cpp}
 \end{algorithm}
@@ -81,6 +81,23 @@
 \end{algorithm}
 \clearpage
 
+\begin{algorithm}{Lichao}
+    \sourcecode{datastructures/lichao.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Policy Based Data Structures}
+    \textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}!
+	\sourcecode{datastructures/stlPriorityQueue.cpp}
+	\columnbreak
+	\sourcecode{datastructures/pbds.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)}
+	Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
+	\sourcecode{datastructures/monotonicConvexHull.cpp}
+	\sourcecode{datastructures/dynamicConvexHull.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Union-Find}
 	\begin{methods}
 		\method{init}{legt $n$ einzelne Unions an}{n}
@@ -90,13 +107,7 @@
 	\end{methods}
 	\sourcecode{datastructures/unionFind.cpp}
 \end{algorithm}
-
-\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)}
-	Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren.
-	\sourcecode{datastructures/monotonicConvexHull.cpp}
-	\columnbreak
-	\sourcecode{datastructures/dynamicConvexHull.cpp}
-\end{algorithm}
+\columnbreak
 
 \begin{algorithm}{Persistent}
 	\begin{methods}
@@ -108,22 +119,6 @@
 	\sourcecode{datastructures/persistentArray.cpp}
 \end{algorithm}
 
-\begin{algorithm}{STL-Tree}
-	\sourcecode{datastructures/stlTree.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL Priority Queue}
-	Nicht notwendig, wenn Smaller-Larger-Optimization greift.
-	\sourcecode{datastructures/stlPQ.cpp}
-\end{algorithm}
-
-\begin{algorithm}{STL HashMap}
-	3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map}
-	\sourcecode{datastructures/stlHashMap.cpp}
-\end{algorithm}
-
-
-
 \begin{algorithm}[optional]{Range Minimum Query}
 	\begin{methods}
 		\method{init}{baut Struktur auf}{n\*\log(n)}
@@ -138,4 +133,3 @@
 	\end{methods}
 	\sourcecode{datastructures/firstUnused.cpp}
 \end{algorithm}
-
diff --git a/geometry/geometry.tex b/geometry/geometry.tex
index d3e1671..d753ed6 100644
--- a/geometry/geometry.tex
+++ b/geometry/geometry.tex
@@ -7,6 +7,14 @@
 	\sourcecode{geometry/closestPair.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Rotating calipers}
+	\begin{methods}
+		\method{antipodalPoints}{berechnet antipodale Punkte}{n}
+	\end{methods}
+	\textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn sortiert sein und konvexes Polygon bilden!
+	\sourcecode{geometry/antipodalPoints.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Konvexehülle}
 	\begin{methods}
 		\method{convexHull}{berechnet Konvexehülle}{n\*\log(n)}
@@ -19,15 +27,6 @@
 	\sourcecode{geometry/convexHull.cpp}
 \end{algorithm}
 
-\columnbreak
-\begin{algorithm}{Rotating calipers}
-	\begin{methods}
-		\method{antipodalPoints}{berechnet antipodale Punkte}{n}
-	\end{methods}
-	\textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn sortiert sein und konvexes Polygon bilden!
-	\sourcecode{geometry/antipodalPoints.cpp}
-\end{algorithm}
-
 \subsection{Formeln~~--~\texttt{std::complex}}
 \sourcecode{geometry/formulars.cpp}
 \sourcecode{geometry/linesAndSegments.cpp}
diff --git a/graph/graph.tex b/graph/graph.tex
index 6fbdb74..060d157 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,18 +1,31 @@
 \section{Graphen}
 
-\begin{algorithm}{Eulertouren}
+\begin{algorithm}{Kruskal}
+	\begin{methods}[ll]
+		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+	\end{methods}
+	\sourcecode{graph/kruskal.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Minimale Spannbäume}
+	\paragraph{Schnitteigenschaft}
+	Für jeden Schnitt $C$ im Graphen gilt:
+	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
+	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
+	
+	\paragraph{Kreiseigenschaft}
+	Für jeden Kreis $K$ im Graphen gilt:
+	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
+\end{algorithm}
+
+\begin{algorithm}{Heavy-Light Decomposition}
 	\begin{methods}
-		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
+		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
 	\end{methods}
-	\sourcecode{graph/euler.cpp}
-	\begin{itemize}
-		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
-		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
-		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
-		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adj} leichter
-		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-		Die Existenz muss separat geprüft werden.
-	\end{itemize}
+	\textbf{Wichtig:} Intervalle sind halboffen
+	
+	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
+	\sourcecode{graph/hld.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Lowest Common Ancestor}
@@ -31,16 +44,20 @@
 	\sourcecode{graph/centroid.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Heavy-Light Decomposition}
+\begin{algorithm}{Eulertouren}
 	\begin{methods}
-		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
 	\end{methods}
-	\textbf{Wichtig:} Intervalle sind halboffen
-	
-	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
-	\sourcecode{graph/hld.cpp}
+	\sourcecode{graph/euler.cpp}
+	\begin{itemize}
+		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
+		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adj} leichter
+		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+		Die Existenz muss separat geprüft werden.
+	\end{itemize}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{Baum-Isomorphie}
 	\begin{methods}
@@ -49,24 +66,6 @@
 	\sourcecode{graph/treeIsomorphism.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Minimale Spannbäume}
-	\paragraph{Schnitteigenschaft}
-	Für jeden Schnitt $C$ im Graphen gilt:
-	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
-	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
-	
-	\paragraph{Kreiseigenschaft}
-	Für jeden Kreis $K$ im Graphen gilt:
-	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
-\end{algorithm}
-
-\begin{algorithm}{Kruskal}
-	\begin{methods}[ll]
-		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
-	\end{methods}
-	\sourcecode{graph/kruskal.cpp}
-\end{algorithm}
-
 \subsection{Kürzeste Wege}
 
 \subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
@@ -91,6 +90,14 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die
 
 Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$
 
+\begin{algorithm}{Dynamic Connectivity}
+	\begin{methods}
+		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
+		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
+	\end{methods}
+	\sourcecode{graph/connect.cpp}
+\end{algorithm}
 
 \begin{algorithm}{Erd\H{o}s-Gallai}
 	Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$
@@ -100,13 +107,11 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/havelHakimi.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Dynamic Connectivity}
+\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})}
 	\begin{methods}
-		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
-		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
-		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
+		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
 	\end{methods}
-	\sourcecode{graph/connect.cpp}
+	\sourcecode{graph/scc.cpp}
 \end{algorithm}
 
 \begin{algorithm}{DFS}
@@ -121,13 +126,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/articulationPoints.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})}
-	\begin{methods}
-		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
-	\end{methods}
-	\sourcecode{graph/scc.cpp}
-\end{algorithm}
-
 \begin{algorithm}{2-SAT}
 	\sourcecode{graph/2sat.cpp}
 \end{algorithm}
@@ -139,7 +137,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/bronKerbosch.cpp}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{Cycle Counting}
 	\begin{methods}
@@ -164,6 +161,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/blossom.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Rerooting Template}
+    \sourcecode{graph/reroot.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Virtual Trees}
+    \sourcecode{graph/virtualTree.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
 	\label{kuhn}
 	\begin{methods}
@@ -179,13 +184,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/hopcroftKarp.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Maximum Weight Bipartite Matching}
-	\begin{methods}
-		\method{match}{berechnet Matching}{\abs{V}^3}
-	\end{methods}
-	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Global Mincut}
 	\begin{methods}
 		\method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}\abs{E}+\abs{V}^2\*\log(\abs{E})}
@@ -205,12 +203,21 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \sourcecode{graph/capacityScaling.cpp}
 }
 
+\optional{
 \subsubsection{Push Relabel}
 \begin{methods}
 	\method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}}
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
-\sourcecode{graph/pushRelabel2.cpp}
+\sourcecode{graph/pushRelabel.cpp}
+}
+
+\begin{algorithm}{Min-Cost-Max-Flow}
+	\begin{methods}
+		\method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2}
+	\end{methods}
+	\sourcecode{graph/minCostMaxFlow.cpp}
+\end{algorithm}
 
 \subsubsection{Dinic's Algorithm mit Capacity Scaling}
 \begin{methods}
@@ -218,6 +225,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
 \sourcecode{graph/dinicScaling.cpp}
+\vfill*
+\columnbreak
 
 \optional{
 \subsubsection{Anwendungen}
@@ -241,12 +250,15 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \end{itemize}
 }
 
-\begin{algorithm}{Min-Cost-Max-Flow}
+\begin{algorithm}{Maximum Weight Bipartite Matching}
 	\begin{methods}
-		\method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2}
+		\method{match}{berechnet Matching}{\abs{V}^3}
 	\end{methods}
-	\sourcecode{graph/minCostMaxFlow.cpp}
+	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
 \end{algorithm}
+\vfill*
+\columnbreak
+
 
 \begin{algorithm}[optional]{TSP}
 	\begin{methods}
@@ -261,3 +273,4 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/bitonicTSPsimple.cpp}
 \end{algorithm}
+
diff --git a/math/math.tex b/math/math.tex
index 8ccc55e..8a30b86 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,5 +1,12 @@
 \section{Mathe}
 
+\begin{algorithm}{Zykel Erkennung}
+	\begin{methods}
+		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
+	\end{methods}
+	\sourcecode{math/cycleDetection.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Longest Increasing Subsequence}
 	\begin{itemize}
 		\item \code{lower\_bound} $\Rightarrow$ streng monoton
@@ -7,14 +14,6 @@
 	\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}
@@ -44,21 +43,20 @@
 
 \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
 	\runtime{\log(a) + \log(b)}
-	\sourcecode{math/gcd-lcm.cpp}
 	\sourcecode{math/extendedEuclid.cpp}
 \end{algorithm}
 
-\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$
+\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(n, p) = 1}$:}
+\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:}
 \begin{itemize}
 	\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$
+	$\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(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
+\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$.
 % \sourcecode{math/multInv.cpp}
 \sourcecode{math/shortModInv.cpp}
 
@@ -121,19 +119,12 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/divisors.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}
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+	\sourcecode{math/goldenSectionSearch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+	\sourcecode{math/simpson.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Diskreter Logarithmus}
@@ -151,6 +142,22 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/discreteNthRoot.cpp}
 \end{algorithm}
 
+
+\begin{algorithm}{Primitivwurzeln}
+	\begin{itemize}
+		\item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
+		\item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
+		\item Sei $g$ Primitivwurzel modulo $n$.
+		Dann gilt:\newline
+		Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
+	\end{itemize}
+	\begin{methods}
+		\method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
+		\method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
+	\end{methods}
+	\sourcecode{math/primitiveRoot.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Linearessieb und Multiplikative Funktionen}
 	Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.
 	
@@ -185,7 +192,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\end{itemize}
 \end{algorithm}
 
-
 \begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
 	\begin{itemize}
 		\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
@@ -216,33 +222,25 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	%\sourcecode{math/mobius.cpp}
 \end{algorithm}
 
-%\columnbreak
-%\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
-%\begin{itemize}
-%	\item Zählt die relativ primen Zahlen $\leq n$.
-%	
-%	\item Multiplikativ:
-%	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
-%	
-%	\item $p$ prim, $k \in \mathbb{N}$:
-%	$~\varphi(p^k) = p^k - p^{k - 1}$
-%	
-%	\item \textbf{\textsc{Euler}'s Theorem:}
-%	Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
-%	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
-%	$a^{m} \equiv a \pmod{m}$
-%\end{itemize}
-%\sourcecode{math/phi.cpp}
-
-
-\begin{algorithm}{Numerisch Extremstelle bestimmen}
-	\sourcecode{math/goldenSectionSearch.cpp}
-\end{algorithm}
-
-
-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
-	\sourcecode{math/simpson.cpp}
-\end{algorithm}
+\optional{
+\columnbreak
+\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
+\begin{itemize}
+	\item Zählt die relativ primen Zahlen $\leq n$.
+	
+	\item Multiplikativ:
+	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
+	
+	\item $p$ prim, $k \in \mathbb{N}$:
+	$~\varphi(p^k) = p^k - p^{k - 1}$
+	
+	\item \textbf{\textsc{Euler}'s Theorem:}
+	Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
+	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
+	$a^{m} \equiv a \pmod{m}$
+\end{itemize}
+\sourcecode{math/phi.cpp}
+}
 
 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
 	Multipliziert Polynome $A$ und $B$.
@@ -259,21 +257,53 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	%\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code
 	\sourcecode{math/transforms/fft.cpp}
 	\sourcecode{math/transforms/ntt.cpp}
+    \vfill*
+    \columnbreak
 	\sourcecode{math/transforms/bitwiseTransforms.cpp}
 	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)
 	\sourcecode{math/transforms/fftMul.cpp}
 \end{algorithm}
 
-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/gauss.cpp}
+\begin{algorithm}{Operations on Formal Power Series}
+    \sourcecode{math/transforms/seriesOperations.cpp}
+\end{algorithm}
 
 \subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
 \method{gauss}{löst LGS}{n^3}
 \sourcecode{math/lgsFp.cpp}
 
-\clearpage
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/gauss.cpp}
+
+\begin{algorithm}{\textsc{Legendre}-Symbol}
+	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
+	\begin{align*}
+		\legendre{a}{p} &=
+		\begin{cases*}
+		\hphantom{-}0 & falls $p~\vert~a$ \\[-1ex]
+		\hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex]
+		-1 & sonst
+		\end{cases*} \\
+		\legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &=
+		\begin{cases*}
+		\hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex]
+		-1 & falls $p \equiv 3 \bmod 4$
+		\end{cases*} \\
+		\legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &=
+		\begin{cases*}
+		\hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex]
+		-1 & falls $p \equiv \pm 3 \bmod 8$
+		\end{cases*}
+	\end{align*}
+	\begin{align*}
+		\legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} &&
+		\legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p
+	\end{align*}
+	\sourcecode{math/legendre.cpp}
+\end{algorithm}
 
+\optional{
 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
 \begin{methods}
 	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
@@ -281,6 +311,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}
 \end{methods}
 \sourcecode{math/piLehmer.cpp}
+}
 
 \begin{algorithm}{Lineare-Recurenz}
 	\begin{methods}
@@ -331,33 +362,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/matrixPower.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}
-
 \begin{algorithm}{Inversionszahl}
 	\sourcecode{math/inversions.cpp}
 \end{algorithm}
@@ -411,14 +415,13 @@ so gilt
 	\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$
-\columnbreak
-	
-	\begin{methods}
+
+    \begin{methods}
 		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
 	\end{methods}
 	\sourcecode{math/binomial1.cpp}
-	
-	\begin{methods}
+
+    \begin{methods}
 		\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
 	\end{methods}
 	\sourcecode{math/binomial3.cpp}
diff --git a/string/string.tex b/string/string.tex
index 526faa2..393c2ad 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -47,6 +47,7 @@
 	\sourcecode{string/longestCommonSubsequence.cpp}
 \end{algorithm}
 
+\columnbreak
 \begin{algorithm}{\textsc{Aho-Corasick}-Automat}
 	\begin{methods}[ll]
 		sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}}
diff --git a/tcr.pdf b/tcr.pdf
index e7330c0..6342868 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/tcr.tex b/tcr.tex
index 445f8b6..bfc73d1 100644
--- a/tcr.tex
+++ b/tcr.tex
@@ -3,7 +3,7 @@
 \documentclass[a4paper,fontsize=7.8pt]{scrartcl}
 
 % General information.
-\newcommand{\teamname}{Let's party!}
+\newcommand{\teamname}{Kindergarten Timelimit}
 \newcommand{\university}{Karlsruhe Institute of Technology}
 
 % Options
@@ -36,6 +36,7 @@
 	\tableofcontents
 \end{multicols*}
 }
+
 \newpage
 
 % Content.
-- 
cgit v1.2.3

