diff options
32 files changed, 601 insertions, 584 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex index 4139219..1ccefaa 100644 --- a/datastructures/datastructures.tex +++ b/datastructures/datastructures.tex @@ -14,6 +14,15 @@ \sourcecode{datastructures/lazyPropagation.cpp} \end{algorithm} +\begin{algorithm}{Wavelet Tree} + \begin{methods} + \method{Constructor}{baut den Baum auf}{n\*\log(n)} + \method{kth}{sort $[l, r)[k]$}{\log(n)} + \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)} + \end{methods} + \sourcecode{datastructures/waveletTree.cpp} +\end{algorithm} + \begin{algorithm}{Fenwick Tree} \begin{methods} \method{init}{baut den Baum auf}{n\*\log(n)} @@ -29,11 +38,11 @@ \end{methods} \sourcecode{datastructures/fenwickTree2.cpp} \end{algorithm} -\clearpage \begin{algorithm}{STL-Rope (Implicit Cartesian Tree)} \sourcecode{datastructures/stlRope.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{(Implicit) Treap (Cartesian Tree)} \begin{methods} @@ -54,15 +63,6 @@ \sourcecode{datastructures/sparseTable.cpp} \end{algorithm} -\begin{algorithm}{Wavelet Tree} - \begin{methods} - \method{Constructor}{baut den Baum auf}{n\*\log(n)} - \method{kth}{sort $[l, r)[k]$}{\log(n)} - \method{countSmaller}{Anzahl elemente in $[l, r)$ kleiner als $k$}{\log(n)} - \end{methods} - \sourcecode{datastructures/waveletTree.cpp} -\end{algorithm} - \begin{algorithm}{STL-Bitset} \sourcecode{datastructures/bitset.cpp} \end{algorithm} @@ -81,6 +81,23 @@ \end{algorithm} \clearpage +\begin{algorithm}{Lichao} + \sourcecode{datastructures/lichao.cpp} +\end{algorithm} + +\begin{algorithm}{Policy Based Data Structures} + \textbf{Wichtig:} Verwende \code{p.swap(p2)} anstatt \code{swap(p, p2)}! + \sourcecode{datastructures/stlPriorityQueue.cpp} + \columnbreak + \sourcecode{datastructures/pbds.cpp} +\end{algorithm} + +\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)} + Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. + \sourcecode{datastructures/monotonicConvexHull.cpp} + \sourcecode{datastructures/dynamicConvexHull.cpp} +\end{algorithm} + \begin{algorithm}{Union-Find} \begin{methods} \method{init}{legt $n$ einzelne Unions an}{n} @@ -90,13 +107,7 @@ \end{methods} \sourcecode{datastructures/unionFind.cpp} \end{algorithm} - -\begin{algorithm}{Lower/Upper Envelope (Convex Hull Optimization)} - Um aus einem lower envelope einen upper envelope zu machen (oder umgekehrt), einfach beim Einfügen der Geraden $m$ und $b$ negieren. - \sourcecode{datastructures/monotonicConvexHull.cpp} - \columnbreak - \sourcecode{datastructures/dynamicConvexHull.cpp} -\end{algorithm} +\columnbreak \begin{algorithm}{Persistent} \begin{methods} @@ -108,22 +119,6 @@ \sourcecode{datastructures/persistentArray.cpp} \end{algorithm} -\begin{algorithm}{STL-Tree} - \sourcecode{datastructures/stlTree.cpp} -\end{algorithm} - -\begin{algorithm}{STL Priority Queue} - Nicht notwendig, wenn Smaller-Larger-Optimization greift. - \sourcecode{datastructures/stlPQ.cpp} -\end{algorithm} - -\begin{algorithm}{STL HashMap} - 3 bis 4 mal langsamer als \code{std::vector} aber 8 bis 9 mal schneller als \code{std::map} - \sourcecode{datastructures/stlHashMap.cpp} -\end{algorithm} - - - \begin{algorithm}[optional]{Range Minimum Query} \begin{methods} \method{init}{baut Struktur auf}{n\*\log(n)} @@ -138,4 +133,3 @@ \end{methods} \sourcecode{datastructures/firstUnused.cpp} \end{algorithm} - diff --git a/datastructures/lazyPropagation.cpp b/datastructures/lazyPropagation.cpp index 7af1a6a..0fe7bbe 100644 --- a/datastructures/lazyPropagation.cpp +++ b/datastructures/lazyPropagation.cpp @@ -65,13 +65,12 @@ struct SegTree { ll lower_bound(int l, int r, T x) { l += n, r += n; push(l), push(r - 1); - vector<int> a, st; + int a[64] = {}, lp = 0, rp = 64; for (; l < r; l /= 2, r /= 2) { - if (l&1) a.push_back(l++); - if (r&1) st.push_back(--r); + if (l&1) a[lp++] = l++; + if (r&1) a[--rp] = --r; } - a.insert(a.end(), st.rbegin(), st.rend()); - for (int i : a) if (tree[i] >= x) { // Modify this + for (int i : a) if (i != 0 && tree[i] >= x) { // Modify this while (i < n) { push_down(i); if (tree[2 * i] >= x) i = 2 * i; // And this diff --git a/datastructures/lichao.cpp b/datastructures/lichao.cpp index e12d243..f66778e 100644 --- a/datastructures/lichao.cpp +++ b/datastructures/lichao.cpp @@ -1,44 +1,46 @@ -vector<ll> xs; // IMPORTANT: Initialize before constructing Lichao! -int findX(int i) {return distance(xs.begin(), lower_bound(all(xs), i));} +vector<ll> xs; // IMPORTANT: Initialize before constructing! +int findX(int i) {return lower_bound(all(xs), i) - begin(xs);} -struct Fun{ // Default: Linear function. Change it to needed function type. - ll m, c; - ll operator()(int x) {return m*xs[x] + c;} +struct Fun { // Default: Linear function. Change as needed. + ll m, c; + ll operator()(int x) {return m*xs[x] + c;} }; // Default: Computes min. Change lines with comment for max. -struct Lichao{ - static constexpr Fun id = {0, inf}; // {0, -inf} - int n, cap; - vector<Fun> seg; - Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {} - - void _insert(Fun f, int l, int r, int i) { - while (i < 2*cap){ - int m = (l+r)/2; - if (m >= n) {r = m; i = 2*i; continue;} - Fun &g = seg[i]; - if (f(m) < g(m)) swap(f, g); // > - if (f(l) < g(l)) r = m, i = 2*i; // > - else l = m, i = 2*i+1; - }} - void insert(Fun f) {_insert(f, 0, cap, 1);} +struct Lichao { + static constexpr Fun id = {0, inf}; // {0, -inf} + int n, cap; + vector<Fun> seg; + Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {} + + void _insert(Fun f, int l, int r, int i) { + while (i < 2*cap){ + int m = (l+r)/2; + if (m >= n) {r = m; i = 2*i; continue;} + Fun &g = seg[i]; + if (f(m) < g(m)) swap(f, g); // > + if (f(l) < g(l)) r = m, i = 2*i; // > + else l = m, i = 2*i+1; + }} + void insert(Fun f) {_insert(f, 0, cap, 1);} - void _segmentInsert(Fun f, int l, int r, int a, int b, int i) { - if (l <= a && b <= r) _insert(f, a, b, i); - else if (a < r && l < b){ - int m = (a+b)/2; - _segmentInsert(f, l, r, a, m, 2*i); - _segmentInsert(f, l, r, m, b, 2*i+1); - }} - void segmentInsert(Fun f, ll l, ll r) { - _segmentInsert(f, findX(l), findX(r), 0, cap, 1); - } + void _segmentInsert(Fun f, int l, int r, int a, int b, int i) { + if (l <= a && b <= r) _insert(f, a, b, i); + else if (a < r && l < b){ + int m = (a+b)/2; + _segmentInsert(f, l, r, a, m, 2*i); + _segmentInsert(f, l, r, m, b, 2*i+1); + }} + void segmentInsert(Fun f, ll l, ll r) { + _segmentInsert(f, findX(l), findX(r), 0, cap, 1); + } - ll _query(int x) { - ll ans = inf; // -inf - for (int i = x + cap; i > 0; i /= 2) ans = min(ans, seg[i](x)); // max - return ans; - } - ll query(ll x) {return _query(findX(x));} + ll _query(int x) { + ll ans = inf; // -inf + for (int i = x + cap; i > 0; i /= 2) { + ans = min(ans, seg[i](x)); // max + } + return ans; + } + ll query(ll x) {return _query(findX(x));} }; diff --git a/datastructures/pbds.cpp b/datastructures/pbds.cpp new file mode 100644 index 0000000..c2b44cc --- /dev/null +++ b/datastructures/pbds.cpp @@ -0,0 +1,18 @@ +#include <ext/pb_ds/assoc_container.hpp> +using namespace __gnu_pbds; +template<typename T> +using Tree = tree<T, null_type, less<T>, rb_tree_tag, + tree_order_statistics_node_update>; +// T.order_of_key(x): number of elements strictly less than x +// *T.find_by_order(k): k-th element + +template<typename T> +struct chash { + const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd + size_t operator()(T o) const { + return __builtin_bswap64(hash<T>()(o) * C); +}}; +template<typename K, typename V> +using hashMap = gp_hash_table<K, V, chash<K>>; +template<typename T> +using hashSet = gp_hash_table<T, null_type, chash<T>>; diff --git a/datastructures/stlPriorityQueue.cpp b/datastructures/stlPriorityQueue.cpp new file mode 100644 index 0000000..32b2455 --- /dev/null +++ b/datastructures/stlPriorityQueue.cpp @@ -0,0 +1,8 @@ +#include <ext/pb_ds/priority_queue.hpp> +template<typename T> +using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>> + +auto it = pq.push(5); +pq.modify(it, 6); +pq.join(pq2); +// push, join are O(1), pop, modify, erase O(log n) amortized diff --git a/geometry/geometry.tex b/geometry/geometry.tex index d3e1671..d753ed6 100644 --- a/geometry/geometry.tex +++ b/geometry/geometry.tex @@ -7,6 +7,14 @@ \sourcecode{geometry/closestPair.cpp} \end{algorithm} +\begin{algorithm}{Rotating calipers} + \begin{methods} + \method{antipodalPoints}{berechnet antipodale Punkte}{n} + \end{methods} + \textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn sortiert sein und konvexes Polygon bilden! + \sourcecode{geometry/antipodalPoints.cpp} +\end{algorithm} + \begin{algorithm}{Konvexehülle} \begin{methods} \method{convexHull}{berechnet Konvexehülle}{n\*\log(n)} @@ -19,15 +27,6 @@ \sourcecode{geometry/convexHull.cpp} \end{algorithm} -\columnbreak -\begin{algorithm}{Rotating calipers} - \begin{methods} - \method{antipodalPoints}{berechnet antipodale Punkte}{n} - \end{methods} - \textbf{WICHTIG:} Punkte müssen gegen den Uhrzeigersinn sortiert sein und konvexes Polygon bilden! - \sourcecode{geometry/antipodalPoints.cpp} -\end{algorithm} - \subsection{Formeln~~--~\texttt{std::complex}} \sourcecode{geometry/formulars.cpp} \sourcecode{geometry/linesAndSegments.cpp} diff --git a/graph/2sat.cpp b/graph/2sat.cpp index 8fb3d39..75e54e6 100644 --- a/graph/2sat.cpp +++ b/graph/2sat.cpp @@ -2,7 +2,7 @@ struct sat2 { int n; // + scc variablen vector<int> sol; - sat2(int vars) : n(vars*2), adj(vars*2) {}; + sat2(int vars) : n(vars*2), adj(n) {} static int var(int i) {return i << 1;} // use this! @@ -18,20 +18,14 @@ struct sat2 { void addAnd(int a, int b) {addTrue(a); addTrue(b);} void addNand(int a, int b) {addOr(1^a, 1^b);} - bool solvable() { + bool solve() { scc(); //scc code von oben + sol.assign(n, -1); for (int i = 0; i < n; i += 2) { if (idx[i] == idx[i + 1]) return false; + sol[i] = idx[i] < idx[i + 1]; + sol[i + 1] = !sol[i]; } return true; } - - void assign() { - sol.assign(n, -1); - for (int i = 0; i < sccCounter; i++) { - if (sol[sccs[i][0]] == -1) { - for (int v : sccs[i]) { - sol[v] = 1; - sol[1^v] = 0; - }}}} }; diff --git a/graph/graph.tex b/graph/graph.tex index 6fbdb74..060d157 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,18 +1,31 @@ \section{Graphen} -\begin{algorithm}{Eulertouren} +\begin{algorithm}{Kruskal} + \begin{methods}[ll] + berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ + \end{methods} + \sourcecode{graph/kruskal.cpp} +\end{algorithm} + +\begin{algorithm}{Minimale Spannbäume} + \paragraph{Schnitteigenschaft} + Für jeden Schnitt $C$ im Graphen gilt: + Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. + ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) + + \paragraph{Kreiseigenschaft} + Für jeden Kreis $K$ im Graphen gilt: + Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. +\end{algorithm} + +\begin{algorithm}{Heavy-Light Decomposition} \begin{methods} - \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}} + \method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})} \end{methods} - \sourcecode{graph/euler.cpp} - \begin{itemize} - \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). - \item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). - \item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.} - \item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adj} leichter - \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert. - Die Existenz muss separat geprüft werden. - \end{itemize} + \textbf{Wichtig:} Intervalle sind halboffen + + Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. + \sourcecode{graph/hld.cpp} \end{algorithm} \begin{algorithm}{Lowest Common Ancestor} @@ -31,16 +44,20 @@ \sourcecode{graph/centroid.cpp} \end{algorithm} -\begin{algorithm}{Heavy-Light Decomposition} +\begin{algorithm}{Eulertouren} \begin{methods} - \method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})} + \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}} \end{methods} - \textbf{Wichtig:} Intervalle sind halboffen - - Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. - \sourcecode{graph/hld.cpp} + \sourcecode{graph/euler.cpp} + \begin{itemize} + \item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet). + \item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten). + \item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.} + \item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adj} leichter + \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert. + Die Existenz muss separat geprüft werden. + \end{itemize} \end{algorithm} -\clearpage \begin{algorithm}{Baum-Isomorphie} \begin{methods} @@ -49,24 +66,6 @@ \sourcecode{graph/treeIsomorphism.cpp} \end{algorithm} -\begin{algorithm}{Minimale Spannbäume} - \paragraph{Schnitteigenschaft} - Für jeden Schnitt $C$ im Graphen gilt: - Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. - ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) - - \paragraph{Kreiseigenschaft} - Für jeden Kreis $K$ im Graphen gilt: - Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. -\end{algorithm} - -\begin{algorithm}{Kruskal} - \begin{methods}[ll] - berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ - \end{methods} - \sourcecode{graph/kruskal.cpp} -\end{algorithm} - \subsection{Kürzeste Wege} \subsubsection{\textsc{Bellmann-Ford}-Algorithmus} @@ -91,6 +90,14 @@ 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}{Dynamic Connectivity} + \begin{methods} + \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} + \method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)} + \method{eraseEdge}{entfernt Kante \code{id}}{\log(n)} + \end{methods} + \sourcecode{graph/connect.cpp} +\end{algorithm} \begin{algorithm}{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)$ @@ -100,13 +107,11 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/havelHakimi.cpp} \end{algorithm} -\begin{algorithm}{Dynamic Connectivity} +\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} \begin{methods} - \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} - \method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)} - \method{eraseEdge}{entfernt Kante \code{id}}{\log(n)} + \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} \end{methods} - \sourcecode{graph/connect.cpp} + \sourcecode{graph/scc.cpp} \end{algorithm} \begin{algorithm}{DFS} @@ -121,13 +126,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/articulationPoints.cpp} \end{algorithm} -\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} - \begin{methods} - \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} - \end{methods} - \sourcecode{graph/scc.cpp} -\end{algorithm} - \begin{algorithm}{2-SAT} \sourcecode{graph/2sat.cpp} \end{algorithm} @@ -139,7 +137,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/bronKerbosch.cpp} \end{algorithm} -\clearpage \begin{algorithm}{Cycle Counting} \begin{methods} @@ -164,6 +161,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/blossom.cpp} \end{algorithm} +\begin{algorithm}{Rerooting Template} + \sourcecode{graph/reroot.cpp} +\end{algorithm} + +\begin{algorithm}{Virtual Trees} + \sourcecode{graph/virtualTree.cpp} +\end{algorithm} + \begin{algorithm}{Maximal Cardinatlity Bipartite Matching} \label{kuhn} \begin{methods} @@ -179,13 +184,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/hopcroftKarp.cpp} \end{algorithm} -\begin{algorithm}{Maximum Weight Bipartite Matching} - \begin{methods} - \method{match}{berechnet Matching}{\abs{V}^3} - \end{methods} - \sourcecode{graph/maxWeightBipartiteMatching.cpp} -\end{algorithm} - \begin{algorithm}{Global Mincut} \begin{methods} \method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}\abs{E}+\abs{V}^2\*\log(\abs{E})} @@ -205,12 +203,21 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/capacityScaling.cpp} } +\optional{ \subsubsection{Push Relabel} \begin{methods} \method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}} \method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1} \end{methods} -\sourcecode{graph/pushRelabel2.cpp} +\sourcecode{graph/pushRelabel.cpp} +} + +\begin{algorithm}{Min-Cost-Max-Flow} + \begin{methods} + \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} + \end{methods} + \sourcecode{graph/minCostMaxFlow.cpp} +\end{algorithm} \subsubsection{Dinic's Algorithm mit Capacity Scaling} \begin{methods} @@ -218,6 +225,8 @@ 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* +\columnbreak \optional{ \subsubsection{Anwendungen} @@ -241,12 +250,15 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{itemize} } -\begin{algorithm}{Min-Cost-Max-Flow} +\begin{algorithm}{Maximum Weight Bipartite Matching} \begin{methods} - \method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2} + \method{match}{berechnet Matching}{\abs{V}^3} \end{methods} - \sourcecode{graph/minCostMaxFlow.cpp} + \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} +\vfill* +\columnbreak + \begin{algorithm}[optional]{TSP} \begin{methods} @@ -261,3 +273,4 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/bitonicTSPsimple.cpp} \end{algorithm} + diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp index 6246fe0..cbd6991 100644 --- a/graph/havelHakimi.cpp +++ b/graph/havelHakimi.cpp @@ -1,6 +1,8 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) { priority_queue<pair<int, int>> pq; - for (int i = 0; i < sz(deg); i++) pq.push({deg[i], i}); + for (int i = 0; i < sz(deg); i++) { + if (deg[i] > 0) pq.push({deg[i], i}); + } vector<vector<int>> adj; while (!pq.empty()) { auto [degV, v] = pq.top(); pq.pop(); diff --git a/graph/maxWeightBipartiteMatching.cpp b/graph/maxWeightBipartiteMatching.cpp index 5eda19b..a2b0a80 100644 --- a/graph/maxWeightBipartiteMatching.cpp +++ b/graph/maxWeightBipartiteMatching.cpp @@ -4,15 +4,14 @@ double costs[N_LEFT][N_RIGHT]; double match(int l, int r) { vector<double> lx(l), ly(r); //xy is matching from l->r, yx from r->l, or -1 - vector<int> xy(l, -1), yx(r, -1), augmenting(r); - vector<bool> s(l); + vector<int> xy(l, -1), yx(r, -1); vector<pair<double, int>> slack(r); for (int x = 0; x < l; x++) lx[x] = *max_element(costs[x], costs[x] + r); for (int root = 0; root < l; root++) { - augmenting.assign(r, -1); - s.assign(l, false); + vector<int> aug(r, -1); + vector<bool> s(l); s[root] = true; for (int y = 0; y < r; y++) { slack[y] = {lx[root] + ly[y] - costs[root][y], root}; @@ -22,38 +21,30 @@ double match(int l, int r) { double delta = INF; int x = -1; for (int yy = 0; yy < r; yy++) { - if (augmenting[yy] < 0) { - if (slack[yy].first < delta) { - delta = slack[yy].first; - x = slack[yy].second; - y = yy; - }}} + if (aug[yy] < 0 && slack[yy].first < delta) { + tie(delta, x) = slack[yy]; + y = yy; + }} if (delta > 0) { for (int x = 0; x < l; x++) if (s[x]) lx[x] -= delta; for (int y = 0; y < r; y++) { - if (augmenting[y] >= 0) ly[y] += delta; + if (aug[y] >= 0) ly[y] += delta; else slack[y].first -= delta; }} - augmenting[y] = x; + aug[y] = x; x = yx[y]; - if (x == -1) break; + if (x < 0) break; s[x] = true; for (int y = 0; y < r; y++) { - if (augmenting[y] < 0) { + if (aug[y] < 0) { double alt = lx[x] + ly[y] - costs[x][y]; if (slack[y].first > alt) { slack[y] = {alt, x}; }}}} while (y >= 0) { - // Jede Iteration vergrößert Matching um 1 - // (können 0-Kanten sein!) - int x = augmenting[y]; - int prec = xy[x]; - yx[y] = x; - xy[x] = y; - y = prec; + yx[y] = aug[y]; + swap(y, xy[aug[y]]); }} - // Wert des Matchings return accumulate(all(lx), 0.0) + - accumulate(all(ly), 0.0); + accumulate(all(ly), 0.0); // Wert des Matchings } diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp index 3526b17..14a222c 100644 --- a/graph/minCostMaxFlow.cpp +++ b/graph/minCostMaxFlow.cpp @@ -8,7 +8,6 @@ struct MinCostFlow { vector<vector<int>> adj; vector<int> pref, con; vector<ll> dist; - const int s, t; ll maxflow, mincost; @@ -27,12 +26,10 @@ struct MinCostFlow { dist.assign(sz(adj), INF); vector<bool> inqueue(sz(adj)); queue<int> queue; - dist[s] = 0; queue.push(s); pref[s] = s; inqueue[s] = true; - while (!queue.empty()) { int cur = queue.front(); queue.pop(); inqueue[cur] = false; diff --git a/graph/pushRelabel.cpp b/graph/pushRelabel.cpp index 52ba8b1..904aec6 100644 --- a/graph/pushRelabel.cpp +++ b/graph/pushRelabel.cpp @@ -1,109 +1,64 @@ -constexpr ll inf = 1ll<<60; - struct Edge { - int from, to; + int to, rev; ll f, c; }; -vector<Edge> edges; -vector<vector<int>> adj, llist; -vector<int> height, ccount, que; -vector<ll> excess; -vector<list<int>> dlist; -vector<list<int>::iterator> iter; -int highest, highestActive; - -void addEdge(int from, int to, ll c) { - adj[from].push_back(sz(edges)); - edges.push_back({from, to, 0, c}); - adj[to].push_back(sz(edges)); - edges.push_back({to, from, 0, 0}); -} +vector<vector<Edge>> adj; +vector<vector<int>> hs; +vector<ll> ec; +vector<int> cur, H; -void globalRelabel(int n, int t) { - height.assign(n, n); - height[t] = 0; - ccount.assign(n, 0); - que.assign(n+1, 0); - int qh = 0, qt = 0; - for (que[qt++] = t; qh < qt;) { - int v = que[qh++], h = height[v] + 1; - for (int id : adj[v]) { - if (height[edges[id].to] == n && edges[id ^ 1].c - edges[id ^ 1].f > 0) { - ccount[height[edges[id].to] = h]++; - que[qt++] = edges[id].to; - }}} - llist.assign(n+1, {}); - dlist.assign(n+1, {}); - for (int v = 0; v < n; v++) { - if (height[v] < n) { - iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v); - if (excess[v] > 0) llist[height[v]].push_back(v); - }} - highest = highestActive = height[que[qt - 1]]; +void addEdge(int u, int v, ll c) { + adj[u].push_back({v, (int)sz(adj[v]), 0, c}); + adj[v].push_back({u, (int)sz(adj[u])-1, 0, 0}); } -void push(int v, int id) { - int u = edges[id].to; - ll df = min(excess[v], edges[id].c - edges[id].f); - edges[id].f += df; - edges[id^1].f -= df; - excess[v] -= df; - excess[u] += df; - if (0 < excess[u] && excess[u] <= df) llist[height[u]].push_back(u); +void addFlow(Edge& e, ll f) { + if (ec[e.to] == 0 && f > 0) + hs[H[e.to]].push_back(e.to); + e.f += f; + adj[e.to][e.rev].f -= f; + ec[e.to] += f; + ec[adj[e.to][e.rev].to] -= f; } -void discharge(int n, int v) { - int nh = n; - for (int id : adj[v]) { - if (edges[id].c - edges[id].f > 0) { - if (height[v] == height[edges[id].to] + 1) { - push(v, id); - if (!excess[v]) return; - } else { - nh = min(nh, height[edges[id].to] + 1); - }}} - int h = height[v]; - if (ccount[h] == 1) { - for (int i = h; i <= highest; i++) { - for (auto p : dlist[i]) --ccount[height[p]], height[p] = n; - dlist[i].clear(); - } - highest = h - 1; - } else { - --ccount[h], iter[v] = dlist[h].erase(iter[v]), height[v] = nh; - if (nh == n) return; - ++ccount[nh], iter[v] = dlist[nh].insert(dlist[nh].begin(), v); - highest = max(highest, highestActive = nh); - llist[nh].push_back(v); -}} - ll maxFlow(int s, int t) { int n = sz(adj); - llist.assign(n + 1, {}); - dlist.assign(n + 1, {}); - highestActive = highest = 0; - height.assign(n, 0); - height[s] = n; - iter.resize(n); - for (int v = 0; v < n; v++) { - if (v != s) iter[v] = dlist[height[v]].insert(dlist[height[v]].begin(), v); - } - ccount.assign(n, 0); - ccount[0] = n-1; - excess.assign(n, 0); - excess[s] = inf; - excess[t] = -inf; - for (int id : adj[s]) push(s, id); - globalRelabel(n, t); - while (highestActive >= 0) { - if (llist[highestActive].empty()) { - highestActive--; - continue; - } - int v = llist[highestActive].back(); - llist[highestActive].pop_back(); - discharge(n, v); - } - return excess[t] + inf; -} + hs.assign(2*n, {}); + ec.assign(n, 0); + cur.assign(n, 0); + H.assign(n, 0); + H[s] = n; + ec[t] = 1;//never set t to active... + vector<int> co(2*n); + co[0] = n - 1; + for (Edge& e : adj[s]) addFlow(e, e.c); + for (int hi = 0;;) { + while (hs[hi].empty()) if (!hi--) return -ec[s]; + int v = hs[hi].back(); + hs[hi].pop_back(); + while (ec[v] > 0) { + if (cur[v] == sz(adj[v])) { + H[v] = 2*n; + for (int i = 0; i < sz(adj[v]); i++) { + Edge& e = adj[v][i]; + if (e.c - e.f > 0 && + H[v] > H[e.to] + 1) { + H[v] = H[e.to] + 1; + cur[v] = i; + }} + co[H[v]]++; + if (!--co[hi] && hi < n) { + for (int i = 0; i < n; i++) { + if (hi < H[i] && H[i] < n) { + co[H[i]]--; + H[i] = n + 1; + }}} + hi = H[v]; + } else { + Edge& e = adj[v][cur[v]]; + if (e.c - e.f > 0 && H[v] == H[e.to] + 1) { + addFlow(adj[v][cur[v]], min(ec[v], e.c - e.f)); + } else { + cur[v]++; +}}}}} diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp deleted file mode 100644 index 7d7defd..0000000 --- a/graph/pushRelabel2.cpp +++ /dev/null @@ -1,66 +0,0 @@ -struct Edge { - int from, to; - ll f, c; -}; - -vector<Edge> edges; -vector<vector<int>> adj, hs; -vector<ll> ec; -vector<int> cur, H; - -void addEdge(int from, int to, ll c) { - adj[from].push_back(sz(edges)); - edges.push_back({from, to, 0, c}); - adj[to].push_back(sz(edges)); - edges.push_back({to, from, 0, 0}); -} - -void addFlow(int id, ll f) { - if (ec[edges[id].to] == 0 && f > 0) - hs[H[edges[id].to]].push_back(edges[id].to); - edges[id].f += f; - edges[id^1].f -= f; - ec[edges[id].to] += f; - ec[edges[id].from] -= f; -} - -ll maxFlow(int s, int t) { - int n = sz(adj); - hs.assign(2*n, {}); - ec.assign(n, 0); - cur.assign(n, 0); - H.assign(n, 0); - H[s] = n; - ec[t] = 1;//never set t to active... - vector<int> co(2*n); - co[0] = n - 1; - for (int id : adj[s]) addFlow(id, edges[id].c); - for (int hi = 0;;) { - while (hs[hi].empty()) if (!hi--) return -ec[s]; - int v = hs[hi].back(); - hs[hi].pop_back(); - while (ec[v] > 0) { - if (cur[v] == sz(adj[v])) { - H[v] = 2*n; - for (int i = 0; i < sz(adj[v]); i++) { - int id = adj[v][i]; - if (edges[id].c - edges[id].f > 0 && - H[v] > H[edges[id].to] + 1) { - H[v] = H[edges[id].to] + 1; - cur[v] = i; - }} - co[H[v]]++; - if (!--co[hi] && hi < n) { - for (int i = 0; i < n; i++) { - if (hi < H[i] && H[i] < n) { - co[H[i]]--; - H[i] = n + 1; - }}} - hi = H[v]; - } else { - auto e = edges[adj[v][cur[v]]]; - if (e.c - e.f > 0 && H[v] == H[e.to] + 1) { - addFlow(adj[v][cur[v]], min(ec[v], e.c - e.f)); - } else { - cur[v]++; -}}}}} diff --git a/graph/reroot.cpp b/graph/reroot.cpp new file mode 100644 index 0000000..4c6a748 --- /dev/null +++ b/graph/reroot.cpp @@ -0,0 +1,62 @@ +// Usual Tree DP can be broken down in 4 steps: +// - Initialize dp[v] = identity +// - Iterate over all children w and take a value for w +// by looking at dp[w] and possibly the edge label of v -> w +// - combine the values of those children +// usually this operation should be commutative and associative +// - finalize the dp[v] after iterating over all children +struct Reroot { + using T = ll; + + // identity element + T E() {} + // x: dp value of child + // e: index of edge going to child + T takeChild(T x, int e) {} + T comb(T x, T y) {} + // called after combining all dp values of children + T fin(T x, int v) {} + + vector<vector<pair<int, int>>> g; + vector<int> ord, pae; + vector<T> dp; + + T dfs(int v) { + ord.push_back(v); + for (auto [w, e] : g[v]) { + g[w].erase(find(all(g[w]), pair(v, e^1))); + pae[w] = e^1; + dp[v] = comb(dp[v], takeChild(dfs(w), e)); + } + return dp[v] = fin(dp[v], v); + } + + vector<T> solve(int n, vector<pair<int, int>> edges) { + g.resize(n); + for (int i = 0; i < n-1; i++) { + g[edges[i].first].emplace_back(edges[i].second, 2*i); + g[edges[i].second].emplace_back(edges[i].first, 2*i+1); + } + pae.assign(n, -1); + dp.assign(n, E()); + dfs(0); + vector<T> updp(n, E()), res(n, E()); + for (int v : ord) { + vector<T> pref(sz(g[v])+1), suff(sz(g[v])+1); + if (v != 0) pref[0] = takeChild(updp[v], pae[v]); + for (int i = 0; i < sz(g[v]); i++){ + auto [u, w] = g[v][i]; + pref[i+1] = suff[i] = takeChild(dp[u], w); + pref[i+1] = comb(pref[i], pref[i+1]); + } + for (int i = sz(g[v])-1; i >= 0; i--) { + suff[i] = comb(suff[i], suff[i+1]); + } + for (int i = 0; i < sz(g[v]); i++) { + updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); + } + res[v] = fin(pref.back(), v); + } + return res; + } +}; diff --git a/graph/scc.cpp b/graph/scc.cpp index 1716add..ac9a40b 100644 --- a/graph/scc.cpp +++ b/graph/scc.cpp @@ -1,8 +1,7 @@ vector<vector<int>> adj, sccs; -int counter, sccCounter; +int counter; vector<bool> inStack; -// idx enthält den Index der SCC pro Knoten. -vector<int> low, idx, s; +vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { int old = low[v] = counter++; @@ -15,14 +14,11 @@ void visit(int v) { if (old == low[v]) { sccs.push_back({}); - int u; - do { + for (int u = -1; u != v;) { u = s.back(); s.pop_back(); inStack[u] = false; - idx[u] = sccCounter; - sccs[sccCounter].push_back(u); - } while (u != v); - sccCounter++; -}} + idx[u] = sz(sccs) - 1; + sccs.back().push_back(u); +}}} void scc() { inStack.assign(sz(adj), false); @@ -30,7 +26,7 @@ void scc() { idx.assign(sz(adj), -1); sccs.clear(); - counter = sccCounter = 0; + counter = 0; for (int i = 0; i < sz(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/graph/virtualTree.cpp b/graph/virtualTree.cpp new file mode 100644 index 0000000..2fcea80 --- /dev/null +++ b/graph/virtualTree.cpp @@ -0,0 +1,22 @@ +// needs dfs in- and out- time and lca function +vector<int> in, out; + +void virtualTree(vector<int> ind) { // indices of used nodes + sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); + for (int i=0; i<sz(a)-1; i++) { + ind.push_back(lca(ind[i], ind[i+1])); + } + sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); + ind.erase(unique(all(ind)), ind.end()); + + int n = ind.size(); + vector<vector<int>> tree(n); + vector<int> st = {0}; + for (int i=1; i<n; i++) { + while (in[ind[i]] >= out[ind[st.back()]]) st.pop_back(); + tree[st.back()].push_back(i); + st.push(i); + } + // virtual directed tree with n nodes, original indices in ind + // weights can be calculated, e.g. with binary lifting +} diff --git a/math/binomial0.cpp b/math/binomial0.cpp index d9af917..896a0f1 100644 --- a/math/binomial0.cpp +++ b/math/binomial0.cpp @@ -10,5 +10,5 @@ void precalc() { ll calc_binom(ll n, ll k) { if (n < 0 || n < k || k < 0) return 0; - return (fac[n] * fac[n-k] % mod) * fac[k] % mod; + return (inv[n] * inv[n-k] % mod) * fac[k] % mod; } diff --git a/math/binomial1.cpp b/math/binomial1.cpp index 02b27e3..dab20b3 100644 --- a/math/binomial1.cpp +++ b/math/binomial1.cpp @@ -2,8 +2,7 @@ ll calc_binom(ll n, ll k) { if (k > n) return 0; ll r = 1; for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit - r *= n--; - r /= d; + r *= n--, r /= d; } return r; } diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index 623f94b..ccbc5dc 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,35 +1,14 @@ -// Laufzeit: O(n * log(n)), n := Anzahl der Kongruenzen. Nur für -// teilerfremde Moduli. Berechnet das kleinste, nicht negative x, -// das alle Kongruenzen simultan löst. Alle Lösungen sind -// kongruent zum kgV der Moduli (Produkt, da teilerfremd). -struct ChineseRemainder { +struct CRT { using lll = __int128; - vector<lll> lhs, rhs, mods, inv; - lll M; // Produkt über die Moduli. Kann leicht überlaufen. + lll M = 1, sol = 0; // Solution unique modulo M + bool hasSol = true; - ll g(const vector<lll> &vec) { - lll res = 0; - for (int i = 0; i < sz(vec); i++) { - res += (vec[i] * inv[i]) % M; - res %= M; - } - return res; - } - - // Fügt Kongruenz l * x = r (mod m) hinzu. - void addEquation(ll l, ll r, ll m) { - lhs.push_back(l); - rhs.push_back(r); - mods.push_back(m); - } - - ll solve() { // Löst das System. - M = accumulate(all(mods), lll(1), multiplies<lll>()); - inv.resize(sz(lhs)); - for (int i = 0; i < sz(lhs); i++) { - lll x = (M / mods[i]) % mods[i]; - inv[i] = (multInv(x, mods[i]) * (M / mods[i])); - } - return (multInv(g(lhs), M) * g(rhs)) % M; + // Adds congruence x = a (mod m) + void add(ll a, ll m) { + auto [d, s, t] = extendedEuclid(M, m); + if((a - sol) % d != 0) hasSol = false; + lll z = M/d * s; + M *= m/d; + sol = (z % M * (a-sol) % M + sol + M) % M; } }; diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp index d016a63..ecf4a16 100644 --- a/math/extendedEuclid.cpp +++ b/math/extendedEuclid.cpp @@ -1,7 +1,6 @@ // a*x + b*y = ggt(a, b) -ll extendedEuclid(ll a, ll b, ll& x, ll& y) { - if (a == 0) {x = 0; y = 1; return b;} - ll x1, y1, d = extendedEuclid(b % a, a, x1, y1); - x = y1 - (b / a) * x1; y = x1; - return d; +array<ll, 3> extendedEuclid(ll a, ll b) { + if (a == 0) return {b, 0, 1}; + auto [d, x, y] = extendedEuclid(b % a, a); + return {d, y - (b / a) * x, x}; } diff --git a/math/math.tex b/math/math.tex index 8ccc55e..f9a5ea5 100644 --- a/math/math.tex +++ b/math/math.tex @@ -1,5 +1,12 @@ \section{Mathe}
+\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}{Longest Increasing Subsequence}
\begin{itemize}
\item \code{lower\_bound} $\Rightarrow$ streng monoton
@@ -7,14 +14,6 @@ \end{itemize}
\sourcecode{math/longestIncreasingSubsequence.cpp}
\end{algorithm}
-\columnbreak
-
-\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}
@@ -44,21 +43,20 @@ \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$
+\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$}
+\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$
-\textbf{Falls $\boldsymbol{\ggT(n, p) = 1}$:}
+\textbf{Falls $\boldsymbol{\ggT(x, m) = 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$
+ $\alpha x + \beta m = 1$.
+ \item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$.
+ \item $x^{-1} :\equiv \alpha \bmod m$
\end{itemize}
-\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
+\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$.
% \sourcecode{math/multInv.cpp}
\sourcecode{math/shortModInv.cpp}
@@ -121,19 +119,12 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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}
+\begin{algorithm}{Numerisch Extremstelle bestimmen}
+ \sourcecode{math/goldenSectionSearch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}
+ \sourcecode{math/simpson.cpp}
\end{algorithm}
\begin{algorithm}{Diskreter Logarithmus}
@@ -151,6 +142,22 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/discreteNthRoot.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}{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$.
@@ -185,7 +192,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{itemize}
\end{algorithm}
-
\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
\begin{itemize}
\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
@@ -216,33 +222,25 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: %\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}
+\optional{
+\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}{Polynome, FFT, NTT \& andere Transformationen}
Multipliziert Polynome $A$ und $B$.
@@ -259,21 +257,53 @@ 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*
+ \columnbreak
\sourcecode{math/transforms/bitwiseTransforms.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}
+\begin{algorithm}{Operations on Formal Power Series}
+ \sourcecode{math/transforms/seriesOperations.cpp}
+\end{algorithm}
\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
\method{gauss}{löst LGS}{n^3}
\sourcecode{math/lgsFp.cpp}
-\clearpage
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/gauss.cpp}
+
+\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}
+\optional{
\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
\begin{methods}
\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}
@@ -281,6 +311,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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}
@@ -331,33 +362,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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}
@@ -405,20 +409,20 @@ 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}
\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}
+
+ \begin{methods}
\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
\end{methods}
\sourcecode{math/binomial1.cpp}
-
- \begin{methods}
+
+ \begin{methods}
\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
\end{methods}
\sourcecode{math/binomial3.cpp}
diff --git a/math/multInv.cpp b/math/multInv.cpp index 87603f3..647dc2d 100644 --- a/math/multInv.cpp +++ b/math/multInv.cpp @@ -1,5 +1,4 @@ -ll multInv(ll n, ll p) { - ll x, y; - extendedEuclid(n, p, x, y); // Implementierung von oben. - return ((x % p) + p) % p; +ll multInv(ll x, ll m) { + auto [d, a, b] = extendedEuclid(x, m); // Implementierung von oben. + return ((a % m) + m) % m; } diff --git a/math/rho.cpp b/math/rho.cpp index 635c630..7885196 100644 --- a/math/rho.cpp +++ b/math/rho.cpp @@ -1,8 +1,8 @@ using lll = __int128; ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. if (n % 2 == 0) return 2; - ll x = 0, y = 0, prd = 2; - auto f = [n](lll x){return (x * x) % n + 1;}; + ll x = 0, y = 0, prd = 2, i = n/2 + 7; + auto f = [&](lll x){return (x * x + i) % n;}; for (ll t = 30, i = n/2 + 7; t % 40 || gcd(prd, n) == 1; t++) { if (x == y) x = ++i, y = f(x); if (ll q = (lll)prd * abs(x-y) % n; q) prd = q; diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp index 747eb7a..244bacf 100644 --- a/math/shortModInv.cpp +++ b/math/shortModInv.cpp @@ -1,3 +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 +ll multInv(ll x, ll m) { // x^{-1} mod m + return 1 < x ? m - inv(m % x, x) * m / x : 1; +} diff --git a/math/tables/composite.tex b/math/tables/composite.tex index b8f5428..8e14b2e 100644 --- a/math/tables/composite.tex +++ b/math/tables/composite.tex @@ -1,26 +1,27 @@ -\begin{tabularx}{\linewidth}{|r||r|r||r|} + +\begin{tabularx}{\linewidth}{|r||r|r||r|r|r||C|} \hline - \multicolumn{4}{|c|}{Important Numbers} \\ + \multicolumn{7}{|c|}{Important Numbers} \\ \hline - $10^x$ & Highly Composite & Divs & Prime \\ + $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & \\ \hline - $1$ & $6$ & $4$ & $10^{1}-~~3$ \\ - $2$ & $60$ & $12$ & $10^{2}-~~3$ \\ - $3$ & $840$ & $32$ & $10^{3}-~~3$ \\ - $4$ & $7~560$ & $64$ & $10^{4}- 27$ \\ - $5$ & $83~160$ & $128$ & $10^{5}-~~9$ \\ - $6$ & $720~720$ & $240$ & $10^{6}- 17$ \\ - $7$ & $8~648~640$ & $448$ & $10^{7}-~~9$ \\ - $8$ & $73~513~440$ & $768$ & $10^{8}- 11$ \\ - $9$ & $735~134~400$ & $1~344$ & $10^{9}- 63$ \\ - $10$ & $6~983~776~800$ & $2~304$ & $10^{10}- 33$ \\ - $11$ & $97~772~875~200$ & $4~032$ & $10^{11}- 23$ \\ - $12$ & $963~761~198~400$ & $6~720$ & $10^{12}- 11$ \\ - $13$ & $9~316~358~251~200$ & $10~752$ & $10^{13}- 29$ \\ - $14$ & $97~821~761~637~600$ & $17~280$ & $10^{14}- 27$ \\ - $15$ & $866~421~317~361~600$ & $26~880$ & $10^{15}- 11$ \\ - $16$ & $8~086~598~962~041~600$ & $41~472$ & $10^{16}- 63$ \\ - $17$ & $74~801~040~398~884~800$ & $64~512$ & $10^{17}-~~3$ \\ - $18$ & $897~612~484~786~617~600$ & $103~680$ & $10^{18}- 11$ \\ + 1 & 6 & 4 & $-3$ & $+1$ & 4 & \\ + 2 & 60 & 12 & $-3$ & $+1$ & 25 & \\ + 3 & 840 & 32 & $-3$ & $+9$ & 168 & \\ + 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & \\ + 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & \\ + 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & \\ + 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & \\ + 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & \\ + 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & \\ + 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & \\ + 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & \\ + 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & \\ + 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & \\ + 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & \\ + 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & \\ + 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & \\ + 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & \\ \hline \end{tabularx} diff --git a/math/transforms/seriesOperations.cpp b/math/transforms/seriesOperations.cpp new file mode 100644 index 0000000..4743674 --- /dev/null +++ b/math/transforms/seriesOperations.cpp @@ -0,0 +1,56 @@ +vector<ll> poly_inv(const vector<ll>& a, int n) { + vector<ll> q = {powMod(a[0], mod-2, mod)}; + for (int len = 1; len < n; len *= 2){ + vector<ll> a2 = a, q2 = q; + a2.resize(2*len), q2.resize(2*len); + ntt(q2); + for (int j : {0, 1}) { + ntt(a2); + for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; + ntt(a2, true); + for (int i = 0; i < len; i++) a2[i] = 0; + } + for (int i = len; i < min(n, 2*len); i++) { + q.push_back((mod - a2[i]) % mod); + }} + return q; +} + +vector<ll> poly_deriv(vector<ll> a) { + for (int i = 1; i < sz(a); i++) + a[i-1] = a[i] * i % mod; + a.pop_back(); + return a; +} + +vector<ll> poly_integr(vector<ll> a) { + if (a.empty()) return {0}; + a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); + for (int i = sz(a)-2; i > 0; i--) + a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; + a[0] = 0; + return a; +} + +vector<ll> poly_log(vector<ll> a, int n) { + a = mul(poly_deriv(a), poly_inv(a, n)); + a.resize(n-1); + a = poly_integr(a); + return a; +} + +vector<ll> poly_exp(vector<ll> a, int n) { + vector<ll> q = {1}; + for (int len = 1; len < n; len *= 2) { + vector<ll> p = poly_log(q, 2*len); + for (int i = 0; i < 2*len; i++) + p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; + vector<ll> q2 = q; + q2.resize(2*len); + ntt(p), ntt(q2); + for (int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; + ntt(p, true); + for (int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); + } + return q; +} diff --git a/other/stuff.cpp b/other/stuff.cpp index 38fde78..41543ad 100644 --- a/other/stuff.cpp +++ b/other/stuff.cpp @@ -6,8 +6,7 @@ setxkbmap de setxkbmap de,us -option grp:alt_space_toggle // Schnelle Ein-/Ausgabe mit cin/cout. -ios::sync_with_stdio(false); -cin.tie(nullptr); +cin.tie(nullptr)->ios::sync_with_stdio(false); // Set mit eigener Sortierfunktion. set<point2, decltype(comp)> set1(comp); diff --git a/string/ahoCorasick.cpp b/string/ahoCorasick.cpp index 9ffa6c9..eac312c 100644 --- a/string/ahoCorasick.cpp +++ b/string/ahoCorasick.cpp @@ -1,54 +1,52 @@ -constexpr ll ALPHABET_SIZE = 26; -constexpr char OFFSET = 'a'; +constexpr ll ALPHABET_SIZE = 26, OFFSET = 'a'; struct AhoCorasick { struct vert { - int suffix, exit, character, parent; - vector<int> nxt, patterns; - vert(int c, int p) : suffix(-1), exit(-1), - character(c), nxt(ALPHABET_SIZE, -1), parent(p) {} - }; - vector<vert> aho; + int suffix = 0, ch, cnt = 0; + array<int, ALPHABET_SIZE> nxt = {}; - AhoCorasick() {aho.push_back(vert(-1, 0));} + vert(int p, int c) : suffix(-p), ch(c) {} + }; + vector<vert> aho = {{0, -1}}; - // Call once for each pattern. - void addString(string &s, int patternIdx) { + int addString(string &s) { int v = 0; - for (char c : s) { + for (auto c : s) { int idx = c - OFFSET; - if (aho[v].nxt[idx] == -1) { + if (!aho[v].nxt[idx]) { aho[v].nxt[idx] = sz(aho); - aho.emplace_back(idx, v); + aho.emplace_back(v, idx); } v = aho[v].nxt[idx]; } - aho[v].patterns.push_back(patternIdx); + aho[v].cnt++; + return v; // trie node index of pattern (pattern state) } int getSuffix(int v) { - if (aho[v].suffix == -1) { - if (v == 0 || aho[v].parent == 0) aho[v].suffix = 0; - else aho[v].suffix = go(getSuffix(aho[v].parent), - aho[v].character); + if (aho[v].suffix < 0) { + aho[v].suffix = go(getSuffix(-aho[v].suffix), aho[v].ch); } return aho[v].suffix; } - int getExit(int v) { - if (aho[v].exit == -1) { - int suffix = getSuffix(v); - if (v == 0) aho[v].exit = 0; - else { - if (aho[suffix].patterns.empty()) { - aho[v].exit = getExit(suffix); - } else { - aho[v].exit = suffix; - }}} - return aho[v].exit; - } - - int go(int v, int idx) { // Root is v=0. - if (aho[v].nxt[idx] != -1) return aho[v].nxt[idx]; + int go(int v, int idx) { // Root is v=0, idx is char - OFFSET + if (aho[v].nxt[idx]) return aho[v].nxt[idx]; else return v == 0 ? 0 : go(getSuffix(v), idx); } + + vector<vector<int>> adj; + vector<ll> dp; + void buildGraph() { + adj.resize(sz(aho)); + dp.assign(sz(aho), 0); + for (int i = 1; i < sz(aho); i++) { + adj[getSuffix(i)].push_back(i); + }} + + void dfs(int v = 0) { // dp on tree + for (int u : adj[v]) { + //dp[u] = dp[v] + aho[u].cnt; // pattern count + dfs(u); + dp[v] += dp[u]; // no of matches + }} }; diff --git a/string/manacher.cpp b/string/manacher.cpp index 03c06e1..112bd55 100644 --- a/string/manacher.cpp +++ b/string/manacher.cpp @@ -1,27 +1,20 @@ -string a, b; //a needs to be set -vector<int> longest; +vector<int> manacher(const string& t) { + //transforms "aa" to ".a.a." to find even length palindromes + string s(sz(t) * 2 + 1, '.'); + for (int i = 0; i < sz(t); i++) s[2 * i + 1] = t[i]; -//transformes "aa" to ".a.a." to find even length palindromes -void init() { - b = string(sz(a) * 2 + 1, '.'); - longest.assign(sz(b), 0); - for (int i = 0; i < sz(a); i++) { - b[2 * i + 1] = a[i]; -}} - -void manacher() { - int center = 0, last = 0, n = sz(b); + int mid = 0, r = 0, n = sz(s); + vector<int> pal(n); for (int i = 1; i < n - 1; i++) { - int i2 = 2 * center - i; - longest[i] = (last > i) ? min(last - i, longest[i2]) : 0; - while (i + longest[i] + 1 < n && i - longest[i] - 1 >= 0 && - b[i + longest[i] + 1] == b[i - longest[i] - 1]) { - longest[i]++; + if (r > i) pal[i] = min(r - i, pal[2 * mid - i]); + while (pal[i] < min(i, n - i - 1) && + s[i + pal[i] + 1] == s[i - pal[i] - 1]) { + pal[i]++; } - if (i + longest[i] > last) { - center = i; - last = i + longest[i]; - }} - //convert lengths to string b (optional) - for (int i = 0; i < n; i++) longest[i] = 2 * longest[i] + 1; + if (i + pal[i] > r) mid = i, r = i + pal[i]; + } + + //convert lengths to constructed string s (optional) + //for (int i = 0; i < n; i++) pal[i] = 2 * pal[i] + 1; + return pal; } diff --git a/string/string.tex b/string/string.tex index c36ec69..393c2ad 100644 --- a/string/string.tex +++ b/string/string.tex @@ -47,18 +47,21 @@ \sourcecode{string/longestCommonSubsequence.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{\textsc{Aho-Corasick}-Automat} \begin{methods}[ll] - sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}+\abs{matches}} + sucht patterns im Text & \runtime{\abs{Text}+\sum\abs{pattern}} \end{methods} \begin{enumerate} - \item mit \code{addString(pattern, idx);} Patterns hinzufügen. + \item mit \code{addString(pattern, idx)} Patterns hinzufügen. + \item rufe \code{buildGraph()} auf \item mit \code{state = go(state, idx)} in nächsten Zustand wechseln. - \item mit \code{state = getExit(state)} den exit Kanten folgen bis \code{state == 0} - \item dabei mit \code{aho[state].patterns} die Matches zählen + \item erhöhe dabei \code{dp[state]++} + \item rufe \code{dfs()} auf. In dp[pattern state] stehen die Anzahl der Matches \end{enumerate} \sourcecode{string/ahoCorasick.cpp} \end{algorithm} +\clearpage \begin{algorithm}{Lyndon und De-Bruijn} \begin{itemize} Binary files differ@@ -3,7 +3,7 @@ \documentclass[a4paper,fontsize=7.8pt]{scrartcl} % General information. -\newcommand{\teamname}{Let's party!} +\newcommand{\teamname}{Kindergarten Timelimit} \newcommand{\university}{Karlsruhe Institute of Technology} % Options @@ -36,6 +36,7 @@ \tableofcontents \end{multicols*} } + \newpage % Content. |