From 9e8344e44eb06ac4a8618413ff2b2311c6348dad Mon Sep 17 00:00:00 2001 From: MZuenni Date: Fri, 28 Jun 2024 14:54:23 +0200 Subject: polishing --- math/math.tex | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'math/math.tex') diff --git a/math/math.tex b/math/math.tex index f9a5ea5..dc0eb00 100644 --- a/math/math.tex +++ b/math/math.tex @@ -172,7 +172,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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}-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 @@ -313,16 +313,16 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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} Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: @@ -332,7 +332,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: 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} \\ + \smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\ 0 & \smash{\cdots} & 0 & 1 & 0 \\ \end{pmatrix}^k \times~~ -- cgit v1.2.3 From 545265f2f3992e15c45f1bbb99e04a27e1fc7856 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 30 Jun 2024 00:26:10 +0200 Subject: improvements --- datastructures/datastructures.tex | 1 + graph/LCA_sparse.cpp | 2 +- graph/cycleCounting.cpp | 2 +- graph/graph.tex | 4 ++-- graph/matching.cpp | 2 +- latexHeaders/commands.sty | 5 +++++ math/discreteNthRoot.cpp | 2 +- math/inversions.cpp | 2 +- math/lgsFp.cpp | 2 +- math/math.tex | 2 +- other/other.tex | 2 +- tcr.pdf | Bin 666019 -> 665586 bytes 12 files changed, 16 insertions(+), 10 deletions(-) (limited to 'math/math.tex') diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 1ccefaa..d35dfb0 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -22,6 +22,7 @@ \end{methods} \sourcecode{datastructures/waveletTree.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{Fenwick Tree} \begin{methods} diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp index 2a864c0..649e697 100644 --- a/graph/LCA_sparse.cpp +++ b/graph/LCA_sparse.cpp @@ -2,7 +2,7 @@ struct LCA { vector depth; vector visited, first; int idx; - SparseTable st; //sparse table von oben + SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector>& adj, int root) { depth.assign(2 * sz(adj), 0); diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp index 9772706..bd7a219 100644 --- a/graph/cycleCounting.cpp +++ b/graph/cycleCounting.cpp @@ -39,7 +39,7 @@ struct cylces { //cycle must be constrcuted from base bool isCycle(cycle cur) { if (cur.none()) return false; - init(sz(adj)); // union find + init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ for (int i = 0; i < sz(edges); i++) { if (cur[i]) { cur[i] = false; diff --git a/graph/graph.tex b/graph/graph.tex index 0f516ac..9232090 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -225,7 +225,7 @@ 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* +\vfill\null \columnbreak \optional{ @@ -256,7 +256,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} -\vfill* +\vfill\null \columnbreak diff --git a/graph/matching.cpp b/graph/matching.cpp index f059351..2513604 100644 --- a/graph/matching.cpp +++ b/graph/matching.cpp @@ -12,7 +12,7 @@ int max_matching() { mat[v][u] = rand() % (MOD - 1) + 1; mat[u][v] = MOD - mat[v][u]; }}} - gauss(sz(adj), MOD); //LGS unten + gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ int rank = 0; for (auto& row : mat) { if (*min_element(all(row)) != 0) rank++; diff --git a/latexHeaders/commands.sty b/latexHeaders/commands.sty index da78745..edbba1b 100644 --- a/latexHeaders/commands.sty +++ b/latexHeaders/commands.sty @@ -30,12 +30,17 @@ %\ifthenelse{\equal{#3}{}}{}{\runtime{#3}} \newcommand{\sourcecode}[1]{% + \label{code:#1}% \nobreak% % \needspace{3\baselineskip}% % \nopagebreak% \lstinputlisting{#1}% \penalty -1000% } +\newcommand{\sourceref}[1]{{% + \color{comment}\bfseries\itshape{}Seite \pageref{code:#1}% +}} + \newcommand{\method}[4][]{\texttt{#2}~~#3~~\runtime{#4}#1\par} \newenvironment{methods}[1][lll]{% diff --git a/math/discreteNthRoot.cpp b/math/discreteNthRoot.cpp index 9249f73..7201b2b 100644 --- a/math/discreteNthRoot.cpp +++ b/math/discreteNthRoot.cpp @@ -1,5 +1,5 @@ ll root(ll a, ll b, ll m) { ll g = findPrimitive(m); - ll c = dlog(powMod(g, a, m), b, m); //diskreter logarithmus + ll c = dlog(powMod(g, a, m), b, m); //dLog @\sourceref{math/discreteLogarithm.cpp}@ return c < 0 ? -1 : powMod(g, c, m); } diff --git a/math/inversions.cpp b/math/inversions.cpp index 051408c..9e47f9b 100644 --- a/math/inversions.cpp +++ b/math/inversions.cpp @@ -1,5 +1,5 @@ ll inversions(const vector& v) { - Tree> t; //ordered statistics tree + Tree> t; //ordered statistics tree @\sourceref{datastructures/pbds.cpp}@ ll res = 0; for (ll i = 0; i < sz(v); i++) { res += i - t.order_of_key({v[i], i}); diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp index 7dcd354..7081fea 100644 --- a/math/lgsFp.cpp +++ b/math/lgsFp.cpp @@ -23,4 +23,4 @@ void gauss(int n, ll mod) { takeAll(n, i, mod); done[i] = true; }} -// für Eindeutigkeit, Existenz etc. siehe LGS +// für Eindeutigkeit, Existenz etc. siehe LGS über R diff --git a/math/math.tex b/math/math.tex index dc0eb00..c157e1b 100644 --- a/math/math.tex +++ b/math/math.tex @@ -257,7 +257,7 @@ 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* + \vfill\null \columnbreak \sourcecode{math/transforms/bitwiseTransforms.cpp} Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!) diff --git a/other/other.tex b/other/other.tex index a21eb37..38434a5 100644 --- a/other/other.tex +++ b/other/other.tex @@ -227,7 +227,7 @@ \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{Gregorian Calendar:} Der Anfangstag des Jahres ist alle $400$ Jahre gleich. \item \textbf{Pivotsuche und Rekursion auf linkem und rechtem Teilarray:} Suche gleichzeitig von links und rechts nach Pivot, um Worst Case von diff --git a/tcr.pdf b/tcr.pdf index 7114518..ec0e434 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3