From 9e9c033aa41f786f494cadea43563f83f3e951a3 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 7 Sep 2024 23:41:49 +0200 Subject: insert divsum --- content/graph/dinicScaling.cpp | 21 +++++++++++++-------- content/graph/graph.tex | 4 ++-- content/math/divSum.cpp | 15 +++++++-------- content/math/gauss.cpp | 12 +++++------- content/math/lgsFp.cpp | 3 +-- content/math/math.tex | 14 ++++++++++---- content/tcr.tex | 1 - tcr.pdf | Bin 673187 -> 691497 bytes 8 files changed, 38 insertions(+), 32 deletions(-) diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index f4e833a..0974b78 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -26,17 +26,18 @@ bool bfs(ll lim) { return dist[t] >= 0; } -bool dfs(int v, ll flow) { - if (v == t) return true; +ll dfs(int v, ll flow) { + if (v == t || flow == 0) return flow; for (; pt[v] < sz(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; - if (e.c - e.f >= flow && dfs(e.to, flow)) { - e.f += flow; - adj[e.to][e.rev].f -= flow; - return true; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; }} - return false; + return 0; } ll maxFlow(int source, int target) { @@ -45,7 +46,11 @@ ll maxFlow(int source, int target) { for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { pt.assign(sz(adj), 0); - while (dfs(s, lim)) flow += lim; + ll cur; + do { + cur = dfs(s, lim); + flow += cur; + } while (cur > 0); }} return flow; } diff --git a/content/graph/graph.tex b/content/graph/graph.tex index 831f4e5..213c597 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -211,6 +211,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/minCostMaxFlow.cpp} \end{algorithm} +\vfill\null +\columnbreak \subsubsection{Dinic's Algorithm mit Capacity Scaling} \begin{methods} @@ -218,8 +220,6 @@ 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\null -\columnbreak \optional{ \subsubsection{Anwendungen} diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp index dc4bc4d..48302b5 100644 --- a/content/math/divSum.cpp +++ b/content/math/divSum.cpp @@ -1,9 +1,8 @@ -// Calculates the sum of (a*i+b)/m for i=0..(n-1) in O(log(n)) -// Note that b should not be negative! ll divSum(ll n, ll m, ll a, ll b){ - if(m == 0) return 0; - ll ans = a/m * n*(n-1) / 2 + b/m * n; - a %= m, b %= m; - ll y = (a*(n-1)+b)/m; - return ans + y*(n-1) - divSum(y, a, m, m-b-1); -} \ No newline at end of file + if (m == 0) return 0; + ll ans = a/m * n*(n-1)/2 + b/m * n; + a %= m; + b %= m; + ll y = (a*(n-1)+b) / m; + return ans + y * (n-1) - divSum(y, a, m, m-b-1); +} diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp index 8129fd2..d431e52 100644 --- a/content/math/gauss.cpp +++ b/content/math/gauss.cpp @@ -14,19 +14,17 @@ void takeAll(int n, int line) { int gauss(int n) { vector done(n, false); for (int i = 0; i < n; i++) { - int swappee = i; // Sucht Pivotzeile für bessere Stabilität. - for (int j = 0; j < n; j++) { - if (done[j]) continue; - if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j; + int j = i; // Sucht Pivotzeile für bessere Stabilität. + for (int k = 0; k < n; k++) { + if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k; } - swap(mat[i], mat[swappee]); + swap(mat[i], mat[j]); if (abs(mat[i][i]) > EPS) { normalLine(i); takeAll(n, i); done[i] = true; }} - // Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung. - for (int i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung bool allZero = true; for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS; if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT; diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index 0241742..bf18c86 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -22,5 +22,4 @@ void gauss(int n, ll mod) { normalLine(i, mod); takeAll(n, i, mod); done[i] = true; -}} -// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ +}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ diff --git a/content/math/math.tex b/content/math/math.tex index c15825f..fffdf37 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -306,7 +306,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \method{gauss}{löst LGS}{n^3} \sourcecode{math/gauss.cpp} -\vfill\null\columnbreak +\begin{algorithm}{Inversionszahl} + \vspace{-2pt} + \sourcecode{math/inversions.cpp} +\end{algorithm} \begin{algorithm}{Numerisch Extremstelle bestimmen} \sourcecode{math/goldenSectionSearch.cpp} @@ -316,7 +319,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/simpson.cpp} \end{algorithm} - \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen} Multipliziert Polynome $A$ und $B$. \begin{itemize} @@ -340,8 +342,11 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/transforms/seriesOperations.cpp} \end{algorithm} -\begin{algorithm}{Inversionszahl} - \sourcecode{math/inversions.cpp} + +\begin{algorithm}{Div Sum} + \method{divSum}{berechnet $\sum_{i=0}^{n-1} \frac{a\cdot i + b}{m}$}{\log(n)} + \textbf{Wichtig:} $b$ darf nicht negativ sein! + \sourcecode{math/divSum.cpp} \end{algorithm} \subsection{Satz von \textsc{Sprague-Grundy}} @@ -394,6 +399,7 @@ so gilt \end{methods} \sourcecode{math/binomial0.cpp} Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$ + \columnbreak \begin{methods} \method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k} diff --git a/content/tcr.tex b/content/tcr.tex index 4e4353b..b3cfb17 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -17,7 +17,6 @@ \usepackage[T1]{fontenc} \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} -\usepackage[nopatch=footnote]{microtype} \usepackage[hidelinks,pdfencoding=auto]{hyperref} % Include headers. diff --git a/tcr.pdf b/tcr.pdf index 488ac70..c16c3cc 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3