From db5ee187a9fb8d9338c74e74c2d2b4b38b2ab586 Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Tue, 27 Feb 2024 15:56:26 +0100 Subject: minor formatting and spelling fixes --- geometry/geometry.tex | 4 ++-- graph/graph.tex | 8 ++++---- math/linearRecurence.cpp | 33 --------------------------------- math/linearRecurrence.cpp | 33 +++++++++++++++++++++++++++++++++ math/math.tex | 27 ++++++++++++++------------- string/string.tex | 14 +++++++------- 6 files changed, 60 insertions(+), 59 deletions(-) delete mode 100644 math/linearRecurence.cpp create mode 100644 math/linearRecurrence.cpp diff --git a/geometry/geometry.tex b/geometry/geometry.tex index 13291eb..d740f46 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -9,10 +9,10 @@ \begin{algorithm}{Konvexe Hülle} \begin{methods} - \method{convexHull}{berechnet Konvexe Hülle}{n\*\log(n)} + \method{convexHull}{berechnet konvexe Hülle}{n\*\log(n)} \end{methods} \begin{itemize} - \item Konvexe Hülle gegen den Uhrzeigersinn sortiert + \item konvexe Hülle gegen den Uhrzeigersinn sortiert \item nur Eckpunkte enthalten(für alle Punkte = im CCW Test entfernen) \item erster und letzter Punkt sind identisch \end{itemize} diff --git a/graph/graph.tex b/graph/graph.tex index e9c32c7..4394192 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -71,7 +71,7 @@ Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. \end{algorithm} -\begin{algorithm}{Kruskal} +\begin{algorithm}{\textsc{Kruskal}} \begin{methods}[ll] berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ \end{methods} @@ -103,7 +103,7 @@ 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}{Erd\H{o}s-Gallai} +\begin{algorithm}{\textsc{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)$ \begin{methods} \method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})} @@ -223,9 +223,9 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/pushRelabel2.cpp} -\subsubsection{Dinic's Algorithm mit Capacity Scaling} +\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} \begin{methods} - \method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}} + \method{maxFlow}{doppelt so schnell wie \textsc{Ford-Fulkerson}}{\abs{V}^2\cdot\abs{E}} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} \sourcecode{graph/dinicScaling.cpp} diff --git a/math/linearRecurence.cpp b/math/linearRecurence.cpp deleted file mode 100644 index 2501e64..0000000 --- a/math/linearRecurence.cpp +++ /dev/null @@ -1,33 +0,0 @@ -constexpr ll mod = 1'000'000'007; -vector modMul(const vector& a, const vector& b, - const vector& c) { - ll n = sz(c); - vector res(n * 2 + 1); - for (int i = 0; i <= n; i++) { //a*b - for (int j = 0; j <= n; j++) { - res[i + j] += a[i] * b[j]; - res[i + j] %= mod; - }} - for (int i = 2 * n; i > n; i--) { //res%c - for (int j = 0; j < n; j++) { - res[i - 1 - j] += res[i] * c[j]; - res[i - 1 - j] %= mod; - }} - res.resize(n + 1); - return res; -} - -ll kthTerm(const vector& f, const vector& c, ll k) { - assert(sz(f) == sz(c)); - vector tmp(sz(c) + 1), a(sz(c) + 1); - tmp[0] = a[1] = 1; //tmp = (x^k) % c - - for (k++; k > 0; k /= 2) { - if (k & 1) tmp = modMul(tmp, a, c); - a = modMul(a, a, c); - } - - ll res = 0; - for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; - return res % mod; -} diff --git a/math/linearRecurrence.cpp b/math/linearRecurrence.cpp new file mode 100644 index 0000000..2501e64 --- /dev/null +++ b/math/linearRecurrence.cpp @@ -0,0 +1,33 @@ +constexpr ll mod = 1'000'000'007; +vector modMul(const vector& a, const vector& b, + const vector& c) { + ll n = sz(c); + vector res(n * 2 + 1); + for (int i = 0; i <= n; i++) { //a*b + for (int j = 0; j <= n; j++) { + res[i + j] += a[i] * b[j]; + res[i + j] %= mod; + }} + for (int i = 2 * n; i > n; i--) { //res%c + for (int j = 0; j < n; j++) { + res[i - 1 - j] += res[i] * c[j]; + res[i - 1 - j] %= mod; + }} + res.resize(n + 1); + return res; +} + +ll kthTerm(const vector& f, const vector& c, ll k) { + assert(sz(f) == sz(c)); + vector tmp(sz(c) + 1), a(sz(c) + 1); + tmp[0] = a[1] = 1; //tmp = (x^k) % c + + for (k++; k > 0; k /= 2) { + if (k & 1) tmp = modMul(tmp, a, c); + a = modMul(a, a, c); + } + + ll res = 0; + for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; + return res % mod; +} diff --git a/math/math.tex b/math/math.tex index 8ccc55e..a9e4c74 100644 --- a/math/math.tex +++ b/math/math.tex @@ -151,21 +151,21 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/discreteNthRoot.cpp} \end{algorithm} -\begin{algorithm}{Linearessieb und Multiplikative Funktionen} +\begin{algorithm}{Lineares Sieb und multiplikative Funktionen} Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$. $\Rightarrow$ Es ist ausreichend $f(p^k)$ für alle primen $p$ und alle $k$ zu kennen. \begin{methods} \method{sieve}{berechnet Primzahlen und co.}{N} - \method{sieved}{Wert der endsprechenden Multiplikativen Funktion}{1} + \method{sieved}{Wert der entsprechenden multiplikativen Funktion}{1} - \method{naive}{Wert der endsprechenden Multiplikativen Funktion}{\sqrt{n}} + \method{naive}{Wert der entsprechenden multiplikativen Funktion}{\sqrt{n}} \end{methods} \textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}! \sourcecode{math/linearSieve.cpp} - \textbf{\textsc{Möbius} Funtkion:} + \textbf{\textsc{Möbius} Funktion:} \begin{itemize} \item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat \item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat @@ -178,7 +178,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \item $p$ prim, $k \in \mathbb{N}$: $~\varphi(p^k) = p^k - p^{k - 1}$ - \item \textbf{Euler's Theorem:} + \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}$ @@ -282,18 +282,18 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{methods} \sourcecode{math/piLehmer.cpp} -\begin{algorithm}{Lineare-Recurenz} +\begin{algorithm}{Lineare Rekurrenz} \begin{methods} - \method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2} + \method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2} \method{}{aus den ersten $2n$ Werte}{} \end{methods} \sourcecode{math/berlekampMassey.cpp} - Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz. + Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Rekurrenz. \begin{methods} - \method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2} + \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2} \end{methods} - \sourcecode{math/linearRecurence.cpp} + \sourcecode{math/linearRecurrence.cpp} Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: $$\renewcommand\arraystretch{1.5} \setlength\arraycolsep{3pt} @@ -375,7 +375,7 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \subsection{Kombinatorik} -\paragraph{Wilsons Theorem} +\paragraph{\textsc{Wilson}'s Theorem} A number $n$ is prime if and only if $(n-1)!\equiv -1\bmod{n}$.\\ ($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$) @@ -387,14 +387,14 @@ $(n-1)!\equiv -1\bmod{n}$.\\ \end{cases} \end{align*} -\paragraph{\textsc{Zeckendorfs} Theorem} +\paragraph{\textsc{Zeckendorf}'s Theorem} Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen.\\ \emph{Lösung:} Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch hineinpasst. -\paragraph{\textsc{Lucas}-Theorem} +\paragraph{\textsc{Lucas}'s Theorem} Ist $p$ prim, $m=\sum_{i=0}^km_ip^i$, $n=\sum_{i=0}^kn_ip^i$ ($p$-adische Darstellung), so gilt \vspace{-0.75\baselineskip} @@ -405,6 +405,7 @@ so gilt %\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} diff --git a/string/string.tex b/string/string.tex index c36ec69..aec50d5 100644 --- a/string/string.tex +++ b/string/string.tex @@ -60,21 +60,21 @@ \sourcecode{string/ahoCorasick.cpp} \end{algorithm} -\begin{algorithm}{Lyndon und De-Bruijn} +\begin{algorithm}{\textsc{Lyndon} und \textsc{De-Bruijn}} \begin{itemize} - \item \textbf{Lyndon-Wort:} Ein Wort das lexikographisch kleiner ist als jede seiner Rotationen. - \item Jedes Wort kann \emph{eindeutig} in eine nicht ansteigende Folge von Lyndon-Worten zerlegt werden. - \item Für Lyndon-Worte $u, v$ mit $u