diff options
Diffstat (limited to 'content')
62 files changed, 610 insertions, 686 deletions
diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex index a0eea64..4bbe507 100644 --- a/content/datastructures/datastructures.tex +++ b/content/datastructures/datastructures.tex @@ -52,7 +52,7 @@ \method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)} \method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)} \end{methods} - \sourcecode{datastructures/treap2.cpp} + \sourcecode{datastructures/treap.cpp} \end{algorithm} \begin{algorithm}{Range Minimum Query} diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index 2bd67a6..7148e31 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -1,22 +1,22 @@ struct Line { - mutable ll m, b, p; + mutable ll m, c, p; 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) - ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} +struct HullDynamic : multiset<Line, less<>> { // max über Geraden + // (for doubles, use INF = 1/.0, div(a,c) = a/c) + ll div(ll a, ll c) {return a / c - ((a ^ c) < 0 && a % c);} bool isect(iterator x, iterator y) { if (y == end()) {x->p = INF; return false;} - if (x->m == y->m) x->p = x->b > y->b ? INF : -INF; - else x->p = div(y->b - x->b, x->m - y->m); + if (x->m == y->m) x->p = x->c > y->c ? INF : -INF; + else x->p = div(y->c - x->c, x->m - y->m); return x->p >= y->p; } - void add(ll m, ll b) { - auto x = insert({m, b, 0}); + void add(ll m, ll c) { + auto x = insert({m, c, 0}); while (isect(x, next(x))) erase(next(x)); if (x != begin()) { --x; @@ -29,6 +29,6 @@ struct HullDynamic : multiset<Line, less<>> { ll query(ll x) { auto l = *lower_bound(x); - return l.m * x + l.b; + return l.m * x + l.c; } }; diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp index f66778e..1318ca7 100644 --- a/content/datastructures/lichao.cpp +++ b/content/datastructures/lichao.cpp @@ -8,13 +8,13 @@ struct Fun { // Default: Linear function. Change as needed. // Default: Computes min. Change lines with comment for max. struct Lichao { - static constexpr Fun id = {0, inf}; // {0, -inf} + 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) {} + 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){ + while (i < 2 * cap) { int m = (l+r)/2; if (m >= n) {r = m; i = 2*i; continue;} Fun &g = seg[i]; @@ -26,7 +26,7 @@ struct Lichao { 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){ + 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); @@ -36,7 +36,7 @@ struct Lichao { } ll _query(int x) { - ll ans = inf; // -inf + ll ans = INF; // -INF for (int i = x + cap; i > 0; i /= 2) { ans = min(ans, seg[i](x)); // max } diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index e7b9b3e..2bdeccf 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -16,7 +16,7 @@ struct Envelope { ls.pop_back(); } ls.push_back({m, b}); - ptr = min(ptr, sz(ls) - 1); + ptr = min(ptr, (int)sz(ls) - 1); } ll query(ll x) { diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp index d00b635..734bf91 100644 --- a/content/datastructures/pbds.cpp +++ b/content/datastructures/pbds.cpp @@ -15,10 +15,10 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag, T.order_of_key(x); // number of elements strictly less than x auto it = T.find_by_order(k); // k-th element +constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd template<typename T> struct chash { - static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd size_t operator()(T o) const { - return __builtin_bswap64(hash<T>()(o) * C); + return __builtin_bswap64(hash<T>()(o) * RNG); }}; template<typename K, typename V> using hashMap = gp_hash_table<K, V, chash<K>>; diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp index 4093cdc..f26680d 100644 --- a/content/datastructures/persistent.cpp +++ b/content/datastructures/persistent.cpp @@ -4,15 +4,15 @@ struct persistent { vector<pair<int, T>> data;
persistent(int& time, T value = {})
- : time(time), data(1, {time, value}) {}
+ : time(time), data(1, {2*time, value}) {}
T get(int t) {
- return prev(upper_bound(all(data), pair{t+1, T{}}))->second;
+ return prev(upper_bound(all(data),pair{2*t+1, T{}}))->second;
}
int set(T value) {
- time += 2;
- data.push_back({time, value});
+ time++;
+ data.push_back({2*time, value});
return time;
}
};
diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp index 60d8b17..8326700 100644 --- a/content/datastructures/persistentArray.cpp +++ b/content/datastructures/persistentArray.cpp @@ -10,8 +10,8 @@ struct persistentArray { T get(int p, int t) {return data[p].get(t);}
int set(int p, T value) {
- mods.push_back({p, time});
- return data[p].set(value);
+ mods.push_back({p, data[p].set(value)});
+ return mods.back().second;
}
void reset(int t) {
diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp index c96e36a..c5a60e9 100644 --- a/content/datastructures/treap.cpp +++ b/content/datastructures/treap.cpp @@ -1,79 +1,79 @@ -struct node { - int key, prio, left, right, size; - node(int key, int prio) : key(key), prio(prio), left(-1), - right(-1), size(1) {}; -}; +mt19937 rng(0xc4bd5dad); +struct Treap { + struct Node { + ll val; + int prio, size = 1, l = -1, r = -1; + Node(ll x) : val(x), prio(rng()) {} + }; -vector<node> treap; + vector<Node> treap; + int root = -1; -int getSize(int root) { - return root < 0 ? 0 : treap[root].size; -} + int getSize(int v) { + return v < 0 ? 0 : treap[v].size; + } -void update(int root) { - if (root < 0) return; - treap[root].size = 1 + getSize(treap[root].left) - + getSize(treap[root].right); -} + void upd(int v) { + if (v < 0) return; + auto& V = treap[v]; + V.size = 1 + getSize(V.l) + getSize(V.r); + // Update Node Code + } -pair<int, int> split(int root, int minKeyRight) { - if (root < 0) return {-1, -1}; - if (treap[root].key >= minKeyRight) { - auto leftSplit = split(treap[root].left, minKeyRight); - treap[root].left = leftSplit.second; - update(root); - leftSplit.second = root; - return leftSplit; - } else { - auto rightSplit = split(treap[root].right, minKeyRight); - treap[root].right = rightSplit.first; - update(root); - rightSplit.first = root; - return rightSplit; -}} + void push(int v) { + if (v < 0) return; + //auto& V = treap[v]; + //if (V.lazy) { + // Lazy Propagation Code + // if (V.l >= 0) treap[V.l].lazy = true; + // if (V.r >= 0) treap[V.r].lazy = true; + // V.lazy = false; + //} + } -int merge (int left, int right) { - if (left < 0) return right; - if (right < 0) return left; - if (treap[left].prio < treap[right].prio) { //min priority heap - treap[left].right = merge(treap[left].right, right); - update(left); - return left; - } else { - treap[right].left = merge(left, treap[right].left); - update(right); - return right; -}} + pair<int, int> split(int v, int k) { + if (v < 0) return {-1, -1}; + auto& V = treap[v]; + push(v); + if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k) + auto [left, right] = split(V.l, k); + V.l = right; + upd(v); + return {left, v}; + } else { + // and only "k" + auto [left, right] = split(V.r, k - getSize(V.l) - 1); + V.r = left; + upd(v); + return {v, right}; + }} -//insert values with high priority first -int insert(int root, int key, int prio) { - int next = sz(treap); - treap.emplace_back(key, prio); - auto t = split(root, key); - //returns new root - return merge(merge(t.first, next), t.second); -} + int merge(int left, int right) { + if (left < 0) return right; + if (right < 0) return left; + if (treap[left].prio < treap[right].prio) { + push(left); + treap[left].r = merge(treap[left].r, right); + upd(left); + return left; + } else { + push(right); + treap[right].l = merge(left, treap[right].l); + upd(right); + return right; + }} -int remove(int root, int key) { - if (root < 0) return -1; - if (key < treap[root].key) { - treap[root].left = remove(treap[root].left, key); - update(root); - return root; - } else if (key > treap[root].key) { - treap[root].right = remove(treap[root].right, key); - update(root); - return root; - } else { //check prio? - return merge(treap[root].left, treap[root].right); -}} + void insert(int i, ll val) { // and i = val + auto [left, right] = split(root, i); + treap.emplace_back(val); + left = merge(left, sz(treap) - 1); + root = merge(left, right); + } -int kth(int root, int k) { - if (root < 0) return -1; - int leftSize = getSize(treap[root].left); - if (k < leftSize) return kth(treap[root].left, k); - else if (k > leftSize) { - return kth(treap[root].right, k - 1 - leftSize); + void remove(int i, int count = 1) { + auto [left, t_right] = split(root, i); + auto [middle, right] = split(t_right, count); + root = merge(left, right); } - return root; -} + // for query use remove and read middle BEFORE remerging +}; diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp deleted file mode 100644 index e40da0d..0000000 --- a/content/datastructures/treap2.cpp +++ /dev/null @@ -1,79 +0,0 @@ -mt19937 rng(0xc4bd5dad); -struct Treap { - struct Node { - ll val; - int prio, size = 1, l = -1, r = -1; - Node(ll x): val(x), prio(rng()) {} - }; - - vector<Node> treap; - int root = -1; - - int getSize(int v) { - return v < 0 ? 0 : treap[v].size; - } - - void upd(int v) { - if (v < 0) return; - auto &V = treap[v]; - V.size = 1 + getSize(V.l) + getSize(V.r); - // Update Node Code - } - - void push(int v) { - if (v < 0) return; - //auto &V = treap[v]; - //if (V.lazy) { - // Lazy Propagation Code - // if (V.l >= 0) treap[V.l].lazy = true; - // if (V.r >= 0) treap[V.r].lazy = true; - // V.lazy = false; - //} - } - - pair<int, int> split(int v, int k) { - if (v < 0) return {-1, -1}; - auto &V = treap[v]; - push(v); - if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k) - auto [left, right] = split(V.l, k); - V.l = right; - upd(v); - return {left, v}; - } else { - // and only "k" - auto [left, right] = split(V.r, k - getSize(V.l) - 1); - V.r = left; - upd(v); - return {v, right}; - }} - - int merge(int left, int right) { - if (left < 0) return right; - if (right < 0) return left; - if (treap[left].prio < treap[right].prio) { - push(left); - treap[left].r = merge(treap[left].r, right); - upd(left); - return left; - } else { - push(right); - treap[right].l = merge(left, treap[right].l); - upd(right); - return right; - }} - - void insert(int i, ll val) { // and i = val - auto [left, right] = split(root, i); - treap.emplace_back(val); - left = merge(left, ssize(treap) - 1); - root = merge(left, right); - } - - void remove(int i, int count = 1) { - auto [left, t_right] = split(root, i); - auto [middle, right] = split(t_right, count); - root = merge(left, right); - } - // for query use remove and read middle BEFORE remerging -}; diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp index 6d89e05..1173924 100644 --- a/content/geometry/convexHull.cpp +++ b/content/geometry/convexHull.cpp @@ -11,8 +11,8 @@ vector<pt> convexHull(vector<pt> pts){ while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--; h[k++] = *it; }}; - half(all(pts), 1);// Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle. + half(all(pts), 1); // Untere Hülle. + half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. h.resize(k); return h; } diff --git a/content/geometry/formulas3d.cpp b/content/geometry/formulas3d.cpp index dee3ce8..63de2ce 100644 --- a/content/geometry/formulas3d.cpp +++ b/content/geometry/formulas3d.cpp @@ -26,23 +26,23 @@ int ccw(pt3 a, pt3 b, pt3 c, pt3 p) { return (orien > EPS) - (orien < -EPS); } -// Entfernung von Punkt p zur Ebene a,b,c. +// Entfernung von Punkt p zur Ebene a, b, c. double distToPlane(pt3 a, pt3 b, pt3 c, pt3 p) { - pt3 n = cross(b-a, c-a); - return (abs(dot(n, p)) - dot(n, a)) / abs(n); + pt3 n = cross(b - a, c - a); + return abs(dot(n, a - p)) / abs(n); } -// Liegt p in der Ebene a,b,c? +// Liegt p in der Ebene a, b, c? bool pointOnPlane(pt3 a, pt3 b, pt3 c, pt3 p) { return ccw(a, b, c, p) == 0; } -// Schnittpunkt von der Grade a-b und der Ebene c,d,e +// Schnittpunkt von der Grade a-b und der Ebene c, d, e // die Grade darf nicht parallel zu der Ebene sein! pt3 linePlaneIntersection(pt3 a, pt3 b, pt3 c, pt3 d, pt3 e) { - pt3 n = cross(d-c, e-c); - pt3 d = b - a; - return a - d * (dot(n, a) - dot(n, c)) / dot(n, d); + pt3 n = cross(d - c, e - c); + pt3 dir = b - a; + return a + dir * dot(n, c - a) / dot(n, dir); } // Abstand zwischen der Grade a-b und c-d diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index 3509e0e..02c71e3 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -1,4 +1,4 @@ -constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP +constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP bool left(pt p) {return real(p) < 0 || (real(p) == 0 && imag(p) < 0);} @@ -27,22 +27,22 @@ struct hp { if (ort == 0) return cross(from, to, a.from) < 0; return cross(b.dir(), a.dir()) * ort > 0; } - ll y = cross(a.dir(), b.dir()); - ll z = cross(b.from - a.from, b.dir()); - ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b - // check if i is outside/right of x - return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0; + ll x = cross(a.dir(), b.dir()); + ll y = cross(b.from - a.from, b.dir()); + ptl i = mul(x, a.from) + mul(y, a.dir()); //intersect a and b + // check if i is outside/right of this + return imag(conj(mul(sgn(x),dir()))*(i-mul(x,from))) < 0; } }; constexpr ll lim = 2e9+7; deque<hp> intersect(vector<hp> hps) { - hps.push_back(hp(pt{lim+1,-1})); - hps.push_back(hp(pt{lim+1,1})); + hps.push_back(hp(pt{lim + 1, -1})); + hps.push_back(hp(pt{lim + 1, 1})); sort(all(hps)); - deque<hp> dq = {hp(pt{-lim, 1})}; + deque<hp> dq = {hp(pt{-lim - 1, 1})}; for (auto x : hps) { while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2])) dq.pop_back(); @@ -60,7 +60,7 @@ deque<hp> intersect(vector<hp> hps) { while (sz(dq) > 2 && dq[0].check(dq.end()[-1], dq.end()[-2])) dq.pop_back(); - while (sz(dq) > 2 && dq.end()[-1].check(dq[0], dq[1])) + while (sz(dq) > 2 && dq.back().check(dq[0], dq[1])) dq.pop_front(); if (sz(dq) < 3) return {}; diff --git a/content/geometry/lines.cpp b/content/geometry/lines.cpp index 95536a4..36de1db 100644 --- a/content/geometry/lines.cpp +++ b/content/geometry/lines.cpp @@ -1,10 +1,10 @@ struct line { - double a, b, c; // ax + by + c = 0; vertikale Line: b = 0, sonst: b = 1 - line(pt p, pt q) : a(-imag(q-p)), b(real(q-p)), c(cross({b, -a},p)) {} + double a, b, c; // ax + by + c = 0; vertikale Gerade: b = 0 + line(pt p, pt q) : a(imag(p-q)), b(real(q-p)), c(cross({-b, a}, p)) {} }; -line pointsToLine(pt p1, pt p2) { - line l; +line pointsToLine(pt p1, pt p2) { // vertikale Gerade: b = 1 oder b = 0 + line l(0, 0); if (abs(real(p1 - p2)) < EPS) { l.a = 1; l.b = 0.0; l.c = -real(p1); } else { @@ -15,19 +15,19 @@ line pointsToLine(pt p1, pt p2) { return l; } -bool parallel(line l1, line l2) { +bool parallel(line l1, line l2) { // braucht b in {0, 1} return (abs(l1.a - l2.a) < EPS) && (abs(l1.b - l2.b) < EPS); } -bool same(line l1, line l2) { +bool same(line l1, line l2) { // braucht b in {0, 1} return parallel(l1, l2) && (abs(l1.c - l2.c) < EPS); } -bool intersect(line l1, line l2, pt& p) { +bool intersect(line l1, line l2, pt& res) { // braucht b in {0, 1} if (parallel(l1, l2)) return false; double y, x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b); if (abs(l1.b) > EPS) y = -(l1.a * x + l1.c); else y = -(l2.a * x + l2.c); - p = {x, y}; + res = {x, y}; return true; } diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp index 1e21cba..ddab554 100644 --- a/content/geometry/linesAndSegments.cpp +++ b/content/geometry/linesAndSegments.cpp @@ -5,7 +5,7 @@ bool pointOnLine(pt a, pt b, pt p) { // Test auf Linienschnitt zwischen a-b und c-d. (nicht identisch) bool lineIntersection(pt a, pt b, pt c, pt d) { - return abs(cross(a - b, c - d)) < EPS; + return abs(cross(a - b, c - d)) > EPS; } // Berechnet den Schnittpunkt der Graden a-b und c-d. diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index 3178290..064d81f 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -29,7 +29,7 @@ bool inside(pt p, const vector<pt>& poly) { bool in = false; for (int i = 0; i + 1 < sz(poly); i++) { pt a = poly[i], b = poly[i + 1]; - if (pointOnLineSegment(a, b, p)) return false; + if (pointOnSegment(a, b, p)) return false; if (real(a) > real(b)) swap(a,b); if (real(a) <= real(p) && real(p) < real(b) && cross(p, a, b) < 0) { diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp index 4262ddc..afc01b2 100644 --- a/content/geometry/segmentIntersection.cpp +++ b/content/geometry/segmentIntersection.cpp @@ -18,8 +18,8 @@ struct event { int id, type; bool operator<(const event& o) const { if (real(p) != real(o.p)) return real(p) < real(o.p); - if (type != o.type) return type > o.type; - return imag(p) < imag(o.p); + if (imag(p) != imag(o.p)) return imag(p) < imag(o.p); + return type > o.type; } }; @@ -29,7 +29,7 @@ bool lessPT(const pt& a, const pt& b) { } bool intersect(const seg& a, const seg& b) { - return lineSegmentIntersection(a.a, a.b, b.a, b.b); + return segmentIntersection(a.a, a.b, b.a, b.b); //@\sourceref{geometry/linesAndSegments.cpp}@ } pair<int, int> intersect(vector<seg>& segs) { diff --git a/content/geometry/spheres.cpp b/content/geometry/spheres.cpp index ec22262..d34bca9 100644 --- a/content/geometry/spheres.cpp +++ b/content/geometry/spheres.cpp @@ -1,3 +1,16 @@ +// 3D Punkt in kartesischen Koordinaten. +struct point{ + double x, y, z; + point() {} + point(double x, double y, double z) : x(x), y(y), z(z) {} + point(double lat, double lon) { + lat *= PI / 180.0; lon *= PI / 180.0; + x = cos(lat) * sin(lon); + y = cos(lat) * cos(lon); + z = sin(lat); + } +}; + // Great Circle Distance mit Längen- und Breitengrad. double gcDist(double pLat, double pLon, double qLat, double qLon, double radius) { @@ -11,19 +24,6 @@ double gcDist(double pLat, double pLon, } // Great Circle Distance mit kartesischen Koordinaten. -double gcDist(point p, point q) { +double gcDist(point p, point q) { // radius = 1 return acos(p.x * q.x + p.y * q.y + p.z * q.z); -} - -// 3D Punkt in kartesischen Koordinaten. -struct point{ - double x, y, z; - point() {} - point(double x, double y, double z) : x(x), y(y), z(z) {} - point(double lat, double lon) { - lat *= PI / 180.0; lon *= PI / 180.0; - x = cos(lat) * sin(lon); - y = cos(lat) * cos(lon); - z = sin(lat); - } -}; +}
\ No newline at end of file diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index 6470232..eee5082 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -27,5 +27,5 @@ auto bitonicTSP() { (lt.back() == 1 ? lt : ut).push_back(0); reverse(all(lt)); lt.insert(lt.end(), all(ut)); - return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position. + return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp index 8b6e6c5..cacfb9c 100644 --- a/content/graph/bitonicTSPsimple.cpp +++ b/content/graph/bitonicTSPsimple.cpp @@ -23,5 +23,5 @@ auto bitonicTSP() { rl.push_back(v); p2 = v; }} lr.insert(lr.end(), rl.rbegin(), rl.rend()); - return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position. + return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/connect.cpp b/content/graph/connect.cpp index ffcd6c2..7940b37 100644 --- a/content/graph/connect.cpp +++ b/content/graph/connect.cpp @@ -10,7 +10,7 @@ struct connect { } void addEdge(int u, int v, int id) { - lct.nodes[id + n] = LCT::Node(id + n, id + n); + lct.nodes[id + n] = LCT::Node(id + n, id); edges[id] = {u, v}; if (connected(u, v)) { int old = lct.query(&lct.nodes[u], &lct.nodes[v]); diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp new file mode 100644 index 0000000..2e58a2d --- /dev/null +++ b/content/graph/dinic.cpp @@ -0,0 +1,55 @@ +struct Edge { + int to, rev; + ll f, c; +}; + +vector<vector<Edge>> adj; +int s, t; +vector<int> pt, dist; + +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}); +} + +bool bfs() { + dist.assign(sz(adj), -1); + dist[s] = 0; + queue<int> q({s}); + while (!q.empty() && dist[t] < 0) { + int v = q.front(); q.pop(); + for (Edge& e : adj[v]) { + if (dist[e.to] < 0 && e.c - e.f > 0) { + dist[e.to] = dist[v] + 1; + q.push(e.to); + }}} + return dist[t] >= 0; +} + +ll dfs(int v, ll flow = INF) { + if (v == t || flow == 0) return flow; + for (; pt[v] < sz(adj[v]); pt[v]++) { + Edge& e = adj[v][pt[v]]; + if (dist[e.to] != dist[v] + 1) continue; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; + }} + return 0; +} + +ll maxFlow(int source, int target) { + s = source, t = target; + ll flow = 0; + while (bfs()) { + pt.assign(sz(adj), 0); + ll cur; + do { + cur = dfs(s); + flow += cur; + } while (cur > 0); + } + return flow; +} diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index f4e833a..0974b78 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -26,17 +26,18 @@ bool bfs(ll lim) { return dist[t] >= 0; } -bool dfs(int v, ll flow) { - if (v == t) return true; +ll dfs(int v, ll flow) { + if (v == t || flow == 0) return flow; for (; pt[v] < sz(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; - if (e.c - e.f >= flow && dfs(e.to, flow)) { - e.f += flow; - adj[e.to][e.rev].f -= flow; - return true; + ll cur = dfs(e.to, min(e.c - e.f, flow)); + if (cur > 0) { + e.f += cur; + adj[e.to][e.rev].f -= cur; + return cur; }} - return false; + return 0; } ll maxFlow(int source, int target) { @@ -45,7 +46,11 @@ ll maxFlow(int source, int target) { for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { pt.assign(sz(adj), 0); - while (dfs(s, lim)) flow += lim; + ll cur; + do { + cur = dfs(s, lim); + flow += cur; + } while (cur > 0); }} return flow; } diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp index 73a9eae..ec36026 100644 --- a/content/graph/pushRelabel.cpp +++ b/content/graph/pushRelabel.cpp @@ -29,7 +29,7 @@ ll maxFlow(int s, int t) { cur.assign(n, 0); H.assign(n, 0); H[s] = n; - ec[t] = 1;//never set t to active... + 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); diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 4c6a748..379c839 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -1,62 +1,48 @@ -// 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 +using W = ll; // edge weight type +vector<vector<pair<int, W>>> adj; + struct Reroot { - using T = ll; + using T = ll; // dp type - // 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) {} + static constexpr T E = 0; // neutral element + T takeChild(int v, int c, W w, T x) {} // move child along edge + static T comb(T x, T y) {} + T fin(int v, T x) {} // add v to own dp value x - 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)); + T dfs0(int v, int from = -1) { + T val = E; + for (auto [u, w] : adj[v]) { + if (u == from) continue; + val = comb(val, takeChild(v, u, w, dfs0(u, v))); } - return dp[v] = fin(dp[v], v); + return dp[v] = fin(v, val); } - 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); + void dfs1(int v, int from = -1) { + vector<T> pref = {E}; + for (auto [u, w] : adj[v]) { + pref.push_back(takeChild(v, u, w, dp[u])); } - 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); + auto suf = pref; + partial_sum(all(pref), pref.begin(), comb); + exclusive_scan(suf.rbegin(), suf.rend(), + suf.rbegin(), E, comb); + + for (int i = 0; i < sz(adj[v]); i++) { + auto [u, w] = adj[v][i]; + if (u == from) continue; + dp[v] = fin(v, comb(pref[i], suf[i + 1])); + dfs1(u, v); } - return res; + dp[v] = fin(v, suf[0]); + } + + auto solve() { + dp.assign(sz(adj), E); + dfs0(0); + dfs1(0); + return dp; } }; diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index ac9a40b..32f1099 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -1,11 +1,12 @@ -vector<vector<int>> adj, sccs; -int counter; +vector<vector<int>> adj; +int counter, sccCounter; vector<bool> inStack; vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { int old = low[v] = counter++; - s.push_back(v); inStack[v] = true; + s.push_back(v); + inStack[v] = true; for (auto u : adj[v]) { if (low[u] < 0) visit(u); @@ -13,20 +14,20 @@ void visit(int v) { } if (old == low[v]) { - sccs.push_back({}); + sccCounter++; for (int u = -1; u != v;) { - u = s.back(); s.pop_back(); inStack[u] = false; - idx[u] = sz(sccs) - 1; - sccs.back().push_back(u); + u = s.back(); + s.pop_back(); + inStack[u] = false; + idx[u] = sccCounter - 1; }}} void scc() { inStack.assign(sz(adj), false); low.assign(sz(adj), -1); idx.assign(sz(adj), -1); - sccs.clear(); - counter = 0; + counter = sccCounter = 0; for (int i = 0; i < sz(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp index 27d2d6c..6233b27 100644 --- a/content/graph/virtualTree.cpp +++ b/content/graph/virtualTree.cpp @@ -3,13 +3,13 @@ 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, n = sz(ind); i < n - 1; i++) { - ind.push_back(lca(ind[i], ind[i + 1])); + for (int i = 1, n = sz(ind); i < n; i++) { + ind.push_back(lca(ind[i - 1], ind[i])); } sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); ind.erase(unique(all(ind)), ind.end()); - int n = ind.size(); + int n = sz(ind); vector<vector<int>> tree(n); vector<int> st = {0}; for (int i = 1; i < n; i++) { diff --git a/content/latexHeaders/layout.sty b/content/latexHeaders/layout.sty index 096cf23..01915f3 100644 --- a/content/latexHeaders/layout.sty +++ b/content/latexHeaders/layout.sty @@ -10,9 +10,8 @@ % Headline and bottomline. \usepackage{scrlayer-scrpage} \pagestyle{scrheadings} -\clearscrheadfoot -\ihead{\university} -\chead{\teamname} +\clearpairofpagestyles +\ihead{\university{} -- \teamname{}} \ohead{\pagemark} % Shift the title up to waste less space. @@ -43,7 +42,7 @@ % use less space... %\usepackage[subtle, sections, indent, leading, charwidths]{savetrees} -\usepackage[moderate,sections]{savetrees} +\usepackage[moderate]{savetrees} \RedeclareSectionCommands[ beforeskip=1pt plus 5pt, afterskip=0.1pt plus 1.5pt diff --git a/content/latexHeaders/math.sty b/content/latexHeaders/math.sty index c34cc99..d758f71 100644 --- a/content/latexHeaders/math.sty +++ b/content/latexHeaders/math.sty @@ -6,6 +6,7 @@ \usepackage{mathtools} \usepackage{amssymb} \usepackage{ntheorem} +\usepackage{nicefrac} %\usepackage{pxfonts} \usepackage[scaled=0.945,largesc,looser]{newpxtext}%better than pxfonts... diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp new file mode 100644 index 0000000..48302b5 --- /dev/null +++ b/content/math/divSum.cpp @@ -0,0 +1,8 @@ +ll divSum(ll n, ll m, ll a, ll b){ + if (m == 0) return 0; + ll ans = a/m * n*(n-1)/2 + b/m * n; + a %= m; + b %= m; + ll y = (a*(n-1)+b) / m; + return ans + y * (n-1) - divSum(y, a, m, m-b-1); +} diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp index 8129fd2..d431e52 100644 --- a/content/math/gauss.cpp +++ b/content/math/gauss.cpp @@ -14,19 +14,17 @@ void takeAll(int n, int line) { int gauss(int n) { vector<bool> done(n, false); for (int i = 0; i < n; i++) { - int swappee = i; // Sucht Pivotzeile für bessere Stabilität. - for (int j = 0; j < n; j++) { - if (done[j]) continue; - if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j; + int j = i; // Sucht Pivotzeile für bessere Stabilität. + for (int k = 0; k < n; k++) { + if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k; } - swap(mat[i], mat[swappee]); + swap(mat[i], mat[j]); if (abs(mat[i][i]) > EPS) { normalLine(i); takeAll(n, i); done[i] = true; }} - // Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung. - for (int i = 0; i < n; i++) { + for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung bool allZero = true; for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS; if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT; diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp index 0241742..bf18c86 100644 --- a/content/math/lgsFp.cpp +++ b/content/math/lgsFp.cpp @@ -22,5 +22,4 @@ void gauss(int n, ll mod) { normalLine(i, mod); takeAll(n, i, mod); done[i] = true; -}} -// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ +}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@ diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index 2501e64..a8adacd 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -1,33 +1,30 @@ -constexpr ll mod = 1'000'000'007; -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; +constexpr ll mod = 998244353; +// oder ntt mul @\sourceref{math/transforms/ntt.cpp}@ +vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { + vector<ll> c(sz(a) + sz(b) - 1); + for (int i = 0; i < sz(a); i++) { + for (int j = 0; j < sz(b); j++) { + c[i+j] += a[i]*b[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; + for (ll& x : c) x %= mod; + return c; } 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; + int n = sz(c); + vector<ll> q(n + 1, 1); + for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i]) % mod; + vector<ll> p = mul(f, q); + p.resize(n); + p.push_back(0); + do { + vector<ll> q2 = q; + for (int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod; + vector<ll> x = mul(p, q2), y = mul(q, q2); + for (int i = 0; i <= n; i++){ + p[i] = i == n ? 0 : x[2*i + (k&1)]; + q[i] = y[2*i]; + } + } while (k /= 2); + return p[0]; } diff --git a/content/math/linearRecurrenceOld.cpp b/content/math/linearRecurrenceOld.cpp new file mode 100644 index 0000000..2501e64 --- /dev/null +++ b/content/math/linearRecurrenceOld.cpp @@ -0,0 +1,33 @@ +constexpr ll mod = 1'000'000'007; +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/content/math/math.tex b/content/math/math.tex index f670a70..644fbc8 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -109,8 +109,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \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}{Teiler}
@@ -138,8 +136,9 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz.
\begin{methods}
- \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+ \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)}
\end{methods}
+ Die Polynom-Multiplikation kann auch mit NTT gemacht werden!
\sourcecode{math/linearRecurrence.cpp}
Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
$$\renewcommand\arraystretch{1.5}
@@ -308,7 +307,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \method{gauss}{löst LGS}{n^3}
\sourcecode{math/gauss.cpp}
-\vfill\null\columnbreak
+\begin{algorithm}{Inversionszahl}
+ \vspace{-2pt}
+ \sourcecode{math/inversions.cpp}
+\end{algorithm}
\begin{algorithm}{Numerisch Extremstelle bestimmen}
\sourcecode{math/goldenSectionSearch.cpp}
@@ -318,7 +320,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/simpson.cpp}
\end{algorithm}
-
\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
Multipliziert Polynome $A$ und $B$.
\begin{itemize}
@@ -342,21 +343,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/transforms/seriesOperations.cpp}
\end{algorithm}
-\begin{algorithm}{Inversionszahl}
- \sourcecode{math/inversions.cpp}
-\end{algorithm}
-
-\subsection{Satz von \textsc{Sprague-Grundy}}
-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\}
-\]
-$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)$.
-
\subsection{Kombinatorik}
\paragraph{\textsc{Wilson}'s Theorem}
@@ -389,7 +375,9 @@ so gilt %\begin{algorithm}{Binomialkoeffizienten}
\paragraph{Binomialkoeffizienten}
Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
-
+
+ \input{math/tables/binom}
+
\begin{methods}
\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
\method{calc\_binom}{berechnet Binomialkoeffizient}{1}
@@ -498,7 +486,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \begin{align*}
p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
- p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg)
+ p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]
\end{align*}
\begin{itemize}
\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
@@ -508,6 +496,59 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
\input{math/tables/twelvefold}
+\subsection{Platonische Körper}
+\input{math/tables/platonic}
+
+\input{math/tables/probability}
+
+\subsection{Satz von \textsc{Sprague-Grundy}}
+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\}
+\]
+$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)$.
+
+\subsection{Nim-Spiele}
+\begin{itemize}
+ \item[\ding{182}] letzter gewinnt (normal)
+ \item[\ding{183}] letzter verliert
+\end{itemize}
+\input{math/tables/nim}
+
+\subsection{Verschiedenes}
+\input{math/tables/stuff}
+
+\begin{algorithm}{Div Sum}
+ \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)}
+ \textbf{Wichtig:} $b$ darf nicht negativ sein!
+ \sourcecode{math/divSum.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Min Mod}
+ \begin{methods}
+ \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)}
+ \method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{}
+ \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
+ \end{methods}
+ \textbf{Wichtig:} $0 \leq a, b, l, r < m$
+ \sourcecode{math/minMod.cpp}
+\end{algorithm}
+
+\subsection{Reihen}
+\input{math/tables/series}
+
+\subsection{Wichtige Zahlen}
+\input{math/tables/prime-composite}
+
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{math/recover.cpp}
+
\optional{
\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
\begin{methods}
@@ -516,9 +557,10 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$. \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}}
\end{methods}
\sourcecode{math/piLehmer.cpp}
-}
-%\input{math/tables/numbers}
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\sourcecode{math/piLegendre.cpp}
+}
\begin{algorithm}[optional]{Big Integers}
\sourcecode{math/bigint.cpp}
diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp new file mode 100644 index 0000000..a80e783 --- /dev/null +++ b/content/math/minMod.cpp @@ -0,0 +1,22 @@ +ll firstVal(ll a, ll m, ll l, ll r) { + if (l == 0) return 0; + if (a == 0) return -1; + if ((l-1)/a < r/a) return (l+a-1) / a*a; + ll s = (r+a-1) / a*a; + ll v = firstVal(m % a, a, s-r, s-l); + return v < 0 ? -1 : s - v; +} + +ll minMod(ll n, ll m, ll a, ll b) { + if (a == 0) return b; + ll g = gcd(m, a); + ll c = b % g; + m /= g; + a /= g; + b /= g; + ll ai = multInv(a, m); + ll l = ai*b % m; + ll r = (n-1 + ai*b) % m; + if (n >= m || l > r) return c; + return a * firstVal(ai, m, l, r) % m * g + c; +}
\ No newline at end of file diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp index 44f6207..84f3aaa 100644 --- a/content/math/polynomial.cpp +++ b/content/math/polynomial.cpp @@ -1,7 +1,7 @@ struct poly { vector<ll> data; - poly(int deg = 0) : data(max(1, deg)) {} + poly(int deg = 0) : data(1 + deg) {} poly(initializer_list<ll> _data) : data(_data) {} int size() const {return sz(data);} @@ -40,17 +40,18 @@ struct poly { //return p(x+a) poly operator<<(ll a) const { - poly res(size()); + poly res(size() - 1); for (int i = size() - 1; i >= 0; i--) { for (int j = size() - i - 1; j >= 1; j--) res[j] = (res[j] * a + res[j - 1]) % mod; - res[0] = (res[0] * a + res[i]) % mod; + res[0] = (res[0] * a + data[i]) % mod; } return res; } pair<poly, poly> divmod(const poly& d) const { int i = size() - d.size(); + if (i <= 0) return {{}, *this}; poly s(i + 1), r = *this; ll inv = multInv(d.data.back(), mod); for (; i >= 0; i--) { diff --git a/content/math/recover.cpp b/content/math/recover.cpp new file mode 100644 index 0000000..1a593f0 --- /dev/null +++ b/content/math/recover.cpp @@ -0,0 +1,13 @@ +ll sq(ll x) {return x*x;} + +array<ll, 2> recover(ll c, ll m) { + array<ll, 2> u = {m, 0}, v = {c, 1}; + while (m <= 2 * sq(v[0])) { + ll q = u[0] / v[0]; + u[0] -= q * v[0]; + u[1] -= q * v[1]; + swap(u, v); + } + if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1}; + return v; +} diff --git a/content/math/shortModInv.cpp b/content/math/shortModInv.cpp index f696cce..cf91ca0 100644 --- a/content/math/shortModInv.cpp +++ b/content/math/shortModInv.cpp @@ -1,3 +1,3 @@ ll multInv(ll x, ll m) { // x^{-1} mod m - return 1 < x ? m - multInv(m % x, x) * m / x : 1; + return 1 < x ? m - multInv(m % x, x) * m / x : 1; } diff --git a/content/math/squfof.cpp b/content/math/squfof.cpp deleted file mode 100644 index 1cb97de..0000000 --- a/content/math/squfof.cpp +++ /dev/null @@ -1,89 +0,0 @@ -using lll = __int128;
-
-constexpr lll multipliers[] = {1, 3, 5, 7,
- 11, 3*5, 3*7, 3*11,
- 5*7, 5*11, 7*11,
- 3*5*7, 3*5*11, 3*7*11,
- 5*7*11, 3*5*7*11};
-
-lll root(lll x) {
- lll r = sqrtl(x);
- while(r*r < x) r++;
- while(r*r > x) r--;
- return r;
-}
-
-lll croot(lll x) {
- lll r = cbrtl(x);
- while(r*r*r < x) r++;
- while(r*r*r > x) r--;
- return r;
-}
-
-lll squfof(lll N) {
- lll s = croot(N);
- if (s*s*s == N) return s;
- s = root(N);
- if (s*s == N) return s;
- for (lll k : multipliers) {
- lll D = k * N;
- lll Po, P, Pprev, q, b, r, i;
- Po = Pprev = P = root(D);
- lll Qprev = 1;
- lll Q = D - Po*Po;
- lll L = 2 * root(2 * s);
- lll B = 3 * L;
- for (i = 2; i < B; i++) {
- b = (Po + P) / Q;
- P = b*Q - P;
- q = Q;
- Q = Qprev + b * (Pprev - P);
- r = root(Q);
- if (!(i & 1) && r*r == Q) break;
- Qprev = q;
- Pprev = P;
- }
- if (i >= B) continue;
- b = (Po - P) / r;
- Pprev = P = b*r + P;
- Qprev = r;
- Q = (D-Pprev*Pprev)/Qprev;
- i = 0;
- do {
- b = (Po + P) / Q;
- Pprev = P;
- P = b*Q - P;
- q = Q;
- Q = Qprev + b * (Pprev - P);
- Qprev = q;
- i++;
- } while(P != Pprev);
- r = gcd(N, Qprev);
- if (r != 1 && r != N) return r;
- }
- exit(1);//try fallback to pollard rho
-}
-
-constexpr lll trialLim = 5'000;
-
-void factor(lll n, map<lll, int>& facts) {
- for (lll i = 2; i * i <= n && i <= trialLim; i++) {
- while (n % i == 0) {
- facts[i]++;
- n /= i;
- }}
- if (n > 1 && n < trialLim * trialLim) {
- facts[n]++;
- } else {
- vector<lll> todo = {n};
- while (!todo.empty()) {
- lll c = todo.back();
- todo.pop_back();
- if (c == 1) continue;
- if (isPrime(c)) {
- facts[c]++;
- } else {
- lll d = squfof(c);
- todo.push_back(d);
- todo.push_back(c / d);
-}}}}
diff --git a/content/math/tables.tex b/content/math/tables.tex deleted file mode 100644 index c422d73..0000000 --- a/content/math/tables.tex +++ /dev/null @@ -1,22 +0,0 @@ -\enlargethispage{0.2cm} -\begin{multicols*}{2} - \refstepcounter{subsection} - \subsectionmark{Tables} - \addcontentsline{toc}{subsection}{\protect\numberline{\thesubsection}Tables} - - \input{math/tables/binom} - \vfill - \input{math/tables/prime-composite} - \vfill - \input{math/tables/platonic} - \vfill - \input{math/tables/series} - - \columnbreak - - \input{math/tables/probability} - \vfill - \input{math/tables/stuff} - \vfill - \input{math/tables/nim} -\end{multicols*} diff --git a/content/math/tables/binom.tex b/content/math/tables/binom.tex index 878a6b0..9fc9ae3 100644 --- a/content/math/tables/binom.tex +++ b/content/math/tables/binom.tex @@ -1,28 +1,27 @@ -\begin{tabularx}{\linewidth}{|XXXX|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|C|} \hline - \multicolumn{4}{|c|}{Binomialkoeffizienten} \\ - \hline - \multicolumn{4}{|c|}{ $\frac{n!}{k!(n - k)!} \hfill=\hfill \binom{n}{k} \hfill=\hfill \binom{n}{n - k} \hfill=\hfill \frac{n}{k}\binom{n - 1}{k - 1} \hfill=\hfill \frac{n-k+1}{k}\binom{n}{k - 1} \hfill=\hfill - \binom{n - 1}{k} + \binom{n - 1}{k - 1} \hfill=\hfill + \frac{k+1}{n-k}\binom{n}{k + 1} \hfill=\hfill$\\ + + $\binom{n - 1}{k - 1} + \binom{n - 1}{k} \hfill=\hfill + \binom{n + 1}{k + 1} - \binom{n}{k + 1} \hfill=\hfill (-1)^k \binom{k - n - 1}{k} \hfill\approx\hfill - 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$ - } \\ + 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$\\ \grayhline - $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ & - $\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ & - $\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ & - $\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\ + $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n\hfill + \sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}\hfill + \sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}\hfill + \sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\ - $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ & - $\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ & - \multicolumn{2}{l|}{ - $\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$ - }\\ + $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\hfill + \sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\hfill + \sum\limits_{i = 1}^n \binom{n}{i} \mathit{Fib}_i = \mathit{Fib}_{2n}$\\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/nim.tex b/content/math/tables/nim.tex index 8490d42..66e289e 100644 --- a/content/math/tables/nim.tex +++ b/content/math/tables/nim.tex @@ -1,7 +1,6 @@ +\begin{expandtable} \begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|} \hline - \multicolumn{2}{|c|}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\ - \hline Beschreibung & Strategie \\ \hline @@ -94,3 +93,5 @@ Periode ab $n = 72$ der Länge $12$.\\ \hline \end{tabularx} +\end{expandtable} +
\ No newline at end of file diff --git a/content/math/tables/numbers.tex b/content/math/tables/numbers.tex deleted file mode 100644 index 1dc9f38..0000000 --- a/content/math/tables/numbers.tex +++ /dev/null @@ -1,59 +0,0 @@ -\begin{expandtable} -\begin{tabularx}{\linewidth}{|l|X|} - \hline - \multicolumn{2}{|c|}{Berühmte Zahlen} \\ - \hline - \textsc{Fibonacci} & - $f(0) = 0 \quad - f(1) = 1 \quad - f(n+2) = f(n+1) + f(n)$ \\ - \grayhline - - \textsc{Catalan} & - $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{2(2n - 1)}{n+1} \cdot C_{n-1}$ \\ - \grayhline - - \textsc{Euler} I & - $\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad - \eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\ - \grayhline - - \textsc{Euler} II & - $\eulerII{n}{0} = 1 \quad - \eulerII{n}{n} = 0 \quad$\\ - & $\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\ - \grayhline - - \textsc{Stirling} I & - $\stirlingI{0}{0} = 1 \qquad - \stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad - \stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\ - \grayhline - - \textsc{Stirling} II & - $\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad - \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} = - \frac{1}{k!} \sum\limits_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$\\ - \grayhline - - \textsc{Bell} & - $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}$\\ - \grayhline - - \textsc{Partitions} & - $p(0,0) = 1 \quad - p(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\ - & $p(n,k) = p(n-k,k) + p(n-1,k-1)$\\ - \grayhline - - \textsc{Partitions} & - $f(0) = 1 \quad f(n) = 0~(n < 0)$ \\ - & $f(n)=\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k+1)}{2})+\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k-1)}{2})$\\ - - \hline -\end{tabularx} -\end{expandtable} diff --git a/content/math/tables/platonic.tex b/content/math/tables/platonic.tex index f4ee554..2866ccf 100644 --- a/content/math/tables/platonic.tex +++ b/content/math/tables/platonic.tex @@ -1,39 +1,39 @@ +\begin{expandtable} \begin{tabularx}{\linewidth}{|X|CCCX|} \hline - \multicolumn{5}{|c|}{Platonische Körper} \\ - \hline - Übersicht & Seiten & Ecken & Kanten & dual zu \\ + Übersicht & |F| & |V| & |E| & dual zu \\ \hline Tetraeder & 4 & 4 & 6 & Tetraeder \\ - Würfel/Hexaeder & 6 & 8 & 12 & Oktaeder \\ - Oktaeder & 8 & 6 & 12 & Würfel/Hexaeder\\ + Würfel & 6 & 8 & 12 & Oktaeder \\ + Oktaeder & 8 & 6 & 12 & Würfel\\ Dodekaeder & 12 & 20 & 30 & Ikosaeder \\ Ikosaeder & 20 & 12 & 30 & Dodekaeder \\ \hline \multicolumn{5}{|c|}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\ \hline - \multicolumn{3}{|l}{Ecken vom Oktaeder/Seiten vom Würfel} & + \multicolumn{3}{|l}{|V| vom Oktaeder/|F| vom Würfel} & \multicolumn{2}{l|}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\ - \multicolumn{3}{|l}{Ecken vom Würfel/Seiten vom Oktaeder} & + \multicolumn{3}{|l}{|V| vom Würfel/|F| vom Oktaeder} & \multicolumn{2}{l|}{$(n^8 + 17n^4 + 6n^2)/24$} \\ - \multicolumn{3}{|l}{Kanten vom Würfel/Oktaeder} & + \multicolumn{3}{|l}{|E| vom Würfel/Oktaeder} & \multicolumn{2}{l|}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\ - \multicolumn{3}{|l}{Ecken/Seiten vom Tetraeder} & + \multicolumn{3}{|l}{|V|/|F| vom Tetraeder} & \multicolumn{2}{l|}{$(n^4 + 11n^2)/12$} \\ - \multicolumn{3}{|l}{Kanten vom Tetraeder} & + \multicolumn{3}{|l}{|E| vom Tetraeder} & \multicolumn{2}{l|}{$(n^6 + 3n^4 + 8n^2)/12$} \\ - \multicolumn{3}{|l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} & + \multicolumn{3}{|l}{|V| vom Ikosaeder/|F| vom Dodekaeder} & \multicolumn{2}{l|}{$(n^{12} + 15n^6 + 44n^4)/60$} \\ - \multicolumn{3}{|l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} & + \multicolumn{3}{|l}{|V| vom Dodekaeder/|F| vom Ikosaeder} & \multicolumn{2}{l|}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\ - \multicolumn{3}{|l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} & + \multicolumn{3}{|l}{|E| vom Dodekaeder/Ikosaeder} & \multicolumn{2}{l|}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/prime-composite.tex b/content/math/tables/prime-composite.tex index 99b3348..073b4ba 100644 --- a/content/math/tables/prime-composite.tex +++ b/content/math/tables/prime-composite.tex @@ -1,26 +1,31 @@ -\begin{tabularx}{\linewidth}{|r|r|rIr|rIrIr|C|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|r|rIr|rIr|r|r|} \hline - \multicolumn{8}{|c|}{Important Numbers} \\ + \multirow{2}{*}{$10^x$} + & \multirow{2}{*}{Highly Composite} + & \multirow{2}{*}{\# Divs} + & \multicolumn{2}{|c|}{Prime} + & \multirow{2}{*}{\# Primes} & \multirow{2}{*}{Primorial} \\ + & & & $<$ & $>$ & & \\ \hline - $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & primorial & \\ - \hline - 1 & 6 & 4 & $-3$ & $+1$ & 4 & 2 & \\ - 2 & 60 & 12 & $-3$ & $+1$ & 25 & 3 & \\ - 3 & 840 & 32 & $-3$ & $+9$ & 168 & 4 & \\ - 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & 5 & \\ - 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & 6 & \\ - 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & 7 & \\ - 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & 8 & \\ - 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & 8 & \\ - 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & 9 & \\ - 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & 10 & \\ - 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & 10 & \\ - 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & 11 & \\ - 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & 12 & \\ - 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & 12 & \\ - 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & 13 & \\ - 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & 13 & \\ - 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & 14 & \\ - 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 16 & \\ + 1 & 6 & 4 & $-3$ & $+1$ & 4 & 2 \\ + 2 & 60 & 12 & $-3$ & $+1$ & 25 & 3 \\ + 3 & 840 & 32 & $-3$ & $+9$ & 168 & 4 \\ + 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & 5 \\ + 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & 6 \\ + 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & 7 \\ + 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & 8 \\ + 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & 8 \\ + 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & 9 \\ + 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & 10 \\ + 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & 10 \\ + 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & 11 \\ + 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & 12 \\ + 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & 12 \\ + 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & 13 \\ + 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & 13 \\ + 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & 14 \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 16 \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/probability.tex b/content/math/tables/probability.tex index f265d10..29f92e1 100644 --- a/content/math/tables/probability.tex +++ b/content/math/tables/probability.tex @@ -1,19 +1,15 @@ -\begin{tabularx}{\linewidth}{|LICIR|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|LIR|} \hline - \multicolumn{3}{|c|}{ + \multicolumn{2}{|c|}{ Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen) } \\ \hline - $\E(X + Y) = \E(X) + \E(Y)$ & - $\E(\alpha X) = \alpha \E(X)$ & - $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$\\ - - $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ & - $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ & - $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\ + $\E(X + Y) = \E(X) + \E(Y)$ & $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\ + $\E(\alpha X) = \alpha \E(X)$ & $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\ + $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$\\ \hline \end{tabularx} -\vfill \begin{tabularx}{\linewidth}{|Xlr|lrX|} \hline \multicolumn{6}{|c|}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\ @@ -25,3 +21,4 @@ $\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ & \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/series.tex b/content/math/tables/series.tex index 3042781..9618c2b 100644 --- a/content/math/tables/series.tex +++ b/content/math/tables/series.tex @@ -1,33 +1,33 @@ -\begin{tabularx}{\linewidth}{|XIXIXIX|} - \hline - \multicolumn{4}{|c|}{Reihen} \\ +\begin{expandtable} +\begin{tabularx}{\linewidth}{|XIXIX|} \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^3 = \frac{n^2 (n + 1)^2}{4}$ & - $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ + $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\ \grayhline - $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ & - $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ & - $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ & - $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\ + $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \hfill c \neq 1$ & + $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \hfill \vert c \vert < 1$ & + $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \hfill \vert c \vert < 1$ \\ \grayhline - + \multicolumn{2}{|lI}{ $\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$ } & - \multicolumn{2}{l|}{ + $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \hfill \vert c \vert < 1$ \\ + \grayhline + + \multicolumn{2}{|lI}{ $\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$ - } \\ + } & + $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\ \grayhline \multicolumn{2}{|lI}{ - $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ - } & - \multicolumn{2}{l|}{ $\sum\limits_{i = 1}^n \binom{i}{m}H_i = \binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m + 1}\right)$ - } \\ + } & + $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ \\ \hline \end{tabularx} +\end{expandtable} diff --git a/content/math/tables/stuff.tex b/content/math/tables/stuff.tex index 3cf8b4c..82f2d3f 100644 --- a/content/math/tables/stuff.tex +++ b/content/math/tables/stuff.tex @@ -1,6 +1,7 @@ -\begin{tabularx}{\linewidth}{|ll|} +\begin{expandtable} +\begin{tabularx}{\linewidth}{|Ll|} \hline - \multicolumn{2}{|C|}{Verschiedenes} \\ + \multicolumn{2}{|c|}{Verschiedenes} \\ \hline Türme von Hanoi, minimale Schirttzahl: & $T_n = 2^n - 1$ \\ @@ -20,7 +21,7 @@ \#Wälder mit $k$ gewurzelten Bäumen & $\frac{k}{n}\binom{n}{k}n^{n-k}$ \\ - \#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten& + \#Wälder mit $k$ gewurzelten~Bäumen mit vorgegebenen Wurzelknoten& $\frac{k}{n}n^{n-k}$ \\ Derangements & @@ -29,4 +30,4 @@ $\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\ \hline \end{tabularx} - +\end{expandtable} diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index 4743674..b405698 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -4,7 +4,7 @@ vector<ll> poly_inv(const vector<ll>& a, int n) { vector<ll> a2 = a, q2 = q; a2.resize(2*len), q2.resize(2*len); ntt(q2); - for (int j : {0, 1}) { + for (int _ : {0, 1}) { ntt(a2); for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; ntt(a2, true); @@ -24,10 +24,13 @@ vector<ll> poly_deriv(vector<ll> 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; + static vector<ll> inv = {0, 1}; + for (static int i = 2; i <= sz(a); i++) + inv.push_back(mod - mod / i * inv[mod % i] % mod); + + a.push_back(0); + for (int i = sz(a) - 1; i > 0; i--) + a[i] = a[i-1] * inv[i] % mod; a[0] = 0; return a; } @@ -35,8 +38,7 @@ vector<ll> poly_integr(vector<ll> 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; + return poly_integr(a); } vector<ll> poly_exp(vector<ll> a, int n) { diff --git a/content/other/bitOps.cpp b/content/other/bitOps.cpp index 8079305..6230c86 100644 --- a/content/other/bitOps.cpp +++ b/content/other/bitOps.cpp @@ -3,13 +3,6 @@ for (int subset = bitmask; subset > 0; subset = (subset - 1) & bitmask) -// Zählt Anzahl der gesetzten Bits. -int numberOfSetBits(int i) { - i = i - ((i >> 1) & 0x5555'5555); - i = (i & 0x3333'3333) + ((i >> 2) & 0x3333'3333); - return (((i + (i >> 4)) & 0x0F0F'0F0F) * 0x0101'0101) >> 24; -} - // Nächste Permutation in Bitmaske // (z.B. 00111 => 01011 => 01101 => ...) ll nextPerm(ll v) { diff --git a/content/other/divideAndConquer.cpp b/content/other/divideAndConquer.cpp index 830dc7f..9bd5f0c 100644 --- a/content/other/divideAndConquer.cpp +++ b/content/other/divideAndConquer.cpp @@ -5,7 +5,7 @@ void rec(int i, int j0, int j1, int m0, int m1) { if (j1 < j0) return; int jmid = (j0 + j1) / 2; - dp[i][jmid] = inf; + dp[i][jmid] = INF; int bestk = m0; for (int k = m0; k < min(jmid, m1 + 1); ++k) { if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) { @@ -18,7 +18,7 @@ void rec(int i, int j0, int j1, int m0, int m1) { } ll calc(int n, int m) { - dp = vector<vector<ll>>(m, vector<ll>(n, inf)); + dp = vector<vector<ll>>(m, vector<ll>(n, INF)); for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; for (int i = 1; i < m; i++) { rec(i, 0, n - 1, 0, n - 1); diff --git a/content/other/fastSubsetSum.cpp b/content/other/fastSubsetSum.cpp new file mode 100644 index 0000000..84396f6 --- /dev/null +++ b/content/other/fastSubsetSum.cpp @@ -0,0 +1,21 @@ +int fastSubsetSum(vector<int> w, int t){ + int a = 0, b = 0; + while(b < sz(w) && a + w[b] <= t) a += w[b++]; + if(b == sz(w)) return a; + int m = *max_element(all(w)); + vector<int> dp(2*m, -1), old; + dp[m+a-t] = b; + for(int i = b; i < sz(w); i++){ + old = dp; + for(int j = 0; j < m; j++){ + dp[j+w[i]] = max(dp[j+w[i]], old[j]); + } + for(int j = 2*m-1; j > m; j--){ + for(int k = max(old[j], 0); k < dp[j]; k++){ + dp[j-w[k]] = max(dp[j-w[k]], k); + } + } + } + for(a = t; dp[m+a-t] < 0; a--); + return a; +}
\ No newline at end of file diff --git a/content/other/josephus2.cpp b/content/other/josephus2.cpp index 5086e13..33544ea 100644 --- a/content/other/josephus2.cpp +++ b/content/other/josephus2.cpp @@ -1,8 +1,5 @@ int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert. - for (int i = 31; i >= 0; i--) { - if (n & (1 << i)) { - n &= ~(1 << i); - break; - }} - n <<= 1; n++; return n; + int bits = __lg(n); + n ^= 1 << bits; + return 2 * n + 1; } diff --git a/content/other/knuth.cpp b/content/other/knuth.cpp index 1d513c8..aa54924 100644 --- a/content/other/knuth.cpp +++ b/content/other/knuth.cpp @@ -1,5 +1,5 @@ ll calc(int n, int m, const vector<vector<ll>>& C) { - vector<vector<ll>> dp(m, vector<ll>(n, inf)); + vector<vector<ll>> dp(m, vector<ll>(n, INF)); vector<vector<int>> opt(m, vector<int>(n + 1, n - 1)); for (int i = 0; i < n; i++) dp[0][i] = C[0][i]; diff --git a/content/other/other.tex b/content/other/other.tex index 7a3c52b..59b5790 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -13,6 +13,19 @@ \sourcecode{other/timed.cpp}
\end{algorithm}
+\begin{algorithm}{Overflow-sichere arithmetische Operationen}
+ Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
+ \begin{expandtable}
+ \begin{tabularx}{\linewidth}{|lR|}
+ \hline
+ Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\
+ Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\
+ Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\
+ \hline
+ \end{tabularx}
+ \end{expandtable}
+\end{algorithm}
+
\begin{algorithm}{Bit Operations}
\begin{expandtable}
\begin{tabularx}{\linewidth}{|Ll|}
@@ -31,19 +44,6 @@ \sourcecode{other/bitOps.cpp}
\end{algorithm}
-\begin{algorithm}{Overflow-sichere arithmetische Operationen}
- Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
- \begin{expandtable}
- \begin{tabularx}{\linewidth}{|lR|}
- \hline
- Addition & \code{__builtin_saddll_overflow(a, b, \&c)} \\
- Subtraktion & \code{__builtin_ssubll_overflow(a, b, \&c)} \\
- Multiplikation & \code{__builtin_smulll_overflow(a, b, \&c)} \\
- \hline
- \end{tabularx}
- \end{expandtable}
-\end{algorithm}
-
\begin{algorithm}{Pragmas}
\sourcecode{other/pragmas.cpp}
\end{algorithm}
@@ -72,6 +72,12 @@ \sourcecode{other/sos.cpp}
\end{algorithm}
+\begin{algorithm}{Fast Subset Sum}
+ \method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
+ Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+ \sourcecode{other/fastSubsetSum.cpp}
+\end{algorithm}
+
\begin{algorithm}{Parallel Binary Search}
\sourcecode{other/pbs.cpp}
\end{algorithm}
diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 7cb60e5..f4db2fd 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,19 +1,19 @@ // Q = # of queries, bucket sort is sometimes faster -vector<int> low(Q, 0), high(Q, MAX_OPERATIONS); +vector<int> low(Q, -1), high(Q, MAX_OPERATIONS); while (true) { vector<pair<int, int>> focus; - for (int i = 0; i < Q; i++) if (low[i] < high[i]) { - focus.emplace_back((low[i] + high[i]) / 2, i); - } + for (int i = 0; i < Q; i++) { + if (low[i] + 1 < high[i]) { + focus.emplace_back((low[i] + high[i]) / 2, i); + }} if (focus.empty()) break; sort(all(focus)); // reset simulation for (int step = 0; auto [mid, i] : focus) { - while (step <= mid) { + for (; step <= mid; step++) { // simulation step - step++; } if (/* requirement already fulfilled */) high[i] = mid; - else low[i] = mid + 1; -}} // answer in low (and high) + else low[i] = mid; +}} // answer in low (MAX_OPERATIONS if never ok) diff --git a/content/other/stuff.cpp b/content/other/stuff.cpp index 41543ad..e4e37e2 100644 --- a/content/other/stuff.cpp +++ b/content/other/stuff.cpp @@ -1,13 +1,7 @@ -// Alles-Header. -#include <bits/stdc++.h> - // Setzt deutsche Tastaturlayout / toggle mit alt + space setxkbmap de setxkbmap de,us -option grp:alt_space_toggle -// Schnelle Ein-/Ausgabe mit cin/cout. -cin.tie(nullptr)->ios::sync_with_stdio(false); - // Set mit eigener Sortierfunktion. set<point2, decltype(comp)> set1(comp); diff --git a/content/string/ahoCorasick.cpp b/content/string/ahoCorasick.cpp index eac312c..390d16d 100644 --- a/content/string/ahoCorasick.cpp +++ b/content/string/ahoCorasick.cpp @@ -4,7 +4,7 @@ struct AhoCorasick { int suffix = 0, ch, cnt = 0; array<int, ALPHABET_SIZE> nxt = {}; - vert(int p, int c) : suffix(-p), ch(c) {} + vert(int p, int c) : suffix(-p), ch(c) {fill(all(nxt), -1);} }; vector<vert> aho = {{0, -1}}; @@ -12,7 +12,7 @@ struct AhoCorasick { int v = 0; for (auto c : s) { int idx = c - OFFSET; - if (!aho[v].nxt[idx]) { + if (aho[v].nxt[idx] == -1) { aho[v].nxt[idx] = sz(aho); aho.emplace_back(v, idx); } @@ -30,8 +30,8 @@ struct AhoCorasick { } 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); + if (aho[v].nxt[idx] != -1) return aho[v].nxt[idx]; + return v == 0 ? 0 : aho[v].nxt[idx] = go(getSuffix(v), idx); } vector<vector<int>> adj; diff --git a/content/string/duval.cpp b/content/string/duval.cpp index bf36cce..253bae1 100644 --- a/content/string/duval.cpp +++ b/content/string/duval.cpp @@ -6,9 +6,8 @@ vector<pair<int, int>> duval(const string& s) { if (s[k] < s[j]) k = i; else k++; } - while (i <= k) { + for (; i <= k; i += j - k) { res.push_back({i, i + j - k}); - i += j - k; }} return res; } @@ -16,6 +15,5 @@ vector<pair<int, int>> duval(const string& s) { int minrotation(const string& s) { auto parts = duval(s+s); for (auto [l, r] : parts) { - if (l < sz(s) && r >= sz(s)) { - return l; -}}} + if (r >= sz(s)) return l; +}} diff --git a/content/tcr.tex b/content/tcr.tex index afac53c..3b686ef 100644 --- a/content/tcr.tex +++ b/content/tcr.tex @@ -1,6 +1,9 @@ - -%maybe size 9pt if too many pages -\documentclass[a4paper,fontsize=7.8pt]{scrartcl} +\documentclass[ + paper=a4, + DIV=calc, + fontsize=7.8pt, + usegeometry +]{scrartcl} % General information. \newcommand{\teamname}{Infinite Loopers} @@ -54,11 +57,7 @@ \input{graph/graph} \input{geometry/geometry} \input{math/math} -\end{multicols*} \clearpage - \input{math/tables} -\begin{multicols*}{3} - \raggedcolumns \input{string/string} \input{python/python} \input{other/other} diff --git a/content/template/template.cpp b/content/template/template.cpp index c9a492c..7430d23 100644 --- a/content/template/template.cpp +++ b/content/template/template.cpp @@ -7,9 +7,9 @@ using namespace std; using ll = long long; using ld = long double; - + void solve() {} - + int main() { cin.tie(0)->sync_with_stdio(false); cout << setprecision(16); diff --git a/content/tests/gcc5bug.cpp b/content/tests/gcc5bug.cpp index f49603e..6aaeea9 100644 --- a/content/tests/gcc5bug.cpp +++ b/content/tests/gcc5bug.cpp @@ -1,4 +1,4 @@ //https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68203 struct A { - pair<int, int> values[1000000]; + pair<int, int> values[1000000]; }; |