summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--datastructures/lichao.cpp76
-rw-r--r--graph/reroot.cpp53
-rw-r--r--graph/scc.cpp3
-rw-r--r--graph/virtualTree.cpp13
-rw-r--r--math/binomial1.cpp3
-rw-r--r--math/chineseRemainder.cpp26
-rw-r--r--math/transforms/seriesOperations.cpp41
-rw-r--r--other/stuff.cpp3
-rw-r--r--string/manacher.cpp4
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<ll> xs; // IMPORTANT: Initialize before constructing Lichao!
-int findX(int i) {return distance(xs.begin(), lower_bound(all(xs), i));}
+vector<ll> xs; // IMPORTANT: Initialize before constructing!
+int findX(int i) {return lower_bound(all(xs), i) - begin(xs);}
-struct Fun{ // Default: Linear function. Change it to needed function type.
- ll m, c;
- ll operator()(int x) {return m*xs[x] + c;}
+struct Fun { // Default: Linear function. Change as needed.
+ ll m, c;
+ ll operator()(int x) {return m*xs[x] + c;}
};
// Default: Computes min. Change lines with comment for max.
-struct Lichao{
- static constexpr Fun id = {0, inf}; // {0, -inf}
- int n, cap;
- vector<Fun> seg;
- Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {}
-
- void _insert(Fun f, int l, int r, int i) {
- while (i < 2*cap){
- int m = (l+r)/2;
- if (m >= n) {r = m; i = 2*i; continue;}
- Fun &g = seg[i];
- if (f(m) < g(m)) swap(f, g); // >
- if (f(l) < g(l)) r = m, i = 2*i; // >
- else l = m, i = 2*i+1;
- }}
- void insert(Fun f) {_insert(f, 0, cap, 1);}
+struct Lichao {
+ static constexpr Fun id = {0, inf}; // {0, -inf}
+ int n, cap;
+ vector<Fun> seg;
+ Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {}
+
+ void _insert(Fun f, int l, int r, int i) {
+ while (i < 2*cap){
+ int m = (l+r)/2;
+ if (m >= n) {r = m; i = 2*i; continue;}
+ Fun &g = seg[i];
+ if (f(m) < g(m)) swap(f, g); // >
+ if (f(l) < g(l)) r = m, i = 2*i; // >
+ else l = m, i = 2*i+1;
+ }}
+ void insert(Fun f) {_insert(f, 0, cap, 1);}
- void _segmentInsert(Fun f, int l, int r, int a, int b, int i) {
- if (l <= a && b <= r) _insert(f, a, b, i);
- else if (a < r && l < b){
- int m = (a+b)/2;
- _segmentInsert(f, l, r, a, m, 2*i);
- _segmentInsert(f, l, r, m, b, 2*i+1);
- }}
- void segmentInsert(Fun f, ll l, ll r) {
- _segmentInsert(f, findX(l), findX(r), 0, cap, 1);
- }
+ void _segmentInsert(Fun f, int l, int r, int a, int b, int i) {
+ if (l <= a && b <= r) _insert(f, a, b, i);
+ else if (a < r && l < b){
+ int m = (a+b)/2;
+ _segmentInsert(f, l, r, a, m, 2*i);
+ _segmentInsert(f, l, r, m, b, 2*i+1);
+ }}
+ void segmentInsert(Fun f, ll l, ll r) {
+ _segmentInsert(f, findX(l), findX(r), 0, cap, 1);
+ }
- ll _query(int x) {
- ll ans = inf; // -inf
- for (int i = x + cap; i > 0; i /= 2) ans = min(ans, seg[i](x)); // max
- return ans;
- }
- ll query(ll x) {return _query(findX(x));}
+ ll _query(int x) {
+ ll ans = inf; // -inf
+ for (int i = x + cap; i > 0; i /= 2) {
+ ans = min(ans, seg[i](x)); // max
+ }
+ return ans;
+ }
+ ll query(ll x) {return _query(findX(x));}
};
diff --git a/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<vector<pair<int, int>>> g;
vector<int> ord, pae;
vector<T> 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<T> solve(int n, vector<pair<int, int>> edges){
+ vector<T> solve(int n, vector<pair<int, int>> 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<T> updp(n, E()), res(n, E());
- for(int v : ord){
+ 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++){
- 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<vector<int>> adj, sccs;
int counter, sccCounter;
vector<bool> inStack;
-// idx enthält den Index der SCC pro Knoten.
-vector<int> low, idx, s;
+vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
void visit(int v) {
int old = low[v] = counter++;
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<int> in, out;
-void virtualTree(const vector<int>& a) { // takes indices of used nodes
- auto ind = a;
+void virtualTree(vector<int> ind) { // indices of used nodes
sort(all(ind), [&](int x, int y) {return in[x] < in[y];});
-
for (int i=0; i<sz(a)-1; i++) {
ind.push_back(lca(ind[i], ind[i+1]));
}
@@ -13,13 +11,12 @@ void virtualTree(const vector<int>& a) { // takes indices of used nodes
int n = ind.size();
vector<vector<int>> tree(n);
- stack<int> st{{0}};
+ vector<int> st = {0};
for (int i=1; i<n; i++) {
- while (in[ind[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<ll> poly_inv(vector<ll> a, int n){
+vector<ll> poly_inv(const vector<ll>& a, int n) {
vector<ll> q = {powMod(a[0], mod-2, mod)};
- for(int len = 1; len < n; len *= 2){
+ for (int len = 1; len < n; len *= 2){
vector<ll> a2 = a, q2 = q;
a2.resize(2*len), q2.resize(2*len);
ntt(q2);
- for(int j = 0; 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<ll> poly_deriv(vector<ll> a){
- for(int i = 0; i < sz(a)-1; i++)
- a[i] = a[i+1] * (i+1) % mod;
+vector<ll> poly_deriv(vector<ll> a) {
+ for (int i = 1; i < sz(a); i++)
+ a[i-1] = a[i] * i % mod;
a.pop_back();
return a;
}
-vector<ll> poly_integr(vector<ll> a){
- if(a.empty()) return {0};
+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--)
+ for (int i = sz(a)-2; i > 0; i--)
a[i] = a[i-1] * powMod(i, mod-2, mod) % mod;
a[0] = 0;
return a;
}
-vector<ll> poly_log(vector<ll> a, int n){
+vector<ll> poly_log(vector<ll> a, int n) {
a = mul(poly_deriv(a), poly_inv(a, n));
a.resize(n-1);
a = poly_integr(a);
return a;
}
-vector<ll> poly_exp(vector<ll> a, int n){
+vector<ll> poly_exp(vector<ll> a, int n) {
vector<ll> q = {1};
- for(int len = 1; len < n; len *= 2){
+ for (int len = 1; len < n; len *= 2) {
vector<ll> 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<ll> q2 = q;
q2.resize(2*len);
ntt(p), ntt(q2);
- for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod;
+ 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<point2, decltype(comp)> 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<int> manacher(const string& t) {
vector<int> 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];
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 20:46:25 +0000