From f1261bb7cd35840b9b5937a6260308f3839c6f3e Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:16:34 +0100 Subject: minor (mostly spacing) changes --- datastructures/lichao.cpp | 76 ++++++++++++++++++------------------ graph/reroot.cpp | 53 +++++++++++++------------ graph/scc.cpp | 3 +- graph/virtualTree.cpp | 13 +++--- math/binomial1.cpp | 3 +- math/chineseRemainder.cpp | 26 ++++++------ math/transforms/seriesOperations.cpp | 41 +++++++++---------- other/stuff.cpp | 3 +- string/manacher.cpp | 4 +- 9 files changed, 111 insertions(+), 111 deletions(-) diff --git a/datastructures/lichao.cpp b/datastructures/lichao.cpp index e12d243..f66778e 100644 --- a/datastructures/lichao.cpp +++ b/datastructures/lichao.cpp @@ -1,44 +1,46 @@ -vector xs; // IMPORTANT: Initialize before constructing Lichao! -int findX(int i) {return distance(xs.begin(), lower_bound(all(xs), i));} +vector xs; // IMPORTANT: Initialize before constructing! +int findX(int i) {return lower_bound(all(xs), i) - begin(xs);} -struct Fun{ // Default: Linear function. Change it to needed function type. - ll m, c; - ll operator()(int x) {return m*xs[x] + c;} +struct Fun { // Default: Linear function. Change as needed. + ll m, c; + ll operator()(int x) {return m*xs[x] + c;} }; // Default: Computes min. Change lines with comment for max. -struct Lichao{ - static constexpr Fun id = {0, inf}; // {0, -inf} - int n, cap; - vector seg; - Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {} - - void _insert(Fun f, int l, int r, int i) { - while (i < 2*cap){ - int m = (l+r)/2; - if (m >= n) {r = m; i = 2*i; continue;} - Fun &g = seg[i]; - if (f(m) < g(m)) swap(f, g); // > - if (f(l) < g(l)) r = m, i = 2*i; // > - else l = m, i = 2*i+1; - }} - void insert(Fun f) {_insert(f, 0, cap, 1);} +struct Lichao { + static constexpr Fun id = {0, inf}; // {0, -inf} + int n, cap; + vector seg; + Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {} + + void _insert(Fun f, int l, int r, int i) { + while (i < 2*cap){ + int m = (l+r)/2; + if (m >= n) {r = m; i = 2*i; continue;} + Fun &g = seg[i]; + if (f(m) < g(m)) swap(f, g); // > + if (f(l) < g(l)) r = m, i = 2*i; // > + else l = m, i = 2*i+1; + }} + void insert(Fun f) {_insert(f, 0, cap, 1);} - void _segmentInsert(Fun f, int l, int r, int a, int b, int i) { - if (l <= a && b <= r) _insert(f, a, b, i); - else if (a < r && l < b){ - int m = (a+b)/2; - _segmentInsert(f, l, r, a, m, 2*i); - _segmentInsert(f, l, r, m, b, 2*i+1); - }} - void segmentInsert(Fun f, ll l, ll r) { - _segmentInsert(f, findX(l), findX(r), 0, cap, 1); - } + void _segmentInsert(Fun f, int l, int r, int a, int b, int i) { + if (l <= a && b <= r) _insert(f, a, b, i); + else if (a < r && l < b){ + int m = (a+b)/2; + _segmentInsert(f, l, r, a, m, 2*i); + _segmentInsert(f, l, r, m, b, 2*i+1); + }} + void segmentInsert(Fun f, ll l, ll r) { + _segmentInsert(f, findX(l), findX(r), 0, cap, 1); + } - ll _query(int x) { - ll ans = inf; // -inf - for (int i = x + cap; i > 0; i /= 2) ans = min(ans, seg[i](x)); // max - return ans; - } - ll query(ll x) {return _query(findX(x));} + ll _query(int x) { + ll ans = inf; // -inf + for (int i = x + cap; i > 0; i /= 2) { + ans = min(ans, seg[i](x)); // max + } + return ans; + } + ll query(ll x) {return _query(findX(x));} }; diff --git a/graph/reroot.cpp b/graph/reroot.cpp index eeca43e..4c6a748 100644 --- a/graph/reroot.cpp +++ b/graph/reroot.cpp @@ -1,39 +1,39 @@ // 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 +// 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 value of dp[v] after iterating over all children -struct Reroot{ +// usually this operation should be commutative and associative +// - finalize the dp[v] after iterating over all children +struct Reroot { using T = ll; // identity element - T E(){} + T E() {} // x: dp value of child // e: index of edge going to child - T takeChild(T x, int e){} - T combine(T x, T y){} + T takeChild(T x, int e) {} + T comb(T x, T y) {} // called after combining all dp values of children - T finalize(T x, int v){} + T fin(T x, int v) {} vector>> g; vector ord, pae; vector dp; - T dfs(int v){ + T dfs(int v) { ord.push_back(v); - for(auto [w, e] : g[v]){ + for (auto [w, e] : g[v]) { g[w].erase(find(all(g[w]), pair(v, e^1))); pae[w] = e^1; - dp[v] = combine(dp[v], takeChild(dfs(w), e)); + dp[v] = comb(dp[v], takeChild(dfs(w), e)); } - return dp[v] = finalize(dp[v], v); + return dp[v] = fin(dp[v], v); } - vector solve(int n, vector> edges){ + vector solve(int n, vector> edges) { g.resize(n); - for(int i = 0; i < n-1; i++){ + 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); } @@ -41,19 +41,22 @@ struct Reroot{ dp.assign(n, E()); dfs(0); vector updp(n, E()), res(n, E()); - for(int v : ord){ + for (int v : ord) { vector 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++){ - pref[i+1] = suff[i] = takeChild(dp[g[v][i].first], g[v][i].second); - pref[i+1] = combine(pref[i], pref[i+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] = combine(suff[i], suff[i+1]); - for(int i = 0; i < sz(g[v]); i++) - updp[g[v][i].first] = finalize(combine(pref[i], suff[i+1]), v); - res[v] = finalize(pref.back(), v); + for (int i = sz(g[v])-1; i >= 0; i--) { + suff[i] = comb(suff[i], suff[i+1]); + } + for (int i = 0; i < sz(g[v]); i++) { + updp[g[v][i].first] = fin(comb(pref[i], suff[i+1]), v); + } + res[v] = fin(pref.back(), v); } return res; } -}; \ No newline at end of file +}; diff --git a/graph/scc.cpp b/graph/scc.cpp index 1716add..5aa7cf2 100644 --- a/graph/scc.cpp +++ b/graph/scc.cpp @@ -1,8 +1,7 @@ vector> adj, sccs; int counter, sccCounter; vector inStack; -// idx enthält den Index der SCC pro Knoten. -vector low, idx, s; +vector low, idx, s; //idx enthält Index der SCC pro Knoten. void visit(int v) { int old = low[v] = counter++; diff --git a/graph/virtualTree.cpp b/graph/virtualTree.cpp index f7a3cb1..2fcea80 100644 --- a/graph/virtualTree.cpp +++ b/graph/virtualTree.cpp @@ -1,10 +1,8 @@ // needs dfs in- and out- time and lca function vector in, out; -void virtualTree(const vector& a) { // takes indices of used nodes - auto ind = a; +void virtualTree(vector ind) { // indices of used nodes sort(all(ind), [&](int x, int y) {return in[x] < in[y];}); - for (int i=0; i& a) { // takes indices of used nodes int n = ind.size(); vector> tree(n); - stack st{{0}}; + vector st = {0}; for (int i=1; i= out[ind[st.top()]]) st.pop(); - tree[st.top()].push_back(i); + while (in[ind[i]] >= out[ind[st.back()]]) st.pop_back(); + tree[st.back()].push_back(i); st.push(i); } - // virtual directed tree with n nodes, original indices in ind - // weights can be calculated if necessary, e.g. with binary lifting + // weights can be calculated, e.g. with binary lifting } diff --git a/math/binomial1.cpp b/math/binomial1.cpp index 02b27e3..dab20b3 100644 --- a/math/binomial1.cpp +++ b/math/binomial1.cpp @@ -2,8 +2,7 @@ ll calc_binom(ll n, ll k) { if (k > n) return 0; ll r = 1; for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit - r *= n--; - r /= d; + r *= n--, r /= d; } return r; } diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index a1aa480..b02de48 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,14 +1,14 @@ -struct CRT{ - using lll = __int128_t; - lll M = 1, sol = 0; // Solution unique modulo M - bool hasSol = true; +struct CRT { + using lll = __int128; + lll M = 1, sol = 0; // Solution unique modulo M + bool hasSol = true; - // Adds congruence x = a (mod m) - void add(ll a, ll m){ - ll s, t, d = extendedEuclid(M, m, s, t); - if((a - sol) % d != 0) hasSol = false; - lll z = M/d * s; - M *= m/d; - sol = (z % M * (a-sol) % M + sol + M) % M; - } -}; \ No newline at end of file + // Adds congruence x = a (mod m) + void add(ll a, ll m) { + auto [d, s, t] = extendedEuclid(M, m); + if((a - sol) % d != 0) hasSol = false; + lll z = M/d * s; + M *= m/d; + sol = (z % M * (a-sol) % M + sol + M) % M; + } +}; diff --git a/math/transforms/seriesOperations.cpp b/math/transforms/seriesOperations.cpp index 3851a1e..4743674 100644 --- a/math/transforms/seriesOperations.cpp +++ b/math/transforms/seriesOperations.cpp @@ -1,55 +1,56 @@ -vector poly_inv(vector a, int n){ +vector poly_inv(const vector& a, int n) { vector q = {powMod(a[0], mod-2, mod)}; - for(int len = 1; len < n; len *= 2){ + for (int len = 1; len < n; len *= 2){ vector a2 = a, q2 = q; a2.resize(2*len), q2.resize(2*len); ntt(q2); - for(int j = 0; j < 2; j++){ + for (int j : {0, 1}) { ntt(a2); - for(int i = 0; i < 2*len; i++) a2[i] = a2[i] * q2[i] % mod; + for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; ntt(a2, true); - for(int i = 0; i < len; i++) a2[i] = 0; + for (int i = 0; i < len; i++) a2[i] = 0; } - for(int i = len; i < min(n, 2*len); i++) q.push_back((mod - a2[i]) % mod); - } + for (int i = len; i < min(n, 2*len); i++) { + q.push_back((mod - a2[i]) % mod); + }} return q; } -vector poly_deriv(vector a){ - for(int i = 0; i < sz(a)-1; i++) - a[i] = a[i+1] * (i+1) % mod; +vector poly_deriv(vector a) { + for (int i = 1; i < sz(a); i++) + a[i-1] = a[i] * i % mod; a.pop_back(); return a; } -vector poly_integr(vector a){ - if(a.empty()) return {0}; +vector poly_integr(vector 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--) + for (int i = sz(a)-2; i > 0; i--) a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; a[0] = 0; return a; } -vector poly_log(vector a, int n){ +vector poly_log(vector a, int n) { a = mul(poly_deriv(a), poly_inv(a, n)); a.resize(n-1); a = poly_integr(a); return a; } -vector poly_exp(vector a, int n){ +vector poly_exp(vector a, int n) { vector q = {1}; - for(int len = 1; len < n; len *= 2){ + for (int len = 1; len < n; len *= 2) { vector p = poly_log(q, 2*len); - for(int i = 0; i < 2*len; i++) + for (int i = 0; i < 2*len; i++) p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; vector q2 = q; q2.resize(2*len); ntt(p), ntt(q2); - for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; + for (int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; ntt(p, true); - for(int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); + for (int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); } return q; -} \ No newline at end of file +} diff --git a/other/stuff.cpp b/other/stuff.cpp index 38fde78..41543ad 100644 --- a/other/stuff.cpp +++ b/other/stuff.cpp @@ -6,8 +6,7 @@ setxkbmap de setxkbmap de,us -option grp:alt_space_toggle // Schnelle Ein-/Ausgabe mit cin/cout. -ios::sync_with_stdio(false); -cin.tie(nullptr); +cin.tie(nullptr)->ios::sync_with_stdio(false); // Set mit eigener Sortierfunktion. set set1(comp); diff --git a/string/manacher.cpp b/string/manacher.cpp index 6c1c94e..112bd55 100644 --- a/string/manacher.cpp +++ b/string/manacher.cpp @@ -7,8 +7,8 @@ vector manacher(const string& t) { vector pal(n); for (int i = 1; i < n - 1; i++) { if (r > i) pal[i] = min(r - i, pal[2 * mid - i]); - while (pal[i] < min(i, n - i - 1) - && s[i + pal[i] + 1] == s[i - pal[i] - 1]) { + while (pal[i] < min(i, n - i - 1) && + s[i + pal[i] + 1] == s[i - pal[i] - 1]) { pal[i]++; } if (i + pal[i] > r) mid = i, r = i + pal[i]; -- cgit v1.2.3