From ed2cdb7ff56664d2447301802e574c9289ca4e3f Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 16 Nov 2024 22:05:24 +0100 Subject: cosmetic changes --- content/math/math.tex | 2 +- content/math/matrixPower.cpp | 8 ++++---- content/other/other.tex | 12 ++++++------ 3 files changed, 11 insertions(+), 11 deletions(-) (limited to 'content') diff --git a/content/math/math.tex b/content/math/math.tex index 2f50845..d59da54 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -121,7 +121,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \begin{algorithm}{Matrix-Exponent} \begin{methods} \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3} - \method{calc}{berechnet $m^b\cdot$}{\log(b)\cdot n^2} + \method{calc}{berechnet $m^b \cdot v$}{\log(b)\cdot n^2} \end{methods} \textbf{Tipp:} wenn \code{v[x]=1} und \code{0} sonst, dann ist \code{res[y]} = $m^b_{y,x}$. \sourcecode{math/matrixPower.cpp} diff --git a/content/math/matrixPower.cpp b/content/math/matrixPower.cpp index 0729c15..d80dac6 100644 --- a/content/math/matrixPower.cpp +++ b/content/math/matrixPower.cpp @@ -1,14 +1,14 @@ vector pows; void precalc(mat m) { - pows = {mat(ssize(m.m), 1), m}; - for (int i = 1; i < 60; i++) pows.push_back(pows[i] * pows[i]); + pows = {m}; + for (int i = 0; i < 60; i++) pows.push_back(pows[i] * pows[i]); } auto calc(ll b, vector v) { - for (ll i = 1; b > 0; i++) { + for (ll i = 0; b > 0; i++) { if (b & 1) v = pows[i] * v; - b /= 2; + b >>= 1; } return v; } diff --git a/content/other/other.tex b/content/other/other.tex index 9f8cfce..153fc2d 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -125,7 +125,7 @@ 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:} + \item \textbf{\textsc{Johnson}s Reweighting Algorithm:} Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen. Falls es einen negativen Zyklus gibt abrrechen. Sonst ändere die Gewichte von allen Kanten \texttt{(u,v)} im ursprünglichen Graphen zu \texttt{d[u]+w[u,v]-d[v]}. @@ -184,8 +184,8 @@ [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{\textsc{Bertrand}sches Postulat:} + Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$. \item \textbf{Satz von \textsc{Kirchhoff}:} Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten. @@ -197,7 +197,7 @@ \newline Entferne letzte Zeile und Spalte und berechne Betrag der Determinante. - \item \textbf{\textsc{Dilworths}-Theorem:} + \item \textbf{\textsc{Dilworth}'s Theorem:} Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset). Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$. Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist. @@ -211,13 +211,13 @@ 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 Antikette zu finden. - \item \textbf{\textsc{Turan}'s-Theorem:} + \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:} + \item \textbf{\textsc{Euler}scher Polyedersatz:} In planaren Graphen gilt $n-m+f-c=1$. \item \textbf{\textsc{Pythagoreische Tripel}:} -- cgit v1.2.3