diff options
47 files changed, 100 insertions, 104 deletions
diff --git a/datastructures/LCT.cpp b/datastructures/LCT.cpp index fde052d..b67ab82 100644 --- a/datastructures/LCT.cpp +++ b/datastructures/LCT.cpp @@ -35,13 +35,13 @@ struct LCT { int id, size; Node *left, *right, *parent; - Node(int id = 0, int val = queryDefault) : - nodeValue(val), subTreeValue(val), delta(updateDefault), + Node(int id = 0, int val = queryDefault) : + nodeValue(val), subTreeValue(val), delta(updateDefault), revert(false), id(id), size(1), left(nullptr), right(nullptr), parent(nullptr) {} bool isRoot() { - return !parent || (parent->left != this && + return !parent || (parent->left != this && parent->right != this); } @@ -53,7 +53,7 @@ struct LCT { if (right) right->revert ^= 1; } nodeValue = joinValueDelta(nodeValue, delta); - subTreeValue = joinValueDelta(subTreeValue, + subTreeValue = joinValueDelta(subTreeValue, _update(delta, size)); if (left) left->delta = joinDeltas(left->delta, delta); if (right) right->delta = joinDeltas(right->delta, delta); @@ -73,7 +73,7 @@ struct LCT { size += left->size; } if (right) { - subTreeValue = _query(subTreeValue, + subTreeValue = _query(subTreeValue, right->getSubtreeValue()); size += right->size; }} @@ -111,7 +111,7 @@ struct LCT { if (!p->isRoot()) g->push(); p->push(); x->push(); - if (!p->isRoot()) rotate((x == p->left) == + if (!p->isRoot()) rotate((x == p->left) == (p == g->left) ? p : x); rotate(x); } diff --git a/datastructures/dynamicConvexHull.cpp b/datastructures/dynamicConvexHull.cpp index 61ba976..f88b2ad 100644 --- a/datastructures/dynamicConvexHull.cpp +++ b/datastructures/dynamicConvexHull.cpp @@ -1,13 +1,13 @@ struct Line { mutable ll m, b, p; - bool operator<(const Line& o) const { return m < o.m; } - bool operator<(ll x) const { return p < x; } + bool operator<(const Line& o) const {return m < o.m;} + bool operator<(ll x) const {return p < x;} }; struct HullDynamic : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static constexpr ll INF = LLONG_MAX; - ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } + ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} bool isect(iterator x, iterator y) { if (y == end()) {x->p = INF; return false;} diff --git a/datastructures/fenwickTree2.cpp b/datastructures/fenwickTree2.cpp index dfd5dc5..ff87e2e 100644 --- a/datastructures/fenwickTree2.cpp +++ b/datastructures/fenwickTree2.cpp @@ -4,7 +4,7 @@ void update(int l, int r, ll val) { for (int tl = l + 1; tl < sz(add); tl += tl&(-tl)) add[tl] += val, mul[tl] -= val * l; for (int tr = r + 1; tr < sz(add); tr += tr&(-tr)) - add[tr] -= val, mul[tr] += val * r; + add[tr] -= val, mul[tr] += val * r; } void init(vector<ll>& v) { diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 7003855..4b3dbff 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -3,7 +3,7 @@ vector<ll> ms, bs; int ptr = 0; bool bad(int l1, int l2, int l3) { - return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < + return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < (bs[l2]-bs[l1])*(ms[l1]-ms[l3]); } diff --git a/datastructures/treap.cpp b/datastructures/treap.cpp index eef56b4..c96e36a 100644 --- a/datastructures/treap.cpp +++ b/datastructures/treap.cpp @@ -1,6 +1,6 @@ struct node { int key, prio, left, right, size; - node(int key, int prio) : key(key), prio(prio), left(-1), + node(int key, int prio) : key(key), prio(prio), left(-1), right(-1), size(1) {}; }; diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp index 225ecee..b86c8e0 100644 --- a/datastructures/unionFind2.cpp +++ b/datastructures/unionFind2.cpp @@ -11,17 +11,15 @@ int findSet(int i) { } void linkSets(int i, int j) { - //Take |uf[i]|, where i must be a root, to get the size + //Take |uf[i]|, where i must be a root, to get the size //of the subset if(abs(uf[i]) < abs(uf[j])) { //Union-by-size. - uf[j] += uf[i]; uf[i] = j; + uf[j] += uf[i]; uf[i] = j; } else { - uf[i] += uf[j]; uf[j] = i; + uf[i] += uf[j]; uf[j] = i; } } void unionSets(int i, int j) { if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j)); -} - - +} diff --git a/geometry/antipodalPoints.cpp b/geometry/antipodalPoints.cpp index db39b39..110cc74 100644 --- a/geometry/antipodalPoints.cpp +++ b/geometry/antipodalPoints.cpp @@ -4,7 +4,7 @@ vector<pair<int, int>> antipodalPoints(vector<pt>& h) { for (int i = 0, j = 1; i < j; i++) { while (true) { result.push_back({i, j}); - if (cross(h[(i + 1) % sz(h)] - h[i], + if (cross(h[(i + 1) % sz(h)] - h[i], h[(j + 1) % sz(h)] - h[j]) <= 0) break; j = (j + 1) % sz(h); }} diff --git a/geometry/circle.cpp b/geometry/circle.cpp index f48e09a..8ebc800 100644 --- a/geometry/circle.cpp +++ b/geometry/circle.cpp @@ -1,6 +1,6 @@ // berechnet die Schnittpunkte von zwei kreisen // (Kreise dürfen nicht gleich sein!) -vector<pt> circleIntersection(pt c1, double r1, +vector<pt> circleIntersection(pt c1, double r1, pt c2, double r2) { double d = abs(c1 - c2); if (d < abs(r1 - r2) || d > abs(r1 + r2)) return {}; @@ -14,7 +14,7 @@ vector<pt> circleIntersection(pt c1, double r1, // berechnet die Schnittpunkte zwischen // einem Kreis(Kugel) und einer Grade 2d und 3d -vector<pt> circleRayIntersection(pt center, double r, +vector<pt> circleRayIntersection(pt center, double r, pt orig, pt dir) { vector<pt> result; double a = dot(dir, dir); diff --git a/geometry/closestPair.cpp b/geometry/closestPair.cpp index 6cde5ae..a2c91b3 100644 --- a/geometry/closestPair.cpp +++ b/geometry/closestPair.cpp @@ -1,5 +1,5 @@ bool compY(pt a, pt b) { - return (imag(a) == imag(b)) ? real(a) < real(b) + return (imag(a) == imag(b)) ? real(a) < real(b) : imag(a) < imag(b); } diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp index d298fde..ba6c468 100644 --- a/geometry/linesAndSegments.cpp +++ b/geometry/linesAndSegments.cpp @@ -10,7 +10,7 @@ bool lineSegmentIntersection(pt a, pt b, pt c, pt d) { } // Berechnet die Schnittpunkte der Strecken p0-p1 und p2-p3. -// Enthält entweder keinen Punkt, den einzigen Schnittpunkt +// Enthält entweder keinen Punkt, den einzigen Schnittpunkt // oder die Endpunkte der Schnittstrecke. vector<pt> lineSegmentIntersection(pt p0, pt p1, pt p2, pt p3) { double a = cross(p1 - p0, p3 - p2); @@ -53,7 +53,7 @@ bool lineIntersection(pt a, pt b, pt c, pt d) { } // Berechnet den Schnittpunkt der Graden p0-p1 und p2-p3. -// die Graden dürfen nicht parallel sein! +// die Graden dürfen nicht parallel sein! pt lineIntersection(pt p0, pt p1, pt p2, pt p3) { double a = cross(p1 - p0, p3 - p2); double b = cross(p2 - p0, p3 - p2); diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp index 8b943a6..f562b7a 100644 --- a/geometry/polygon.cpp +++ b/geometry/polygon.cpp @@ -91,7 +91,7 @@ double dist(const vector<pt>& ps, const vector<pt>& qs) { return res; } -bool left(pt of, pt p) {return cross(p, of) < 0 || +bool left(pt of, pt p) {return cross(p, of) < 0 || (cross(p, of) == 0 && dot(p, of) > 0);} // convex hulls without duplicates, hull[0] == hull.back() and diff --git a/geometry/segmentIntersection.cpp b/geometry/segmentIntersection.cpp index b2e3ac4..6dc5dc5 100644 --- a/geometry/segmentIntersection.cpp +++ b/geometry/segmentIntersection.cpp @@ -12,7 +12,7 @@ struct seg { return imag(a) < imag(o.a); } }; - + struct event { pt p; int id, type; @@ -22,16 +22,16 @@ struct event { return imag(p) < imag(o.p); } }; - + bool lessPT(const pt& a, const pt& b) { return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b); } - + bool intersect(const seg& a, const seg& b) { return lineSegmentIntersection(a.a, a.b, b.a, b.b); } - + pair<int, int> intersect(vector<seg>& segs) { vector<event> events; for (seg& s : segs) { @@ -40,7 +40,7 @@ pair<int, int> intersect(vector<seg>& segs) { events.push_back({s.b, s.id, -1}); } sort(all(events)); - + set<seg> q; vector<set<seg>::iterator> where(sz(segs)); for (auto e : events) { diff --git a/geometry/spheres.cpp b/geometry/spheres.cpp index 01c54de..abffde5 100644 --- a/geometry/spheres.cpp +++ b/geometry/spheres.cpp @@ -1,5 +1,5 @@ // Great Cirlce Distance mit Längen- und Breitengrad. -double gcDist(double pLat, double pLon, +double gcDist(double pLat, double pLon, double qLat, double qLon, double radius) { pLat *= PI / 180; pLon *= PI / 180; qLat *= PI / 180; qLon *= PI / 180; diff --git a/graph/TSP.cpp b/graph/TSP.cpp index 856107f..e0fced6 100644 --- a/graph/TSP.cpp +++ b/graph/TSP.cpp @@ -9,9 +9,9 @@ void TSP() { for (int v = m - 2; v >= 0; v--) { for (int c = n - 1; c >= 0; c--) { - for (int g = 0; g < n; g++) { + for (int g = 0; g < n; g++) { if (g != c && !((1 << g) & v)) { - if ((dp[g][(v | (1 << g))].dist + dist[c][g]) < + if ((dp[g][(v | (1 << g))].dist + dist[c][g]) < dp[c][v].dist) { dp[c][v].dist = dp[g][(v | (1 << g))].dist + dist[c][g]; diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp index 730cad2..785a42d 100644 --- a/graph/bellmannFord.cpp +++ b/graph/bellmannFord.cpp @@ -4,7 +4,7 @@ void bellmannFord(int n, vector<edge> edges, int start) { for (int i = 1; i < n; i++) { for (edge& e : edges) { - if (dist[e.from] != INF && + if (dist[e.from] != INF && dist[e.from] + e.cost < dist[e.to]) { dist[e.to] = dist[e.from] + e.cost; parent[e.to] = e.from; diff --git a/graph/bitonicTSPsimple.cpp b/graph/bitonicTSPsimple.cpp index 7a0c3c8..96ae5bd 100644 --- a/graph/bitonicTSPsimple.cpp +++ b/graph/bitonicTSPsimple.cpp @@ -11,7 +11,7 @@ double get(int p1, int p2) { } void bitonicTour() { - dp = vector<vector<double>>(sz(dist), + dp = vector<vector<double>>(sz(dist), vector<double>(sz(dist), -1)); get(0, 0); // return dp[0][0]; // Länger der Tour diff --git a/graph/blossom.cpp b/graph/blossom.cpp index 72531c6..13a3246 100644 --- a/graph/blossom.cpp +++ b/graph/blossom.cpp @@ -5,7 +5,7 @@ struct GM { vector<pair<int, int>> label; int head, tail; - GM(int n) : adjlist(n), pairs(n + 1, n), first(n + 1, n), + GM(int n) : adjlist(n), pairs(n + 1, n), first(n + 1, n), que(n), label(n + 1, {-1, -1}) {} void rematch(int v, int w) { @@ -15,8 +15,7 @@ struct GM { pairs[t] = label[v].first; rematch(pairs[t], t); } else { - int x = label[v].first; - int y = label[v].second; + auto [x, y] = label[v]; rematch(x, y); rematch(y, x); }} diff --git a/graph/capacityScaling.cpp b/graph/capacityScaling.cpp index 8467f81..b8c747f 100644 --- a/graph/capacityScaling.cpp +++ b/graph/capacityScaling.cpp @@ -1,5 +1,5 @@ struct edge { - int from, to; + int from, to; ll f, c; }; diff --git a/graph/connect.cpp b/graph/connect.cpp index c38b8bd..b25d844 100644 --- a/graph/connect.cpp +++ b/graph/connect.cpp @@ -23,7 +23,7 @@ struct connect { void eraseEdge(ll id) { if (connected(edges[id].first, edges[id].second) && - lct.query(&lct.nodes[edges[id].first], + lct.query(&lct.nodes[edges[id].first], &lct.nodes[edges[id].second]) == id) { lct.cut(&lct.nodes[edges[id].first], &lct.nodes[id + n]); lct.cut(&lct.nodes[edges[id].second], &lct.nodes[id + n]); diff --git a/graph/cycleCounting.cpp b/graph/cycleCounting.cpp index c3fe457..bf32874 100644 --- a/graph/cycleCounting.cpp +++ b/graph/cycleCounting.cpp @@ -29,11 +29,11 @@ struct cylces { } else { seen[c] = true; paths[c] = cur; - for (auto e : adj[c]) { - if (e.first == p) continue; - cur[e.second].flip(); - findBase(e.first, c, cur); - cur[e.second].flip(); + for (auto [to, id] : adj[c]) { + if (to == p) continue; + cur[id].flip(); + findBase(to, c, cur); + cur[id].flip(); }}} //cycle must be constrcuted from base @@ -43,7 +43,7 @@ struct cylces { for (int i = 0; i < sz(edges); i++) { if (cur[i]) { cur[i] = false; - if (findSet(edges[i].first) == + if (findSet(edges[i].first) == findSet(edges[i].second)) break; unionSets(edges[i].first, edges[i].second); }} diff --git a/graph/dijkstra.cpp b/graph/dijkstra.cpp index 0b821dd..50c9654 100644 --- a/graph/dijkstra.cpp +++ b/graph/dijkstra.cpp @@ -7,15 +7,15 @@ void dijkstra(const vector<vector<path>> &adjlist, int start) { dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { - path front = pq.top(); pq.pop(); - if (front.first > dist[front.second]) continue; // WICHTIG! + auto [dc, c] = pq.top(); pq.pop(); + if (dc > dist[c]) continue; // WICHTIG! - for (path e : adjlist[front.second]) { - ll newDist = front.first + e.first; - if (newDist < dist[e.second]) { - dist[e.second] = newDist; - prev[e.second] = front.second; - pq.emplace(newDist, e.second); + for (auto [dx, x] : adjlist[c]) { + ll newDist = dc + dx; + if (newDist < dist[x]) { + dist[x] = newDist; + prev[x] = c; + pq.emplace(newDist, x); }}} //return dist, prev; } diff --git a/graph/dinicScaling.cpp b/graph/dinicScaling.cpp index 5dc06d6..aecbddc 100644 --- a/graph/dinicScaling.cpp +++ b/graph/dinicScaling.cpp @@ -1,5 +1,5 @@ struct edge { - int from, to; + int from, to; ll f, c; }; @@ -19,7 +19,7 @@ void addEdge(int from, int to, ll c) { bool bfs() { dist.assign(sz(dist), -1); - dist[t] = sz(adjlist) + 1; + dist[t] = sz(adjlist) + 1; q.push(t); while (!q.empty() && dist[s] < 0) { int cur = q.front(); q.pop(); @@ -39,7 +39,7 @@ bool dfs(int v, ll flow) { if (v == t) return true; for (; pt[v] < sz(adjlist[v]); pt[v]++) { int id = adjlist[v][pt[v]], to = edges[id].to; - if (dist[to] == dist[v] + 1 && + if (dist[to] == dist[v] + 1 && edges[id].c - edges[id].f >= flow) { if (dfs(to, flow)) { edges[id].f += flow; diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp index 135c4b0..8d5d6ab 100644 --- a/graph/havelHakimi.cpp +++ b/graph/havelHakimi.cpp @@ -3,17 +3,16 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) { for (int i = 0; i < sz(deg); i++) pq.push({deg[i], i}); vector<vector<int>> adj; while (!pq.empty()) { - auto v = pq.top(); pq.pop(); - if (sz(pq) < v.first) return {}; //impossible + auto [degV, v] = pq.top(); pq.pop(); + if (sz(pq) < degV) return {}; //impossible vector<pair<int, int>> todo; - for (int i = 0; i < v.first; i++) { - auto u = pq.top(); pq.pop(); - adj[v.second].push_back(u.second); - adj[u.second].push_back(v.second); - u.first--; - if (u.first > 0) todo.push_back(u); + for (int i = 0; i < degV; i++) { + auto [degU, v] = pq.top(); pq.pop(); + adj[v].push_back(u); + adj[u].push_back(v); + if (degU > 1) todo.push_back({degU - 1, u}); } for (auto e : todo) pq.push(e); } return adj; -} +} diff --git a/graph/hopcroftKarp.cpp b/graph/hopcroftKarp.cpp index c0eda96..09d27bc 100644 --- a/graph/hopcroftKarp.cpp +++ b/graph/hopcroftKarp.cpp @@ -22,8 +22,8 @@ bool bfs(int n) { bool dfs(int u) { for (int v : adjlist[u]) { if (pairs[v] < 0 || - (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) { - pairs[v] = u; pairs[u] = v; + (dist[pairs[v]] > dist[u] && dfs(pairs[v]))) { + pairs[v] = u; pairs[u] = v; return true; }} dist[u] = -1; diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp index 46d444c..27f6b34 100644 --- a/graph/minCostMaxFlow.cpp +++ b/graph/minCostMaxFlow.cpp @@ -12,7 +12,7 @@ struct MinCostFlow { const int s, t; ll maxflow, mincost; - MinCostFlow(int n, int source, int target) : + MinCostFlow(int n, int source, int target) : adjlist(n), s(source), t(target) {}; void addedge(int u, int v, ll c, ll cost) { diff --git a/graph/pushRelabel2.cpp b/graph/pushRelabel2.cpp index f4a66e8..b8ec3e9 100644 --- a/graph/pushRelabel2.cpp +++ b/graph/pushRelabel2.cpp @@ -1,7 +1,7 @@ constexpr ll inf = 1ll<<60; struct edge { - int from, to; + int from, to; ll f, c; }; diff --git a/graph/pushRelabel3.cpp b/graph/pushRelabel3.cpp index bdbe0a5..1a0af81 100644 --- a/graph/pushRelabel3.cpp +++ b/graph/pushRelabel3.cpp @@ -1,5 +1,5 @@ struct edge { - int from, to; + int from, to; ll f, c; }; diff --git a/java/output.java b/java/output.java index e43cb06..f046731 100644 --- a/java/output.java +++ b/java/output.java @@ -2,6 +2,6 @@ PrintWriter out = new PrintWriter(new BufferedWriter( new OutputStreamWriter(new FileOutputStream( FileDescriptor.out), StandardCharsets.UTF_8), 4096)); -out.println("blub" + "a" + "b"); //zeile Ausgeben +out.println("blub" + "a" + "b"); //zeile Ausgeben out.println(String.format("%d %s", 5, "a")) // wie printf out.close();//WICHTIG! diff --git a/latexHeaders/code.sty b/latexHeaders/code.sty index 1e67ead..535a380 100644 --- a/latexHeaders/code.sty +++ b/latexHeaders/code.sty @@ -93,7 +93,7 @@ \begin{btHighlight}[#1]\bgroup\aftergroup\bt@HL@endenv% } \def\bt@HL@endenv{% - \end{btHighlight}% + \end{btHighlight}% \egroup% } \newcommand{\bt@HL@box}[2][]{% diff --git a/math/longestIncreasingSubsequence.cpp b/math/longestIncreasingSubsequence.cpp index c2c5f3e..99bb141 100644 --- a/math/longestIncreasingSubsequence.cpp +++ b/math/longestIncreasingSubsequence.cpp @@ -2,7 +2,7 @@ vector<int> lis(vector<int> &seq) { int n = sz(seq), lisLength = 0, lisEnd = 0; vector<int> L(n), L_id(n), parents(n); for (int i = 0; i < n; i++) { - int pos = upper_bound(L.begin(), L.begin() + lisLength, + int pos = upper_bound(L.begin(), L.begin() + lisLength, seq[i]) - L.begin(); L[pos] = seq[i]; L_id[pos] = i; diff --git a/math/math.tex b/math/math.tex index e640814..235c508 100644 --- a/math/math.tex +++ b/math/math.tex @@ -38,7 +38,7 @@ %\end{multicols} %\vspace{-2.75em} \begin{itemize} - \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! + \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! \end{itemize} \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} @@ -165,8 +165,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/linearSieve.cpp} \textbf{\textsc{Möbius} Funtkion:} \begin{itemize} - \item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat - \item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat + \item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat + \item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat \item $\mu(n)=0$, falls $n$ nicht quadratfrei ist \end{itemize} @@ -293,7 +293,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: $$\renewcommand\arraystretch{1.5} \setlength\arraycolsep{3pt} - \begin{pmatrix} + \begin{pmatrix} c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\ 1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\ 0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\ @@ -301,7 +301,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: 0 & \smash{\cdots} & 0 & 1 & 0 \\ \end{pmatrix}^k \times~~ - \begin{pmatrix} + \begin{pmatrix} f(n-1) \\ f(n-2) \\ \smash{\vdots} \\ @@ -309,7 +309,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: f(0) \\ \end{pmatrix} ~~=~~ - \begin{pmatrix} + \begin{pmatrix} f(n-1+k) \\ f(n-2+k) \\ \smash{\vdots} \\ @@ -364,7 +364,7 @@ Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu g\left(X\right) := \min\left\{ \mathbb{Z}_0^+ \setminus \left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\} -\right\} +\right\} \] $X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$. @@ -372,7 +372,7 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \subsection{Kombinatorik} \paragraph{Wilsons Theorem} -A number $n$ is prime if and only if +A number $n$ is prime if and only if $(n-1)!\equiv -1\bmod{n}$.\\ ($n$ is prime if and only if $(m-1)!\cdot(n-m)!\equiv(-1)^m\bmod{n}$ for all $m$ in $\{1,\dots,n\}$) \begin{align*} diff --git a/math/millerRabin.cpp b/math/millerRabin.cpp index e4d2f6e..c6a782f 100644 --- a/math/millerRabin.cpp +++ b/math/millerRabin.cpp @@ -1,5 +1,5 @@ constexpr ll bases32[] = {2, 7, 61}; -constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, +constexpr ll bases64[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; bool isPrime(ll n) { if (n < 2 || n % 2 == 0) return n == 2; diff --git a/math/polynomial.cpp b/math/polynomial.cpp index f7d9a89..44f6207 100644 --- a/math/polynomial.cpp +++ b/math/polynomial.cpp @@ -62,4 +62,4 @@ struct poly { s.trim(); r.trim(); return {s, r}; } -}; +}; diff --git a/math/primitiveRoot.cpp b/math/primitiveRoot.cpp index 7973c24..464bdb3 100644 --- a/math/primitiveRoot.cpp +++ b/math/primitiveRoot.cpp @@ -1,12 +1,12 @@ bool isPrimitive(ll g, ll n, ll phi, map<ll, int> phiFacs) { if (g == 1) return n == 2; - for (auto& f : phiFacs) - if (1 == powMod(g, phi / f.first, n)) return false; + for (auto [f, _] : phiFacs) + if (powMod(g, phi / f, n) == 1) return false; return true; } bool isPrimitive(ll g, ll n) { - ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 + ll phin = phi(n); //isPrime(n) => phi(n) = n - 1 map<ll, int> phiFacs; factor(phin, phiFacs); return isPrimitive(g, n, phin, phiFacs); diff --git a/math/tables/series.tex b/math/tables/series.tex index f7e7839..3042781 100644 --- a/math/tables/series.tex +++ b/math/tables/series.tex @@ -3,7 +3,7 @@ \multicolumn{4}{|c|}{Reihen} \\ \hline $\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ & - $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ & + $\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ & $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ & $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ \grayhline diff --git a/math/transforms/fftMul.cpp b/math/transforms/fftMul.cpp index c8de19a..a1205f6 100644 --- a/math/transforms/fftMul.cpp +++ b/math/transforms/fftMul.cpp @@ -11,4 +11,4 @@ vector<cplx> mul(vector<cplx>& a, vector<cplx>& b) { d[i] = x * y; } return fft(d, true); -} +} diff --git a/other/other.tex b/other/other.tex index b0e480b..9c71a3b 100644 --- a/other/other.tex +++ b/other/other.tex @@ -84,7 +84,7 @@ \item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden. Nummeriere die Personen mit $0, 1, \ldots, n-1$. Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$. - Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$. + Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$. \end{description} \lstinputlisting{other/josephusK.cpp} \textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!} @@ -200,7 +200,7 @@ Berechnung: Maximales Matching in bipartitem Graphen. Dupliziere jedes $s \in S$ in $u_s$ und $v_s$. Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu. - Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. + Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Anitkette zu finden. \item \textbf{\textsc{Turan}'s-Theorem:} Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist: diff --git a/other/stuff.cpp b/other/stuff.cpp index 4462c3b..e3bbed6 100644 --- a/other/stuff.cpp +++ b/other/stuff.cpp @@ -15,7 +15,7 @@ set<point2, decltype(comp)> set1(comp); -D_GLIBCXX_DEBUG #define _GLIBCXX_DEBUG -// 128-Bit Integer/Float. Muss zum Einlesen/Ausgeben +// 128-Bit Integer/Float. Muss zum Einlesen/Ausgeben // in einen int oder long long gecastet werden. __int128, __float128 diff --git a/string/ahoCorasick.cpp b/string/ahoCorasick.cpp index c83f9c3..9ffa6c9 100644 --- a/string/ahoCorasick.cpp +++ b/string/ahoCorasick.cpp @@ -4,7 +4,7 @@ struct AhoCorasick { struct vert { int suffix, exit, character, parent; vector<int> nxt, patterns; - vert(int c, int p) : suffix(-1), exit(-1), + vert(int c, int p) : suffix(-1), exit(-1), character(c), nxt(ALPHABET_SIZE, -1), parent(p) {} }; vector<vert> aho; @@ -28,7 +28,7 @@ struct AhoCorasick { 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), + else aho[v].suffix = go(getSuffix(aho[v].parent), aho[v].character); } return aho[v].suffix; diff --git a/string/duval.cpp b/string/duval.cpp index 6d80e95..bf36cce 100644 --- a/string/duval.cpp +++ b/string/duval.cpp @@ -15,7 +15,7 @@ vector<pair<int, int>> duval(const string& s) { int minrotation(const string& s) { auto parts = duval(s+s); - for (auto e : parts) { - if (e.first < sz(s) && e.second >= sz(s)) { - return e.first; + for (auto [l, r] : parts) { + if (l < sz(s) && r >= sz(s)) { + return l; }}} diff --git a/string/lyndon.cpp b/string/lyndon.cpp index 6a131a5..858c3db 100644 --- a/string/lyndon.cpp +++ b/string/lyndon.cpp @@ -1,5 +1,5 @@ bool next(string& s, int n, char mi = '0', char ma = '1') { - for (ll i = sz(s), j = sz(s); i < n; i++) + for (int i = sz(s), j = sz(s); i < n; i++) s.push_back(s[i % j]); while(!s.empty() && s.back() == ma) s.pop_back(); if (s.empty()) { diff --git a/string/rollingHashCf.cpp b/string/rollingHashCf.cpp index d1b8893..9608aff 100644 --- a/string/rollingHashCf.cpp +++ b/string/rollingHashCf.cpp @@ -4,7 +4,7 @@ struct Hasher { vector<ll> power = {1}, pref = {0}; ll m, q; char c; - Hasher(const string& s, ll m, ll q, char c) : + Hasher(const string& s, ll m, ll q, char c) : m(m), q(q), c(c) { for (char x : s) { power.push_back(power.back() * q % m); diff --git a/string/string.tex b/string/string.tex index 6b83e2c..a09d7f8 100644 --- a/string/string.tex +++ b/string/string.tex @@ -54,7 +54,7 @@ \begin{enumerate} \item mit \code{addString(pattern, idx);} Patterns hinzufügen. \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 mit \code{state = getExit(state)} den exit Kanten folgen bis \code{state == 0} \item dabei mit \code{aho[state].patterns} die Matches zählen \end{enumerate} \sourcecode{string/ahoCorasick.cpp} diff --git a/string/suffixArray.cpp b/string/suffixArray.cpp index df6259a..720148c 100644 --- a/string/suffixArray.cpp +++ b/string/suffixArray.cpp @@ -9,11 +9,11 @@ struct SuffixArray { for (int i = 0; i < n; i++) P[0][i] = s[i]; for (step = 1, count = 1; count < n; step++, count *= 2) { for (int i = 0; i < n; i++) - L[i] = {{P[step-1][i], + L[i] = {{P[step-1][i], i+count < n ? P[step-1][i+count] : -1}, i}; sort(all(L)); for (int i = 0; i < n; i++) { - P[step][L[i].second] = + P[step][L[i].second] = i > 0 && L[i].first == L[i-1].first ? P[step][L[i-1].second] : i; }} diff --git a/string/suffixAutomaton.cpp b/string/suffixAutomaton.cpp index 4d05b6e..c6205da 100644 --- a/string/suffixAutomaton.cpp +++ b/string/suffixAutomaton.cpp @@ -2,7 +2,7 @@ constexpr char MIN_CHAR = 'a'; constexpr ll ALPHABET_SIZE = 26; struct SuffixAutomaton { struct State { - int length, link; + int length, link; vector<int> next; State() : next(ALPHABET_SIZE) {} }; Binary files differdiff --git a/tests/test.tex b/tests/test.tex index 95f1645..1640f4e 100644 --- a/tests/test.tex +++ b/tests/test.tex @@ -1,4 +1,4 @@ -\section{Tests} +\section{Tests} Dieser Abschnitt enthält lediglich Dinge die während der Practicesession getestet werden sollten! \subsection{GCC} |