summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--datastructures/datastructures.tex4
-rw-r--r--geometry/antipodalPoints.cpp9
-rw-r--r--geometry/geometry.tex18
-rw-r--r--geometry/linesAndSegments.cpp5
-rw-r--r--geometry/polygon.cpp8
-rw-r--r--geometry/triangle.cpp13
-rw-r--r--graph/2sat.cpp22
-rw-r--r--graph/articulationPoints.cpp2
-rw-r--r--graph/cycleCounting.cpp27
-rw-r--r--graph/euler.cpp11
-rw-r--r--graph/graph.tex110
-rw-r--r--math/chineseRemainder.cpp14
-rw-r--r--math/linearRecurence.cpp32
-rw-r--r--math/math.tex295
-rw-r--r--math/rho.cpp5
-rw-r--r--math/transforms/all.cpp6
-rw-r--r--tcr.pdfbin646184 -> 648178 bytes
17 files changed, 303 insertions, 278 deletions
diff --git a/datastructures/datastructures.tex b/datastructures/datastructures.tex
index 88bbd8c..9e954e7 100644
--- a/datastructures/datastructures.tex
+++ b/datastructures/datastructures.tex
@@ -2,7 +2,7 @@
\begin{algorithm}{Union-Find}
\begin{methods}
- \method{init}{legt n einzelne Unions an}{n}
+ \method{init}{legt $n$ einzelne Unions an}{n}
\method{findSet}{findet den Repräsentanten}{\log(n)}
\method{unionSets}{vereint 2 Mengen}{\log(n)}
\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
@@ -113,7 +113,7 @@
\begin{algorithm}{Link-Cut-Tree}
\begin{methods}
\method{Constructor}{baut Wald auf}{n}
- \method{connected}{prüft ob zwei Knoten im selben baum liegen}{\log(n)}
+ \method{connected}{prüft ob zwei Knoten im selben Baum liegen}{\log(n)}
\method{link}{fügt $\{x,y\}$ Kante ein}{\log(n)}
\method{cut}{entfernt $\{x,y\}$ Kante}{\log(n)}
\method{lca}{berechnet LCA von $x$ und $y$}{\log(n)}
diff --git a/geometry/antipodalPoints.cpp b/geometry/antipodalPoints.cpp
index 06efd6c..db39b39 100644
--- a/geometry/antipodalPoints.cpp
+++ b/geometry/antipodalPoints.cpp
@@ -1,13 +1,12 @@
vector<pair<int, int>> antipodalPoints(vector<pt>& h) {
+ if (sz(h) < 2) return {};
vector<pair<int, int>> result;
- int n = sz(h);
- if (n < 2) return result;
for (int i = 0, j = 1; i < j; i++) {
while (true) {
result.push_back({i, j});
- if (cross(h[(i + 1) % n] - h[i],
- h[(j + 1) % n] - h[j]) <= 0) break;
- j = (j + 1) % n;
+ if (cross(h[(i + 1) % sz(h)] - h[i],
+ h[(j + 1) % sz(h)] - h[j]) <= 0) break;
+ j = (j + 1) % sz(h);
}}
return result;
}
diff --git a/geometry/geometry.tex b/geometry/geometry.tex
index 3e50a8e..a027de4 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}{Konvexe Hülle}
\begin{methods}
\method{convexHull}{berechnet Konvexehülle}{n\*\log(n)}
@@ -19,22 +27,14 @@
\sourcecode{geometry/convexHull.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}
-
\subsection{Formeln~~--~\texttt{std::complex}}
\sourcecode{geometry/formulars.cpp}
\sourcecode{geometry/linesAndSegments.cpp}
\input{geometry/triangle}
\sourcecode{geometry/triangle.cpp}
\sourcecode{geometry/polygon.cpp}
-\sourcecode{geometry/circle.cpp}
\sourcecode{geometry/sortAround.cpp}
+\sourcecode{geometry/circle.cpp}
\subsection{Formeln - 3D}
\sourcecode{geometry/formulars3d.cpp}
diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp
index a9ba9ab..d298fde 100644
--- a/geometry/linesAndSegments.cpp
+++ b/geometry/linesAndSegments.cpp
@@ -82,9 +82,8 @@ double distBetweenSegments(pt a, pt b, pt c, pt d) {
distToSegment(c, d, a), distToSegment(c, d, b)});
}
-// sortiert alle Punkte pts auf einer Linie
-// entsprechend der richtung dir 2d und 3d
-void sortLine(pt dir, vector<pt>& pts) {
+// sortiert alle Punkte pts auf einer Linie entsprechend dir
+void sortLine(pt dir, vector<pt>& pts) { // (2d und 3d)
sort(all(pts), [&](pt a, pt b){
return dot(dir, a) < dot(dir, b);
});
diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp
index 1620d7c..8b943a6 100644
--- a/geometry/polygon.cpp
+++ b/geometry/polygon.cpp
@@ -123,7 +123,6 @@ int extremal(const vector<pt>& hull, pt dir) {
vector<int> intersect(const vector<pt>& hull, pt a, pt b) {
int endA = extremal(hull, (a-b) * pt(0, 1));
int endB = extremal(hull, (b-a) * pt(0, 1));
-
// cross == 0 => line only intersects border
if (cross(hull[endA], a, b) > 0 ||
cross(hull[endB], a, b) < 0) return {};
@@ -136,11 +135,10 @@ vector<int> intersect(const vector<pt>& hull, pt a, pt b) {
while (l + 1 < r) {
int m = (l + r) / 2;
if (cross(hull[m % n], a, b) <= 0 &&
- cross(hull[m % n], a, b) != hull(poly[endB], a, b)) {
+ cross(hull[m % n], a, b) != hull(poly[endB], a, b))
l = m;
- } else {
- r = m;
- }}
+ else r = m;
+ }
if (cross(hull[r % n], a, b) == 0) l++;
res.push_back(l % n);
swap(endA, endB);
diff --git a/geometry/triangle.cpp b/geometry/triangle.cpp
index 4dbd532..a00eb56 100644
--- a/geometry/triangle.cpp
+++ b/geometry/triangle.cpp
@@ -12,6 +12,12 @@ double area(double a, double b, double c) {
return sqrt(s * (s-a) * (s-b) * (s-c));
}
+// Zentrum des größten Kreises im Dreiecke
+pt inCenter(pt a, pt b, pt c) {
+ double x = abs(a-b), y = abs(b-c), z = abs(a-c);
+ return (y*a + z*b + x*c) / (x+y+z);
+}
+
// Zentrum des Kreises durch alle Eckpunkte
pt outCenter(pt a, pt b, pt c) {
double d = 2.0 * (real(a) * imag(b-c) +
@@ -22,13 +28,6 @@ pt outCenter(pt a, pt b, pt c) {
c*conj(c)*conj(a-b)) / d;
}
-// Zentrum des größten Kreises im Dreiecke
-pt inCenter(pt a, pt b, pt c) {
- double x = abs(a-b), y = abs(b-c), z = abs(a-c);
- return (y*a + z*b + x*c) / (x+y+z);
-}
-
-
// Sind die Dreiecke a1, b1, c1, and a2, b2, c2 ähnlich?
// Erste Zeile testet Ähnlichkeit mit gleicher Orientierung,
// zweite Zeile testet Ähnlichkeit mit verschiedener Orientierung
diff --git a/graph/2sat.cpp b/graph/2sat.cpp
index 2ebb11a..4e47ba0 100644
--- a/graph/2sat.cpp
+++ b/graph/2sat.cpp
@@ -4,19 +4,19 @@ struct sat2 {
sat2(int vars) : n(vars*2), adjlist(vars*2) {};
- static int var(int i) {return i << 1;}
+ static int var(int i) {return i << 1;} // use this!
- void addImpl(int v1, int v2) {
- adjlist[v1].push_back(v2);
- adjlist[1^v2].push_back(1^v1);
+ void addImpl(int a, int b) {
+ adjlist[a].push_back(b);
+ adjlist[1^b].push_back(1^a);
}
- void addEquiv(int v1, int v2) {addImpl(v1, v2); addImpl(v2, v1);}
- void addOr(int v1, int v2) {addImpl(1^v1, v2);}
- void addXor(int v1, int v2) {addOr(v1, v2); addOr(1^v1, 1^v2);}
- void addTrue(int v1) {addImpl(1^v1, v1);}
- void addFalse(int v1) {addTrue(1^v1);}
- void addAnd(int v1, int v2) {addTrue(v1); addTrue(v2);}
- void addNand(int v1, int v2) {addOr(1^v1, 1^v2);}
+ void addEquiv(int a, int b) {addImpl(a, b); addImpl(b, a);}
+ void addOr(int a, int b) {addImpl(1^a, b);}
+ void addXor(int a, int b) {addOr(a, b); addOr(1^a, 1^b);}
+ void addTrue(int a) {addImpl(1^a, a);}
+ void addFalse(int a) {addTrue(1^a);}
+ void addAnd(int a, int b) {addTrue(a); addTrue(b);}
+ void addNand(int a, int b) {addOr(1^a, 1^b);}
bool solvable() {
scc(); //scc code von oben
diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp
index 0df1eeb..fb18d36 100644
--- a/graph/articulationPoints.cpp
+++ b/graph/articulationPoints.cpp
@@ -29,7 +29,7 @@ int dfs(int v, int parent = -1) {
return top;
}
-void findArticulationPoints() {
+void find() {
counter = 0;
num.assign(sz(adjlist), 0);
isArt.assign(sz(adjlist), false);
diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp
index b64b230..c3fe457 100644
--- a/graph/cycleCounting.cpp
+++ b/graph/cycleCounting.cpp
@@ -1,15 +1,14 @@
-constexpr ll maxEdges = 128;
+constexpr int maxEdges = 128;
using cycle = bitset<maxEdges>;
struct cylces {
- ll n;
- vector<vector<pair<ll, ll>>> adj;
+ vector<vector<pair<int, int>>> adj;
vector<bool> seen;
vector<cycle> paths, base;
- vector<pair<ll, ll>> edges;
+ vector<pair<int, int>> edges;
- cylces(ll n) : n(n), adj(n), seen(n), paths(n) {}
+ cylces(int n) : adj(n), seen(n), paths(n) {}
- void addEdge(ll a, ll b) {
+ void addEdge(int a, int b) {
adj[a].push_back({b, sz(edges)});
adj[b].push_back({a, sz(edges)});
edges.push_back({a, b});
@@ -23,8 +22,8 @@ struct cylces {
if (cur.any()) base.push_back(cur);
}
- void findBase(ll c = 0, ll p = -1, cycle cur = {}) {
- if (n == 0) return;
+ void findBase(int c = 0, int p = -1, cycle cur = {}) {
+ if (adj.empty()) return;
if (seen[c]) {
addBase(cur ^ paths[c]);
} else {
@@ -40,8 +39,8 @@ struct cylces {
//cycle must be constrcuted from base
bool isCycle(cycle cur) {
if (cur.none()) return false;
- init(n);
- for (ll i = 0; i < sz(edges); i++) {
+ init(sz(adj)); // union find
+ for (int i = 0; i < sz(edges); i++) {
if (cur[i]) {
cur[i] = false;
if (findSet(edges[i].first) ==
@@ -51,12 +50,12 @@ struct cylces {
return cur.none();
};
- ll count() {
+ int count() {
findBase();
- ll res = 0;
- for (ll i = 1; i < (1ll << sz(base)); i++) {
+ int res = 0;
+ for (int i = 1; i < (1 << sz(base)); i++) {
cycle cur;
- for (ll j = 0; j < sz(base); j++) {
+ for (int j = 0; j < sz(base); j++) {
if (((i >> j) & 1) != 0) cur ^= base[j];
if (isCycle(cur)) res++;
}
diff --git a/graph/euler.cpp b/graph/euler.cpp
index 0907ab2..6ef3c13 100644
--- a/graph/euler.cpp
+++ b/graph/euler.cpp
@@ -6,21 +6,18 @@ void addEdge(int a, int b) {
idx[a].push_back(sz(to));
to.push_back(b);
used.push_back(false);
- idx[b].push_back(sz(to)); //für ungerichtet
+ idx[b].push_back(sz(to)); // für ungerichtet
to.push_back(a);
used.push_back(false);
}
-// Findet Eulerzyklus an Knoten n startend.
-// init idx und validIdx
-void euler(int n) {
+void euler(int n) { // init idx und validIdx
for (;validIdx[n] < sz(idx[n]); validIdx[n]++) {
if (!used[idx[n][validIdx[n]]]) {
int nn = to[idx[n][validIdx[n]]];
used[idx[n][validIdx[n]]] = true;
- used[idx[n][validIdx[n]] ^ 1] = true; //für ungerichtet
+ used[idx[n][validIdx[n]] ^ 1] = true; // für ungerichtet
euler(nn);
}}
- // Zyklus in cycle in umgekehrter Reihenfolge.
- cycle.push_back(n);
+ cycle.push_back(n); // Zyklus in umgekehrter Reihenfolge.
}
diff --git a/graph/graph.tex b/graph/graph.tex
index a26661d..47f1d75 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -68,52 +68,6 @@ Sei $d_{ij}$ die Distanzmatrix von $G$, dann gibt $d_{ij}^k$ die kürzeste Dista
Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{ij}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{ij} = a_{ij} \* b_{ij} = \sum a_{ik} + b_{kj}$
-\begin{algorithm}{Artikulationspunkte, Brücken und BCC}
- \begin{methods}
- \method{findArticulationPoints}{berechnet Artikulationspunkte,}{\abs{V}+\abs{E}}
- \method{}{Brücken und BCC}{}
- \end{methods}
- \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC.
- \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}
-
-\begin{algorithm}{Eulertouren}
- \begin{methods}
- \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
- \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>> adjlist} leichter
- \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
- Die Existenz muss separat geprüft werden.
- \end{itemize}
-\end{algorithm}
-
-\begin{algorithm}{Cycle Counting}
- \begin{methods}
- \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
- \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
- \end{methods}
- \begin{itemize}
- \item jeder Zyklus ist das xor von einträgen in \code{base}.
- \end{itemize}
- \sourcecode{graph/cycleCounting.cpp}
-\end{algorithm}
-
\begin{algorithm}{Lowest Common Ancestor}
\begin{methods}
\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
@@ -132,14 +86,33 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
\sourcecode{graph/hld.cpp}
\end{algorithm}
+\clearpage
-\begin{algorithm}{Dynamic Connectivity}
+\begin{algorithm}{Maximal Cliques}
\begin{methods}
- \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
- \method{addEdge}{fügt Kannte ein,\texttt{id}=delete Zeitpunkt}{\log(n)}
- \method{eraseEdge}{entfernt Kante \texttt{id}}{\log(n)}
+ \method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
+ \method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
\end{methods}
- \sourcecode{graph/connect.cpp}
+ \sourcecode{graph/bronKerbosch.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Artikulationspunkte, Brücken und BCC}
+ \begin{methods}
+ \method{find}{berechnet Artikulationspunkte, Brücken und BCC}{\abs{V}+\abs{E}}
+ \end{methods}
+ \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC.
+ \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}
\begin{algorithm}{Global Mincut}
@@ -254,10 +227,37 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
\end{algorithm}
}
-\begin{algorithm}{Maximal Cliques}
+\begin{algorithm}{Cycle Counting}
\begin{methods}
- \method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
- \method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
+ \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
+ \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
\end{methods}
- \sourcecode{graph/bronKerbosch.cpp}
+ \begin{itemize}
+ \item jeder Zyklus ist das xor von einträgen in \code{base}.
+ \end{itemize}
+ \sourcecode{graph/cycleCounting.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Eulertouren}
+ \begin{methods}
+ \method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
+ \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>> adjlist} leichter
+ \item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+ Die Existenz muss separat geprüft werden.
+ \end{itemize}
+\end{algorithm}
+
+\begin{algorithm}{Dynamic Connectivity}
+ \begin{methods}
+ \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+ \method{addEdge}{fügt Kannte ein,\texttt{id}=delete Zeitpunkt}{\log(n)}
+ \method{eraseEdge}{entfernt Kante \texttt{id}}{\log(n)}
+ \end{methods}
+ \sourcecode{graph/connect.cpp}
\end{algorithm}
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp
index 86a10ae..623f94b 100644
--- a/math/chineseRemainder.cpp
+++ b/math/chineseRemainder.cpp
@@ -1,14 +1,13 @@
-// 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, falls alle teilerfremd sind).
+// 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 {
using lll = __int128;
vector<lll> lhs, rhs, mods, inv;
lll M; // Produkt über die Moduli. Kann leicht überlaufen.
- ll g(vector<lll> &vec) {
+ ll g(const vector<lll> &vec) {
lll res = 0;
for (int i = 0; i < sz(vec); i++) {
res += (vec[i] * inv[i]) % M;
@@ -24,8 +23,7 @@ struct ChineseRemainder {
mods.push_back(m);
}
- // Löst das System.
- ll solve() {
+ 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++) {
diff --git a/math/linearRecurence.cpp b/math/linearRecurence.cpp
new file mode 100644
index 0000000..83c4e05
--- /dev/null
+++ b/math/linearRecurence.cpp
@@ -0,0 +1,32 @@
+constexpr ll mod = 1000000007;
+vector<ll> modMul(const vector<ll>& a, const vector<ll>& b, const vector<ll>& c) {
+ ll n = sz(c);
+ vector<ll> 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<ll>& f, const vector<ll>& c, ll k) {
+ assert(sz(f) == sz(c));
+ vector<ll> 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 feb0466..31fbdd6 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,38 +1,26 @@
\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}{Permutationen}
- \begin{methods}
- \method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
- \end{methods}
- \sourcecode{math/kthperm.cpp}
- \begin{methods}
- \method{permIndex}{bestimmt index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
- \end{methods}
- \sourcecode{math/permIndex.cpp}
+\begin{algorithm}{Longest Increasing Subsequence}
+ \begin{itemize}
+ \item \code{lower\_bound} $\Rightarrow$ streng monoton
+ \item \code{upper\_bound} $\Rightarrow$ monoton
+ \end{itemize}
+ \sourcecode{math/longestIncreasingSubsequence.cpp}
\end{algorithm}
-\paragraph{Lemma von \textsc{Bézout}}
-Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
-Dann lassen sich wie folgt alle Lösungen berechnen:
-\[
-\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
-\]
-
-\paragraph{\textsc{Pell}-Gleichungen}
-Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
-Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
-sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
-\begin{align*}
- x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
- x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
-\end{align*}
+\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
+%\vspace{-1.25em}
+%\begin{multicols}{2}
+\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
+\sourcecode{math/modMulIterativ.cpp}
+% \vfill\null\columnbreak
+\method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
+\sourcecode{math/modPowIterativ.cpp}
+%\end{multicols}
+%\vspace{-2.75em}
+\begin{itemize}
+ \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
+\end{itemize}
\begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}
\runtime{\log(a) + \log(b)}
@@ -49,7 +37,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
$\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$
- \end{itemize}
+\end{itemize}
\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.
\sourcecode{math/multInv.cpp}
@@ -62,38 +50,55 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\sourcecode{math/linearCongruence.cpp}
\end{algorithm}
-\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$}
-%\vspace{-1.25em}
-%\begin{multicols}{2}
- \method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)}
- \sourcecode{math/modMulIterativ.cpp}
-% \vfill\null\columnbreak
- \method{powMod}{berechnet $a^b \bmod n$}{\log(b)}
- \sourcecode{math/modPowIterativ.cpp}
-%\end{multicols}
-%\vspace{-2.75em}
-\begin{itemize}
- \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten!
-\end{itemize}
+\paragraph{Lemma von \textsc{Bézout}}
+Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$.
+Dann lassen sich wie folgt alle Lösungen berechnen:
+\[
+\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right)
+\]
-\begin{algorithm}{Matrix-Exponent}
+\paragraph{\textsc{Pell}-Gleichungen}
+Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert.
+Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen
+sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
+\begin{align*}
+ x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\
+ x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k
+\end{align*}
+
+
+\begin{algorithm}{Zykel Erkennung}
\begin{methods}
- \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
- \method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+ \method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}
\end{methods}
- \sourcecode{math/matrixPower.cpp}
+ \sourcecode{math/cycleDetection.cpp}
\end{algorithm}
-\begin{algorithm}{Berlekamp-Massey}
+\begin{algorithm}{Permutationen}
\begin{methods}
- \method{BerlekampMassey}{Berechnet ein lineare Recurenz $n$-ter Ordnung}{n^2}
- \method{}{aus den ersten $2n$ Werte}{}
+ \method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)}
\end{methods}
- \sourcecode{math/berlekampMassey.cpp}
+ \sourcecode{math/kthperm.cpp}
+ \begin{methods}
+ \method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)}
+ \end{methods}
+ \sourcecode{math/permIndex.cpp}
\end{algorithm}
\begin{algorithm}{Lineare-Recurenz}
- Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine Lineare Recurenz. Dann kann das \mbox{$k$-te} folgenglid in \runtime{n^3\log(k)} brechnet werden.
+ \begin{methods}
+ \method{BerlekampMassey}{Berechnet eine lineare Recurenz $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.
+
+ \begin{methods}
+ \method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $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:
+ \small
$$\renewcommand\arraystretch{1.5}
\setlength\arraycolsep{3pt}
\begin{pmatrix}
@@ -113,15 +118,24 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\end{pmatrix}
~~=~~
\begin{pmatrix}
- f(n-1+k) \\
- f(n-2+k) \\
- \smash{\vdots} \\
- \smash{\vdots} \\
- f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
+ f(n-1+k) \\
+ f(n-2+k) \\
+ \smash{\vdots} \\
+ \smash{\vdots} \\
+ f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\
\end{pmatrix}
$$
\end{algorithm}
+
+\begin{algorithm}{Matrix-Exponent}
+ \begin{methods}
+ \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3}
+ \method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2}
+ \end{methods}
+ \sourcecode{math/matrixPower.cpp}
+\end{algorithm}
+
\begin{algorithm}{Chinesischer Restsatz}
\begin{itemize}
\item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden.
@@ -140,33 +154,42 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\sourcecode{math/chineseRemainder.cpp}
\end{algorithm}
-\begin{algorithm}{Primzahltest \& Faktorisierung}
- \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
- \sourcecode{math/millerRabin.cpp}
- \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}3]{n}}
- \sourcecode{math/rho.cpp}
- %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
- %\sourcecode{math/squfof.cpp}
+\begin{algorithm}{Teiler}
+ \begin{methods}
+ \method{countDivisors}{Zählt Teiler von $n$}{n^\frac{1}{3}}
+ \method{isPrime}{prüft ob Zahl prim ist}{1}
+ \end{methods}
+ \sourcecode{math/divisors.cpp}
\end{algorithm}
-\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
+\begin{algorithm}{Primitivwurzeln}
\begin{itemize}
- \item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
- \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
+ \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{primeSieve}{berechnet Primzahlen und Anzahl}{n\*\log(\log(n))}
- \method{isPrime}{prüft ob Zahl prim ist}{1}
+ \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/primeSieve.cpp}
+ \sourcecode{math/primitiveRoot.cpp}
\end{algorithm}
-\begin{algorithm}{Teiler}
+\begin{algorithm}{Diskreter Logarithmus}
\begin{methods}
- \method{countDivisors}{Zählt teiler von $n$}{n^\frac{1}{3}}
- \method{isPrime}{prüft ob Zahl prim ist}{1}
+ \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
\end{methods}
- \sourcecode{math/divisors.cpp}
+ \sourcecode{math/discreteLogarithm.cpp}
+\end{algorithm}
+%TODO
+\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel}
+ \begin{methods}
+ \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
+ \end{methods}
+ Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
+ \sourcecode{math/discreteNthRoot.cpp}
\end{algorithm}
\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
@@ -176,23 +199,36 @@ 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}
+\clearpage
-\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
-\begin{itemize}
- \item Zählt die relativ primen Zahlen $\leq n$.
+\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
+\method{gauss}{löst LGS}{n^3}
+\sourcecode{math/lgsFp.cpp}
- \item Multiplikativ:
- $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
+\sourcecode{math/gauss.cpp}
- \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}{Primzahltest \& Faktorisierung}
+ \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2}
+ \sourcecode{math/millerRabin.cpp}
+ \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}}
+ \sourcecode{math/rho.cpp}
+ %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}}
+ %\sourcecode{math/squfof.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}
+ \begin{itemize}
+ \item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen
+ \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)
+ \end{itemize}
+ \begin{methods}
+ \method{primeSieve}{berechnet Primzahlen und Anzahl}{n\*\log(\log(n))}
+ \method{isPrime}{prüft ob Zahl prim ist}{1}
+ \end{methods}
+ \sourcecode{math/primeSieve.cpp}
+\end{algorithm}
\begin{algorithm}{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion}
\begin{itemize}
@@ -200,8 +236,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$.
\item $\sum\limits_{d \vert n}\mu(d) =
\begin{cases*}
- 1 & falls $n = 1$\\
- 0 & sonst
+ 1 & falls $n = 1$\\
+ 0 & sonst
\end{cases*}$
\end{itemize}
\textbf{Beispiel Inklusion/Exklusion:}
@@ -212,43 +248,24 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$.
\sourcecode{math/mobius.cpp}
\end{algorithm}
+\clearpage
-\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}
+\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}
+\begin{itemize}
+ \item Zählt die relativ primen Zahlen $\leq n$.
-\begin{algorithm}{Diskreter Logarithmus}
- \begin{methods}
- \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)}
- \end{methods}
- \sourcecode{math/discreteLogarithm.cpp}
-\end{algorithm}
-%TODO
-\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel}
- \begin{methods}
- \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)}
- \end{methods}
- Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$
- \sourcecode{math/discreteNthRoot.cpp}
-\end{algorithm}
+ \item Multiplikativ:
+ $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$
-\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}
-\method{gauss}{löst LGS}{n^3}
-\sourcecode{math/lgsFp.cpp}
+ \item $p$ prim, $k \in \mathbb{N}$:
+ $~\varphi(p^k) = p^k - p^{k - 1}$
-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}
-\sourcecode{math/gauss.cpp}
+ \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$.
@@ -257,8 +274,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe
$\deg(A \cdot B) + 1$ haben.
Größe muss eine Zweierpotenz sein.
- \item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))}
- \item xor, or und and Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
+ \item Für ganzzahlige Koeffizienten: \lstinline{(ll)round(real(a[i]))}
+ \item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$
\end{itemize}
%\lstinputlisting{math/fft.cpp}
%\lstinputlisting{math/ntt.cpp}
@@ -278,14 +295,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\sourcecode{math/simpson.cpp}
\end{algorithm}
-\begin{algorithm}{Longest Increasing Subsequence}
- \begin{itemize}
- \item \code{lower\_bound} $\Rightarrow$ streng monoton
- \item \code{upper\_bound} $\Rightarrow$ monoton
- \end{itemize}
- \sourcecode{math/longestIncreasingSubsequence.cpp}
-\end{algorithm}
-
\begin{algorithm}{\textsc{Legendre}-Symbol}
Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:
\begin{align*}
@@ -375,27 +384,27 @@ so gilt
\[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} =
\frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} \cdot C_{n-1}\]
\begin{itemize}
- \item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
- \item Formel $2$ und $3$ erlauben berechnung in \runtime{n}
+ \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+ \item Formel $2$ und $3$ erlauben Berechnung in \runtime{n}
\end{itemize}
\paragraph{\textsc{Euler}-Zahlen 1. Ordnung}
Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen.
Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen.
-Dabei wird entweder ein Ansteig in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
+Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt.
\[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad
\eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}=
\sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\]
\begin{itemize}
- \item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
- \item Formel $2$ erlaubt berechnung in \runtime{n\log(n)}
+ \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+ \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
\end{itemize}
\paragraph{\textsc{Euler}-Zahlen 2. Ordnung}
Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen.
\[\eulerII{n}{0} = 1 \qquad\eulerII{n}{n} = 0 \qquad\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}\]
\begin{itemize}
- \item Formel erlaubt berechnung ohne Division in \runtime{n^2}
+ \item Formel erlaubt Berechnung ohne Division in \runtime{n^2}
\end{itemize}
\paragraph{\textsc{Stirling}-Zahlen 1. Ordnung}
@@ -416,13 +425,13 @@ Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht.
\stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
\frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\]
\begin{itemize}
- \item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2}
- \item Formel $2$ erlaubt berechnung in \runtime{n\log(n)}
+ \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2}
+ \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)}
\end{itemize}
\paragraph{\textsc{Bell}-Zahlen}
Anzahl der Partitionen von $\{1, \ldots, n\}$.
-Wie \textsc{Striling}-Zahlen 2. Ordnung ohne Limit durch $k$.
+Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$.
\[B_1 = 1 \qquad
B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k}
= \sum\limits_{k = 0}^{n}\stirlingII{n}{k}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\]
diff --git a/math/rho.cpp b/math/rho.cpp
index 1f5ba86..865a438 100644
--- a/math/rho.cpp
+++ b/math/rho.cpp
@@ -13,10 +13,7 @@ ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
void factor(ll n, map<ll, int>& facts) {
if (n == 1) return;
- if (isPrime(n)) {
- facts[n]++;
- return;
- }
+ if (isPrime(n)) {facts[n]++, return;}
ll f = rho(n);
factor(n / f, facts);
factor(f, facts);
diff --git a/math/transforms/all.cpp b/math/transforms/all.cpp
index 4f4d83b..22cd5b5 100644
--- a/math/transforms/all.cpp
+++ b/math/transforms/all.cpp
@@ -24,8 +24,7 @@ void fft(vector<cplx>& a, bool inverse = 0) {
t %= mod;
a[j + k] = (u + t) % mod;
a[j + s + k] = (u - t + mod) % mod;
- w *= ws;
- w %= mod;*/
+ w = (w * ws) % mod;*/
/*ll u = a[j + k], t = a[j + s + k]; @\hl{xor only}@
a[j + k] = u + t;
a[j + s + k] = u - t;*/
@@ -52,8 +51,7 @@ void fft(vector<cplx>& a, bool inverse = 0) {
/*if (inverse) { @\hl{NTT only}@
ll div = powMod(n, mod - 2, mod);
for (ll i = 0; i < n; i++) {
- a[i] *= div;
- a[i] %= mod;
+ a[i] = (a[i] * div) % mod;
}}*/
/*if (inverse) { @\hl{xor only}@
for (ll i = 0; i < n; i++) {
diff --git a/tcr.pdf b/tcr.pdf
index 082d961..211d73b 100644
--- a/tcr.pdf
+++ b/tcr.pdf
Binary files differ
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 21:22:56 +0000