summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--math/math.tex1055
-rw-r--r--math/shortModInv.cpp3
-rw-r--r--other/other.tex612
3 files changed, 837 insertions, 833 deletions
diff --git a/math/math.tex b/math/math.tex
index 1c3f856..b986770 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,527 +1,528 @@
-\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}
-
-\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}
-\clearpage
-
-\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
-%\vspace{-1.25em}
-%\begin{multicols}{2}
-\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
-\sourcecode{math/modMulIterativ.cpp}
-% \vfill\null\columnbreak
-\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
-\sourcecode{math/modPowIterativ.cpp}
-%\end{multicols}
-%\vspace{-2.75em}
-\begin{itemize}
- \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
-\end{itemize}
-
-\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
- \runtime{\log(a) + \log(b)}
- \sourcecode{math/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$
-
-\textbf{Falls $\boldsymbol{\ggT(n, p) = 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$
-\end{itemize}
-\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
-\sourcecode{math/multInv.cpp}
-
-\paragraph{Lemma von \textsc{Bézout}}
-Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
-Dann lassen sich wie folgt alle Lösungen berechnen:
-\[
-\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
-\]
-
-\paragraph{\textsc{Pell}-Gleichungen}
-Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
-Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
-sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
-\begin{align*}
- x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
- x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
-\end{align*}
-
-\begin{algorithm}{Lineare Kongruenz}
- \begin{itemize}
- \item Löst $ax\equiv b\pmod{m}$.
- \item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
- also $g$ Lösungen modulo $m$.
- \end{itemize}
- \sourcecode{math/linearCongruence.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Chinesischer Restsatz}
- \begin{itemize}
- \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
- \item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:
- \[
- x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
- \qquad \text{mit} \qquad
- d := \ggT(n, m) = yn + zm
- \]
- Formel kann auch für nicht teilerfremde Moduli verwendet werden.
- Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
- wenn $a\equiv~b \bmod \ggT(m, n)$.
- In diesem Fall sind keine Faktoren
- auf der linken Seite erlaubt.
- \end{itemize}
- \sourcecode{math/chineseRemainder.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Primzahltest \& Faktorisierung}
- \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
- \sourcecode{math/millerRabin.cpp}
- \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
- \sourcecode{math/rho.cpp}
- %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
- %\sourcecode{math/squfof.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Teiler}
- \begin{methods}
- \method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
- \end{methods}
- \sourcecode{math/divisors.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Primitivwurzeln}
- \begin{itemize}
- \item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
- \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
- \item Sei $g$ Primitivwurzel modulo $n$.
- Dann gilt:\newline
- Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
- \end{itemize}
- \begin{methods}
- \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
- \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
- \end{methods}
- \sourcecode{math/primitiveRoot.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Diskreter Logarithmus}
- \begin{methods}
- \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
- \end{methods}
- \sourcecode{math/discreteLogarithm.cpp}
-\end{algorithm}
-%TODO
-\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel}
- \begin{methods}
- \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
- \end{methods}
- Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
- \sourcecode{math/discreteNthRoot.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Linearessieb und Multiplikative Funktionen}
- Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.
-
- $\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen.
-
- \begin{methods}
- \method{sieve}{berechnet Primzahlen und co.}{N}
- \method{sieved}{Wert der endsprechenden Multiplikativen Funktion}{1}
-
- \method{naive}{Wert der endsprechenden Multiplikativen Funktion}{\sqrt{n}}
- \end{methods}
- \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!
-
- \sourcecode{math/linearSieve.cpp}
- \textbf{\textsc{Möbius} Funtkion:}
- \begin{itemize}
- \item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat
- \item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat
- \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist
- \end{itemize}
-
- \textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:}
- \begin{itemize}
- \item Zählt die relativ primen Zahlen $\leq n$.
- \item $p$ prim, $k \in \mathbb{N}$:
- $~\varphi(p^k) = p^k - p^{k - 1}$
-
- \item \textbf{Euler's Theorem:}
- Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
- Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
- $a^{m} \equiv a \pmod{m}$
- \end{itemize}
-\end{algorithm}
-
-
-\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
- \begin{itemize}
- \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
- \end{itemize}
- \begin{methods}
- \method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))}
- \method{isPrime}{prüft ob Zahl prim ist}{1}
- \end{methods}
- \sourcecode{math/primeSieve.cpp}
-\end{algorithm}
-
-\begin{algorithm}{\textsc{Möbius}-Inversion}
- \begin{itemize}
- \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$.
- Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
- \item $\sum\limits_{d \vert n}\mu(d) =
- \begin{cases*}
- 1 & falls $n = 1$\\
- 0 & sonst
- \end{cases*}$
- \end{itemize}
- \textbf{Beispiel Inklusion/Exklusion:}
- Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline
- \textbf{Lösung}:
- Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$.
- Es gibt $2^{[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten.
- Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
- %\sourcecode{math/mobius.cpp}
-\end{algorithm}
-
-%\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}
-
-\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
- Multipliziert Polynome $A$ und $B$.
- \begin{itemize}
- \item $\deg(A \cdot B) = \deg(A) + \deg(B)$
- \item Vektoren \code{a} und \code{b} müssen mindestens Größe
- $\deg(A \cdot B) + 1$ haben.
- Größe muss eine Zweierpotenz sein.
- \item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))}
- \item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
- \end{itemize}
- %\lstinputlisting{math/fft.cpp}
- %\lstinputlisting{math/ntt.cpp}
- %\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code
- \sourcecode{math/transforms/all.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}
-
-\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/lgsFp.cpp}
-
-\clearpage
-
-\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
-\begin{methods}
- \method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
- \method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
- \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}}
-\end{methods}
-\sourcecode{math/piLehmer.cpp}
-
-\begin{algorithm}{Lineare-Recurenz}
- \begin{methods}
- \method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
- \method{}{aus den ersten $2n$ Werte}{}
- \end{methods}
- \sourcecode{math/berlekampMassey.cpp}
- Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
-
- \begin{methods}
- \method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
- \end{methods}
- \sourcecode{math/linearRecurence.cpp}
- Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
- $$\renewcommand\arraystretch{1.5}
- \setlength\arraycolsep{3pt}
- \begin{pmatrix}
- c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\
- 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
- 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
- 0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
- 0 & \smash{\cdots} & 0 & 1 & 0 \\
- \end{pmatrix}^k
- \times~~
- \begin{pmatrix}
- f(n-1) \\
- f(n-2) \\
- \smash{\vdots} \\
- \smash{\vdots} \\
- f(0) \\
- \end{pmatrix}
- ~~=~~
- \begin{pmatrix}
- f(n-1+k) \\
- f(n-2+k) \\
- \smash{\vdots} \\
- \smash{\vdots} \\
- f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
- \end{pmatrix}
- $$
-\end{algorithm}
-
-\begin{algorithm}{Matrix-Exponent}
- \begin{methods}
- \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
- \method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
- \end{methods}
- \sourcecode{math/matrixPower.cpp}
-\end{algorithm}
-
-\begin{algorithm}{\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}
-
-\subsection{Satz von \textsc{Sprague-Grundy}}
-Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
-\[
-g\left(X\right) := \min\left\{
-\mathbb{Z}_0^+ \setminus
-\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
-\right\}
-\]
-$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\
-Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
-
-\subsection{Kombinatorik}
-
-\paragraph{Wilsons Theorem}
-A number $n$ is prime if and only if
-$(n-1)!\equiv -1\bmod{n}$.\\
-($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)
-\begin{align*}
- (n-1)!\equiv\begin{cases}
- -1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\
- \hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\
- \hphantom{-}0\bmod{n},&\mathrm{sonst}
- \end{cases}
-\end{align*}
-
-\paragraph{\textsc{Zeckendorfs} Theorem}
-Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer
-verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei
-aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\
-\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch
-hineinpasst.
-
-\paragraph{\textsc{Lucas}-Theorem}
-Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),
-so gilt
-\vspace{-0.75\baselineskip}
-\[
- \binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}.
-\]
-
-%\begin{algorithm}{Binomialkoeffizienten}
-\paragraph{Binomialkoeffizienten}
- Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
- \begin{methods}
- \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
- \method{calc\_binom}{berechnet Binomialkoeffizient}{1}
- \end{methods}
- \sourcecode{math/binomial0.cpp}
- Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$
-\columnbreak
-
- \begin{methods}
- \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
- \end{methods}
- \sourcecode{math/binomial1.cpp}
-
- \begin{methods}
- \method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
- \end{methods}
- \sourcecode{math/binomial3.cpp}
-
-% \begin{methods}
-% \method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n}
-% \end{methods}
-% \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
-% \sourcecode{math/binomial2.cpp}
-%\end{algorithm}
-
-\paragraph{\textsc{Catalan}-Zahlen}
-\begin{itemize}
- \item Die \textsc{Catalan}-Zahl $C_n$ gibt an:
- \begin{itemize}
- \item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.
- \item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.
- \item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.
- \item Anzahl Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren.
- \item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
- einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
- \end{itemize}
-\end{itemize}
-\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
-\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} \cdot C_{n-1}\]
-\begin{itemize}
- \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
- \item Formel $2$ und $3$ erlauben Berechnung in \runtime{n}
-\end{itemize}
-
-\paragraph{\textsc{Catalan}-Convolution}
-\begin{itemize}
- \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $(^k$ beginnen.
-\end{itemize}
-\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =
-\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)\cdot(2n+k)}{n(n+k+1)} \cdot C_{n-1}\]
-
-\paragraph{\textsc{Euler}-Zahlen 1. Ordnung}
-Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
-Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
-Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
-\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad
-\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}=
-\sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\]
-\begin{itemize}
- \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
- \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
-\end{itemize}
-
-\paragraph{\textsc{Euler}-Zahlen 2. Ordnung}
-Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
-\[\eulerII{n}{0} = 1 \qquad\eulerII{n}{n} = 0 \qquad\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}\]
-\begin{itemize}
- \item Formel erlaubt Berechnung ohne Division in \runtime{n^2}
-\end{itemize}
-
-\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}
-Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
-Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
-\[\stirlingI{0}{0} = 1 \qquad
-\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
-\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
-\begin{itemize}
- \item Formel erlaubt berechnung ohne Division in \runtime{n^2}
-\end{itemize}
-\[\sum_{k=0}^{n}\pm\stirlingI{n}{k}x^k=x(x-1)(x-2)\cdots(x-n+1)\]
-\begin{itemize}
- \item Berechne Polynom mit FFT und benutzte betrag der Koeffizienten \runtime{n\log(n)^2} (nur ungefähr gleich große Polynome zusammen multiplizieren beginnend mit $x-k$)
-\end{itemize}
-
-\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung}
-Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
-Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen.
-Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
-\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
-\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
-\frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\]
-\begin{itemize}
- \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
- \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
-\end{itemize}
-
-\paragraph{\textsc{Bell}-Zahlen}
-Anzahl der Partitionen von $\{1, \ldots, n\}$.
-Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
-\[B_1 = 1 \qquad
-B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
-= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
-
-\paragraph{Partitions}
-Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
-Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
-\begin{align*}
- p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
- p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
- p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg)
-\end{align*}
-\begin{itemize}
- \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
- \item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.
-\end{itemize}
-
-\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
-\input{math/tables/twelvefold}
-
-%\input{math/tables/numbers}
-
-\begin{algorithm}[optional]{Big Integers}
- \sourcecode{math/bigint.cpp}
-\end{algorithm}
+\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}
+
+\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}
+\clearpage
+
+\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
+%\vspace{-1.25em}
+%\begin{multicols}{2}
+\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
+\sourcecode{math/modMulIterativ.cpp}
+% \vfill\null\columnbreak
+\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
+\sourcecode{math/modPowIterativ.cpp}
+%\end{multicols}
+%\vspace{-2.75em}
+\begin{itemize}
+ \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
+\end{itemize}
+
+\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
+ \runtime{\log(a) + \log(b)}
+ \sourcecode{math/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$
+
+\textbf{Falls $\boldsymbol{\ggT(n, p) = 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$
+\end{itemize}
+\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
+% \sourcecode{math/multInv.cpp}
+\sourcecode{math/shortModInv.cpp}
+
+\paragraph{Lemma von \textsc{Bézout}}
+Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
+Dann lassen sich wie folgt alle Lösungen berechnen:
+\[
+\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
+\]
+
+\paragraph{\textsc{Pell}-Gleichungen}
+Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
+Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
+sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
+\begin{align*}
+ x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
+ x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
+\end{align*}
+
+\begin{algorithm}{Lineare Kongruenz}
+ \begin{itemize}
+ \item Löst $ax\equiv b\pmod{m}$.
+ \item Weitere Lösungen unterscheiden sich um \raisebox{2pt}{$\frac{m}{g}$}, es gibt
+ also $g$ Lösungen modulo $m$.
+ \end{itemize}
+ \sourcecode{math/linearCongruence.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Chinesischer Restsatz}
+ \begin{itemize}
+ \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
+ \item Direkte Formel für zwei Kongruenzen $x \equiv a \bmod n$, $x \equiv b \bmod m$:
+ \[
+ x \equiv a - y \cdot n \cdot \frac{a - b}{d} \bmod \frac{mn}{d}
+ \qquad \text{mit} \qquad
+ d := \ggT(n, m) = yn + zm
+ \]
+ Formel kann auch für nicht teilerfremde Moduli verwendet werden.
+ Sind die Moduli nicht teilerfremd, existiert genau dann eine Lösung,
+ wenn $a\equiv~b \bmod \ggT(m, n)$.
+ In diesem Fall sind keine Faktoren
+ auf der linken Seite erlaubt.
+ \end{itemize}
+ \sourcecode{math/chineseRemainder.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Primzahltest \& Faktorisierung}
+ \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
+ \sourcecode{math/millerRabin.cpp}
+ \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
+ \sourcecode{math/rho.cpp}
+ %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
+ %\sourcecode{math/squfof.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Teiler}
+ \begin{methods}
+ \method{countDivisors}{Zählt Teiler von $n$}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
+ \end{methods}
+ \sourcecode{math/divisors.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Primitivwurzeln}
+ \begin{itemize}
+ \item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$
+ \item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln
+ \item Sei $g$ Primitivwurzel modulo $n$.
+ Dann gilt:\newline
+ Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.
+ \end{itemize}
+ \begin{methods}
+ \method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}
+ \method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}
+ \end{methods}
+ \sourcecode{math/primitiveRoot.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Diskreter Logarithmus}
+ \begin{methods}
+ \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
+ \end{methods}
+ \sourcecode{math/discreteLogarithm.cpp}
+\end{algorithm}
+%TODO
+\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel}
+ \begin{methods}
+ \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
+ \end{methods}
+ Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
+ \sourcecode{math/discreteNthRoot.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Linearessieb und Multiplikative Funktionen}
+ Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.
+
+ $\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen.
+
+ \begin{methods}
+ \method{sieve}{berechnet Primzahlen und co.}{N}
+ \method{sieved}{Wert der endsprechenden Multiplikativen Funktion}{1}
+
+ \method{naive}{Wert der endsprechenden Multiplikativen Funktion}{\sqrt{n}}
+ \end{methods}
+ \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!
+
+ \sourcecode{math/linearSieve.cpp}
+ \textbf{\textsc{Möbius} Funtkion:}
+ \begin{itemize}
+ \item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat
+ \item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat
+ \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist
+ \end{itemize}
+
+ \textbf{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion:}
+ \begin{itemize}
+ \item Zählt die relativ primen Zahlen $\leq n$.
+ \item $p$ prim, $k \in \mathbb{N}$:
+ $~\varphi(p^k) = p^k - p^{k - 1}$
+
+ \item \textbf{Euler's Theorem:}
+ Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.
+ Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:
+ $a^{m} \equiv a \pmod{m}$
+ \end{itemize}
+\end{algorithm}
+
+
+\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
+ \begin{itemize}
+ \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
+ \end{itemize}
+ \begin{methods}
+ \method{primeSieve}{berechnet Primzahlen und Anzahl}{N\*\log(\log(N))}
+ \method{isPrime}{prüft ob Zahl prim ist}{1}
+ \end{methods}
+ \sourcecode{math/primeSieve.cpp}
+\end{algorithm}
+
+\begin{algorithm}{\textsc{Möbius}-Inversion}
+ \begin{itemize}
+ \item Seien $f,g : \mathbb{N} \to \mathbb{N}$ und $g(n) := \sum_{d \vert n}f(d)$.
+ Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
+ \item $\sum\limits_{d \vert n}\mu(d) =
+ \begin{cases*}
+ 1 & falls $n = 1$\\
+ 0 & sonst
+ \end{cases*}$
+ \end{itemize}
+ \textbf{Beispiel Inklusion/Exklusion:}
+ Gegeben sein eine Sequenz $A={a_1,\ldots,a_n}$ von Zahlen, $1 \leq a_i \leq N$. Zähle die Anzahl der \emph{coprime subsequences}.\newline
+ \textbf{Lösung}:
+ Für jedes $x$, sei $cnt[x]$ die Anzahl der Vielfachen von $x$ in $A$.
+ Es gibt $2^{[x]}-1$ nicht leere Subsequences in $A$, die nur Vielfache von $x$ enthalten.
+ Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
+ %\sourcecode{math/mobius.cpp}
+\end{algorithm}
+
+%\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}
+
+\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
+ Multipliziert Polynome $A$ und $B$.
+ \begin{itemize}
+ \item $\deg(A \cdot B) = \deg(A) + \deg(B)$
+ \item Vektoren \code{a} und \code{b} müssen mindestens Größe
+ $\deg(A \cdot B) + 1$ haben.
+ Größe muss eine Zweierpotenz sein.
+ \item Für ganzzahlige Koeffizienten: \code{(ll)round(real(a[i]))}
+ \item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
+ \end{itemize}
+ %\lstinputlisting{math/fft.cpp}
+ %\lstinputlisting{math/ntt.cpp}
+ %\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code
+ \sourcecode{math/transforms/all.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}
+
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
+
+\clearpage
+
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\begin{methods}
+ \method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
+ \method{phi}{zählt zu $p_i$ teilerfremde Zahlen $\leq n$ für alle $i \leq k$}{???}
+ \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}}
+\end{methods}
+\sourcecode{math/piLehmer.cpp}
+
+\begin{algorithm}{Lineare-Recurenz}
+ \begin{methods}
+ \method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}
+ \method{}{aus den ersten $2n$ Werte}{}
+ \end{methods}
+ \sourcecode{math/berlekampMassey.cpp}
+ Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.
+
+ \begin{methods}
+ \method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+ \end{methods}
+ \sourcecode{math/linearRecurence.cpp}
+ Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
+ $$\renewcommand\arraystretch{1.5}
+ \setlength\arraycolsep{3pt}
+ \begin{pmatrix}
+ c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\
+ 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\
+ 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\
+ 0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\
+ 0 & \smash{\cdots} & 0 & 1 & 0 \\
+ \end{pmatrix}^k
+ \times~~
+ \begin{pmatrix}
+ f(n-1) \\
+ f(n-2) \\
+ \smash{\vdots} \\
+ \smash{\vdots} \\
+ f(0) \\
+ \end{pmatrix}
+ ~~=~~
+ \begin{pmatrix}
+ f(n-1+k) \\
+ f(n-2+k) \\
+ \smash{\vdots} \\
+ \smash{\vdots} \\
+ f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
+ \end{pmatrix}
+ $$
+\end{algorithm}
+
+\begin{algorithm}{Matrix-Exponent}
+ \begin{methods}
+ \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
+ \method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+ \end{methods}
+ \sourcecode{math/matrixPower.cpp}
+\end{algorithm}
+
+\begin{algorithm}{\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}
+
+\subsection{Satz von \textsc{Sprague-Grundy}}
+Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
+\[
+g\left(X\right) := \min\left\{
+\mathbb{Z}_0^+ \setminus
+\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
+\right\}
+\]
+$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\
+Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
+
+\subsection{Kombinatorik}
+
+\paragraph{Wilsons Theorem}
+A number $n$ is prime if and only if
+$(n-1)!\equiv -1\bmod{n}$.\\
+($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$)
+\begin{align*}
+ (n-1)!\equiv\begin{cases}
+ -1\bmod{n},&\mathrm{falls}~n \in \mathbb{P}\\
+ \hphantom{-}2\bmod{n},&\mathrm{falls}~n = 4\\
+ \hphantom{-}0\bmod{n},&\mathrm{sonst}
+ \end{cases}
+\end{align*}
+
+\paragraph{\textsc{Zeckendorfs} Theorem}
+Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer
+verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei
+aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\
+\emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch
+hineinpasst.
+
+\paragraph{\textsc{Lucas}-Theorem}
+Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung),
+so gilt
+\vspace{-0.75\baselineskip}
+\[
+ \binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}.
+\]
+
+%\begin{algorithm}{Binomialkoeffizienten}
+\paragraph{Binomialkoeffizienten}
+ Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
+ \begin{methods}
+ \method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
+ \method{calc\_binom}{berechnet Binomialkoeffizient}{1}
+ \end{methods}
+ \sourcecode{math/binomial0.cpp}
+ Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$
+\columnbreak
+
+ \begin{methods}
+ \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
+ \end{methods}
+ \sourcecode{math/binomial1.cpp}
+
+ \begin{methods}
+ \method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
+ \end{methods}
+ \sourcecode{math/binomial3.cpp}
+
+% \begin{methods}
+% \method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n}
+% \end{methods}
+% \textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
+% \sourcecode{math/binomial2.cpp}
+%\end{algorithm}
+
+\paragraph{\textsc{Catalan}-Zahlen}
+\begin{itemize}
+ \item Die \textsc{Catalan}-Zahl $C_n$ gibt an:
+ \begin{itemize}
+ \item Anzahl der Binärbäume mit $n$ nicht unterscheidbaren Knoten.
+ \item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren.
+ \item Anzahl der korrekten Klammerungen von $n+1$ Faktoren.
+ \item Anzahl Möglichkeiten ein konvexes Polygon mit $n + 2$ Ecken zu triangulieren.
+ \item Anzahl der monotonen Pfade (zwischen gegenüberliegenden Ecken) in
+ einem $n \times n$-Gitter, die nicht die Diagonale kreuzen.
+ \end{itemize}
+\end{itemize}
+\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
+\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} \cdot C_{n-1}\]
+\begin{itemize}
+ \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+ \item Formel $2$ und $3$ erlauben Berechnung in \runtime{n}
+\end{itemize}
+
+\paragraph{\textsc{Catalan}-Convolution}
+\begin{itemize}
+ \item Anzahl an Klammerausdrücken mit $n+k$ Klammerpaaren, die mit $(^k$ beginnen.
+\end{itemize}
+\[C^k_0 = 1\qquad C^k_n = \sum\limits_{\mathclap{a_0+a_1+\dots+a_k=n}} C_{a_0}C_{a_1}\cdots C_{a_k} =
+\frac{k+1}{n+k+1}\binom{2n+k}{n} = \frac{(2n+k-1)\cdot(2n+k)}{n(n+k+1)} \cdot C_{n-1}\]
+
+\paragraph{\textsc{Euler}-Zahlen 1. Ordnung}
+Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
+Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
+Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
+\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad
+\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}=
+\sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\]
+\begin{itemize}
+ \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+ \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
+\end{itemize}
+
+\paragraph{\textsc{Euler}-Zahlen 2. Ordnung}
+Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
+\[\eulerII{n}{0} = 1 \qquad\eulerII{n}{n} = 0 \qquad\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}\]
+\begin{itemize}
+ \item Formel erlaubt Berechnung ohne Division in \runtime{n^2}
+\end{itemize}
+
+\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}
+Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Zyklen.
+Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eigene Zyklus, oder sie kann an jeder Position in jedem Zyklus einsortiert werden.
+\[\stirlingI{0}{0} = 1 \qquad
+\stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
+\stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}\]
+\begin{itemize}
+ \item Formel erlaubt berechnung ohne Division in \runtime{n^2}
+\end{itemize}
+\[\sum_{k=0}^{n}\pm\stirlingI{n}{k}x^k=x(x-1)(x-2)\cdots(x-n+1)\]
+\begin{itemize}
+ \item Berechne Polynom mit FFT und benutzte betrag der Koeffizienten \runtime{n\log(n)^2} (nur ungefähr gleich große Polynome zusammen multiplizieren beginnend mit $x-k$)
+\end{itemize}
+
+\paragraph{\textsc{Stirling}-Zahlen 2. Ordnung}
+Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
+Es gibt $k$ Möglichkeiten die $n$ in eine $n-1$-Partition einzuordnen.
+Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
+\[\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
+\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
+\frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\]
+\begin{itemize}
+ \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+ \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
+\end{itemize}
+
+\paragraph{\textsc{Bell}-Zahlen}
+Anzahl der Partitionen von $\{1, \ldots, n\}$.
+Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
+\[B_1 = 1 \qquad
+B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
+= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
+
+\paragraph{Partitions}
+Die Anzahl der Partitionen von $n$ in genau $k$ positive Summanden.
+Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
+\begin{align*}
+ p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
+ p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
+ p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg)
+\end{align*}
+\begin{itemize}
+ \item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
+ \item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.
+\end{itemize}
+
+\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
+\input{math/tables/twelvefold}
+
+%\input{math/tables/numbers}
+
+\begin{algorithm}[optional]{Big Integers}
+ \sourcecode{math/bigint.cpp}
+\end{algorithm}
diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp
new file mode 100644
index 0000000..747eb7a
--- /dev/null
+++ b/math/shortModInv.cpp
@@ -0,0 +1,3 @@
+ll inv(ll a, ll b){ // a^{-1} mod b
+ return 1 < a ? b - inv(b % a, a) * b / a : 1;
+} \ No newline at end of file
diff --git a/other/other.tex b/other/other.tex
index 2063aea..808d288 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -1,306 +1,306 @@
-\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 werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen.
- \sourcecode{other/timed.cpp}
-\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 setzten & \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 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}{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}{Pragmas}
- \sourcecode{other/pragmas.cpp}
-\end{algorithm}
-
-\begin{algorithm}{DP Optimizations}
- Aufgabe: Partitioniere Array in genau $k$ zusammenhängende Teile mit minimalen Kosten:
- $dp[i][j] = \min_{k<j}\{dp[i-1][k]+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}{k\*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} $\text{res}[\text{mask}]=\sum_{i\subseteq\text{mask}}\text{in}[i]$.
- Für Summe über Supersets \code{res} einmal vorher und einmal nachher reversen.
- \sourcecode{other/sos.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Parallel Binary Search}
- \sourcecode{other/pbs.cpp}
-\end{algorithm}
-
-\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_n1$ die Position des letzten Überlebenden.
- (Rotiere $n$ um eine Stelle nach links)
- \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}
- \textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
-\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{Dinic'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{Johnsons} Reweighting Algorithmus:}
- 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 Gweicht \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{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:}
- 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$, makiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die makierten Knoten aus $B$ und die unmakierten 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{Verteilung von Primzahlen:}
- Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n \leq p \leq 2n$.
-
- \item \textbf{Satz von \textsc{Kirchhoff}:}
- 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, $b_{ii}$ sei der Grad von Knoten $i$.
- Definiere $R = B - A$.
- Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$.
- \newline
- Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.
-
- \item \textbf{\textsc{Dilworths}-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: 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 Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden.
-
- \item \textbf{\textsc{Turan}'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}'s-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 verhält sich periodisch alle $400$ Jahre.
-
- \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 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?
- \end{itemize}
-
- \item Strings:
- \begin{itemize}
- \item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?
- \item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.
- \end{itemize}
-
- \item 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 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}
+\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 werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen.
+ \sourcecode{other/timed.cpp}
+\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 setzten & \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 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}{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}{Pragmas}
+ \sourcecode{other/pragmas.cpp}
+\end{algorithm}
+
+\begin{algorithm}{DP Optimizations}
+ Aufgabe: Partitioniere Array in genau $k$ zusammenhängende Teile mit minimalen Kosten:
+ $dp[i][j] = \min_{k<j}\{dp[i-1][k]+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}{k\*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} $\text{res}[\text{mask}]=\sum_{i\subseteq\text{mask}}\text{in}[i]$.
+ Für Summe über Supersets \code{res} einmal vorher und einmal nachher reversen.
+ \sourcecode{other/sos.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Parallel Binary Search}
+ \sourcecode{other/pbs.cpp}
+\end{algorithm}
+
+\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_n1$ die Position des letzten Überlebenden.
+ (Rotiere $n$ um eine Stelle nach links)
+ \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}
+ \textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
+\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{Dinic'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{Johnsons} Reweighting Algorithmus:}
+ 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 Gweicht \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{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:}
+ 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$, makiere alle Knoten die von einem ungematchten Knoten in $A$ erreichbar sind, das Vertex Cover sind die makierten Knoten aus $B$ und die unmakierten 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{Verteilung von Primzahlen:}
+ Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n \leq p \leq 2n$.
+
+ \item \textbf{Satz von \textsc{Kirchhoff}:}
+ 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, $b_{ii}$ sei der Grad von Knoten $i$.
+ Definiere $R = B - A$.
+ Alle Kofaktoren von $R$ sind gleich und die Anzahl der Spannbäume von $G$.
+ \newline
+ Entferne letzte Zeile und Spalte und berechne Betrag der Determinante.
+
+ \item \textbf{\textsc{Dilworths}-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: 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 Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden.
+
+ \item \textbf{\textsc{Turan}'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}'s-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 verhält sich periodisch alle $400$ Jahre.
+
+ \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 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 Strings:
+ \begin{itemize}
+ \item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?
+ \item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.
+ \end{itemize}
+
+ \item 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 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}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 23:11:07 +0000