Team Notebook

Sample Team Name (Sample University Name)

December 14, 2018

Contents 4 Geometry 11 8 Misc 18

4.1 center 2 points + radious . . . . . . . . . . . 11 8.1 Template Java . . . . . . . . . . . . . . . . . 18
1 Algorithms 2 4.2 closest pair problem . . . . . . . . . . . . . . 11 8.2 dates . . . . . . . . . . . . . . . . . . . . . . . 19
1.1 Mo’s algorithm on trees . . . . . . . . . . . . 2 4.3 triangles . . . . . . . . . . . . . . . . . . . . . 11 8.3 fraction . . . . . . . . . . . . . . . . . . . . . 19
1.2 Mo’s algorithm . . . . . . . . . . . . . . . . . 2 8.4 io . . . . . . . . . . . . . . . . . . . . . . . . . 19
5 Graphs 11
1.3 sliding window . . . . . . . . . . . . . . . . . 2
5.1 SCC kosaraju . . . . . . . . . . . . . . . . . . 11 9 Number theory 20
5.2 board . . . . . . . . . . . . . . . . . . . . . . 12
2 DP Optimizations 3 9.1 convolution . . . . . . . . . . . . . . . . . . . 20
5.3 bridges . . . . . . . . . . . . . . . . . . . . . . 12
2.1 convex hull trick . . . . . . . . . . . . . . . . 3 9.2 diophantine equations . . . . . . . . . . . . . 20
5.4 directed mst . . . . . . . . . . . . . . . . . . . 13
2.2 divide and conquer . . . . . . . . . . . . . . . 3 5.5 eulerian path . . . . . . . . . . . . . . . . . . 13 9.3 discrete logarithm . . . . . . . . . . . . . . . 21
2.3 dp on trees . . . . . . . . . . . . . . . . . . . 4 5.6 karp min mean cycle . . . . . . . . . . . . . . 13 9.4 ext euclidean . . . . . . . . . . . . . . . . . . 21
5.7 konig’s theorem . . . . . . . . . . . . . . . . . 14 9.5 highest exponent factorial . . . . . . . . . . . 21
3 Data structures 4 5.8 minimum path cover in DAG . . . . . . . . . 14 9.6 miller rabin . . . . . . . . . . . . . . . . . . . 21
3.1 STL Treap . . . . . . . . . . . . . . . . . . . 4 5.9 planar graph (euler) . . . . . . . . . . . . . . 14 9.7 mod integer . . . . . . . . . . . . . . . . . . . 21
3.2 STL order statistics tree II . . . . . . . . . . 5 5.10 query with lca . . . . . . . . . . . . . . . . . . 14 9.8 mod inv . . . . . . . . . . . . . . . . . . . . . 21
3.3 STL order statistics tree . . . . . . . . . . . . 5 5.11 tarjan scc . . . . . . . . . . . . . . . . . . . . 15 9.9 mod mul . . . . . . . . . . . . . . . . . . . . . 22
5.12 two sat (with kosaraju) . . . . . . . . . . . . 15 9.10 mod pow . . . . . . . . . . . . . . . . . . . . 22
3.4 binary index tree . . . . . . . . . . . . . . . . 5
9.11 number theoretic transform . . . . . . . . . . 22
3.5 dsu . . . . . . . . . . . . . . . . . . . . . . . . 5 6 Math 16 9.12 primes . . . . . . . . . . . . . . . . . . . . . . 22
3.6 heavy light decomposition . . . . . . . . . . . 6 6.1 Lucas theorem . . . . . . . . . . . . . . . . . 16
9.13 totient sieve . . . . . . . . . . . . . . . . . . . 23
3.7 persistent array . . . . . . . . . . . . . . . . . 6 6.2 counting . . . . . . . . . . . . . . . . . . . . . 16
9.14 totient . . . . . . . . . . . . . . . . . . . . . . 23
3.8 persistent seg tree . . . . . . . . . . . . . . . 6 6.3 cumulative sum of divisors . . . . . . . . . . . 16
3.9 persistent trie . . . . . . . . . . . . . . . . . . 7 6.4 fft . . . . . . . . . . . . . . . . . . . . . . . . 17
10 Strings 23
3.10 segment tree . . . . . . . . . . . . . . . . . . 8 6.5 fibonacci properties . . . . . . . . . . . . . . . 18
10.1 Incremental Aho Corasick . . . . . . . . . . . 23
6.6 polynomials . . . . . . . . . . . . . . . . . . . 18
3.11 sparse table . . . . . . . . . . . . . . . . . . . 9 10.2 minimal string rotation . . . . . . . . . . . . 24
6.7 sigma function . . . . . . . . . . . . . . . . . 18
3.12 splay tree . . . . . . . . . . . . . . . . . . . . 9 10.3 suffix array . . . . . . . . . . . . . . . . . . . 24
3.13 trie . . . . . . . . . . . . . . . . . . . . . . . . 10 7 Matrix 18 10.4 suffix automaton . . . . . . . . . . . . . . . . 25
3.14 wavelet tree . . . . . . . . . . . . . . . . . . . 10 7.1 matrix . . . . . . . . . . . . . . . . . . . . . . 18 10.5 z algorithm . . . . . . . . . . . . . . . . . . . 25

1
Sample Team Name (Sample University Name) 2

1 Algorithms if (le[u] > le[v]) int n;

swap(u, v); cin >> n;
queries[i].id = i; vector<int> a(n);
1.1 Mo’s algorithm on trees queries[i].lca = lca; for (auto &i : a) cin >> i;
queries[i].u = u;
/** queries[i].v = v; int q;
problems: if (lca == u) { cin >> q;
- [Link] problem E queries[i].a = le[u] + 1; for (int i = 0; i < q; ++i) {
*/ queries[i].b = le[v]; int b, e;
void flat(vector<vector<edge>> &g, vector<int> &a, } else { cin >> b >> e;
vector<int> &le, vector<int> &ri, vector<int> &cost, queries[i].a = ri[u]; b--;
int node, int pi, int &ts, int w) { queries[i].b = le[v]; e--;
} s[i] = Query(b, e, i);
cost[node] = w; } }
le[node] = ts; solve_mo(queries, a, le, cost); // this is the usal
a[ts] = node; algorithm sort(s, s + q);
ts++; }
for (auto e : g[node]) { int i = 0;
if ([Link] == pi) continue; int j = -1;
flat(g, a, le, ri, cost, [Link], node, ts, e.w); for (int k = 0; k < (int)q; ++k) {
} 1.2 Mo’s algorithm int L = s[k].a;
ri[node] = ts; int R = s[k].b;
a[ts] = node; const int MN = 5 * 100000 + 1;
ts++; const int SN = 708; while (j < R) [Link](a[++j]);
} while (j > R) [Link](a[j--]);
struct Query { while (i < L) [Link](a[i++]);
/** int a, b, id; while (i > L) [Link](a[--i]);
* Case when the cost is in the edges. Query() {}
* */ Query(int x, int y, int i) : a(x), b(y), id(i) {} ans[s[k].id] = [Link]();
void compute_queries(vector<vector<edge>> &g) { }
// g is undirected bool operator<(const Query &o) const {
int n = [Link](); if (a / SN != o.a / SN) return a < o.a; for (int i = 0; i < q; ++i) {
return a / SN & 1 ? b < o.b : b > o.b; cout << ans[i] << endl;
lca_tree.init(g, 0); } }
};
vector<int> a(2 * n), le(n), ri(n), cost(n); return 0;
// a: nodes in the flatten array struct DS { };
// le: left id of the given node DS() : {}
// ri: right id of the given node
// cost: cost of the edge from the node to the parent void Insert(int x) {}
1.3 sliding window
int ts = 0; // timestamp void Erase(int x) {}
flat(g, a, le, ri, cost, 0, -1, ts, 0);
long long Query() {} /*
int q; cin >> q; }; * Given an array ARR and an integer K, the problem boils
vector<query> queries(q); down to computing for each index i: min(ARR[i], ARR[i
for (int i = 0; i < q; i++) { Query s[MN]; -1], ..., ARR[i-K+1]).
int u, v; int ans[MN]; * if mx == true, returns the maximun.
cin >> u >> v; DS active; * [Link]
u--; v--; sliding_window_minimum.html
int lca = lca_tree.query(u, v); int main() { * */
Sample Team Name (Sample University Name) 3

return num / den;

vector<int> sliding_window_minmax(vector<int> & ARR, int K, } struct Line {
bool mx) { int64 m, b;
deque< pair<int, int> > window; /** mutable function<const Line*()> succ;
vector<int> ans; * min m_i * x_j + b_i, for all i. bool operator<(const Line& rhs) const {
for (int i = 0; i < [Link](); i++) { * x_j <= x_{j + 1} if (rhs.b != is_query) return m < rhs.m;
if (mx) { * m_i >= m_{j + 1} const Line* s = succ();
while (![Link]() && [Link]().first <= ARR[i * */ if (!s) return 0;
]) struct ordered_cht { int64 x = rhs.m;
window.pop_back(); vector<line> ch; return b - s->b < (s->m - m) * x;
} else { int idx; // id of last "best" in query }
while (![Link]() && [Link]().first >= ARR[i ordered_cht() { };
]) idx = 0;
window.pop_back(); } struct HullDynamic : public multiset<Line> { // will
} maintain upper hull for maximum
window.push_back(make_pair(ARR[i], i)); void insert_line(long long m, long long b) { bool bad(iterator y) {
line cur(m, b); auto z = next(y);
while([Link]().second <= i - K) // new line’s slope is less than all the previous if (y == begin()) {
window.pop_front(); while ([Link]() > 1 && if (z == end()) return 0;
(inter(cur, ch[[Link]() - 2]) >= inter(cur, ch[ch. return y->m == z->m && y->b <= z->b;
ans.push_back([Link]().first); size() - 1]))) { }
} // f(x) is better in interval [inter([Link](), cur), auto x = prev(y);
return ans; inf) if (z == end()) return y->m == x->m && y->b <= x->b;
} ch.pop_back(); return (float128)(x->b - y->b)*(z->m - y->m) >= (float128
} )(y->b - z->b)*(y->m - x->m);
}
ch.push_back(cur); void insert_line(int64 m, int64 b) {
2 DP Optimizations } auto y = insert({ m, b });
y->succ = [=] { return next(y) == end() ? 0 : &*next(y);
long long eval(long long x) { // minimum };
2.1 convex hull trick // current x is greater than all the previous x, if (bad(y)) { erase(y); return; }
// if that is not the case we can make binary search. while (next(y) != end() && bad(next(y))) erase(next(y));
/** idx = min<int>(idx, [Link]() - 1); while (y != begin() && bad(prev(y))) erase(prev(y));
* Problems: while (idx + 1 < (int)[Link]() && ch[idx + 1].eval(x) <= }
* [Link] ch[idx].eval(x))
* [Link] idx++; int64 eval(int64 x) {
* [Link] auto l = *lower_bound((Line) { x, is_query });
* [Link] return ch[idx].eval(x); return l.m * x + l.b;
* */ } }
}; };
struct line {
long long m, b;
line (long long a, long long c) : m(a), b(c) {} /**
long long eval(long long x) { * Dynammic convex hull trick 2.2 divide and conquer
return m * x + b; * */
} /**
}; typedef long long int64; * recurrence:
typedef long double float128; * dp[k][i] = min dp[k-1][j] + c[i][j - 1], for all j > i;
long double inter(line a, line b) { *
long double den = a.m - b.m; const int64 is_query = -(1LL<<62), inf = 1e18; * "comp" computes dp[k][i] for all i in O(n log n) (k is
long double num = b.b - a.b; fixed)
Sample Team Name (Sample University Name) 4

* long long total; return [Link];

* Problems: vector<long long> partial; }
* [Link]
* [Link] state() { clear(); } if ([Link] != -1) { // only one missing and is
* */ different of ’id_parent’
void clear() { int tmp = go(g[node][[Link]].to, g[node][[Link]].
void comp(int l, int r, int le, int re) { seen = false; p_id);
if (l > r) return; missing = 0; [Link][[Link]] = tmp;
total = 0; [Link] += tmp;
int mid = (l + r) >> 1; [Link](); [Link] = -1;
} }
int best = max(mid + 1, le); };
dp[cur][mid] = dp[cur ^ 1][best] + cost(mid, best - 1); int extra = (id_parent == -1) ? 0 : [Link][id_parent];
for (int i = best; i <= re; i++) { void add_edge(int u, int v) { return [Link] - extra;
if (dp[cur][mid] > dp[cur ^ 1][i] + cost(mid, i - 1)) { int id_u_v = g[u].size(); }
best = i; int id_v_u = g[v].size(); }
dp[cur][mid] = dp[cur ^ 1][i] + cost(mid, i - 1); g[u].emplace_back(v, id_v_u); // id of the parent in the
} child’s list (g[v][id] -> u)
} g[v].emplace_back(u, id_u_v); // id of the parent in the
child’s list (g[u][id] -> v) 3 Data structures
comp(l, mid - 1, le, best); }
comp(mid + 1, r, best, re);
} 3.1 STL Treap
int go(int node, int id_parent) {
#include <ext/rope> //header with rope
state &s = dp[node]; using namespace std;
2.3 dp on trees using namespace __gnu_cxx; //namespace with rope and some
if (![Link]) { additional stuff
/** int ans = 1; int main()
* This trick is very useful when doing DP on trees, [Link](g[node].size(), 0); // create the list {
basically, you can save of partial results. ios_base::sync_with_stdio(false);
* the answer for each node as if it was the root of the for (int i = 0; i < int(g[node].size()); i++) { rope <int> v; //use as usual STL container
tree. Partial results int to = g[node][i].to; int n, m;
* are also stored in order to query subtrees (taking the int pid = g[node][i].p_id; cin >> n >> m;
root and exclude some if (i != id_parent) { for(int i = 1; i <= n; ++i)
* child). int tmp = go(to, pid); v.push_back(i); //initialization
* ans += tmp; int l, r;
* problems: [Link][i] = tmp; for(int i = 0; i < m; ++i)
* - [Link] problem I : Sky tax } {
* - [Link] } cin >> l >> r;
* */ --l, --r;
[Link] = id_parent; rope <int> cur = [Link](l, r - l + 1);
[Link] = ans; [Link](l, r - l + 1);
struct edge { [Link] = true; [Link](v.mutable_begin(), cur);
int to, p_id; }
edge (int a, int b) : to(a), p_id(b) {} return ans; for(rope <int>::iterator it = v.mutable_begin(); it != v.
}; } else { mutable_end(); ++it)
cout << *it << " ";
struct state { if ([Link] == id_parent) { // the same id_parent than return 0;
bool seen; before, so we can not complete the results yet }
long long missing;
Sample Team Name (Sample University Name) 5

3.2 STL order statistics tree II D 5 cout<<ans[i]<<’\n’;

L 4 }
L 5
#include <bits/stdc++.h> /***
#include <ext/pb_ds/assoc_container.hpp> Output Input
#include <ext/pb_ds/tree_policy.hpp> 5 5
4 1 1
using namespace std; 6 5 1
using namespace __gnu_pbds; 4 7 1
7 3 3
typedef tree<int,null_type,less<int>,rb_tree_tag, ***/ 5 5
tree_order_statistics_node_update> order_set;
Output
order_set X; 1
3.3 STL order statistics tree 2
int get(int y) { 1
int l=0,r=1e9+1; #include <ext/pb_ds/assoc_container.hpp> 1
while(l<r) { #include <ext/pb_ds/tree_policy.hpp> 0
int m=l+((r-l)>>1); #include <bits/stdc++.h> ***/
if(m-X.order_of_key(m+1)<y)
l=m+1; using namespace __gnu_pbds;
else using namespace std;
r=m; 3.4 binary index tree
} typedef
return l; tree< struct binary_index_tree {
} pair<int,int>, int n;
null_type, int t[2 * N];
main(){ less<pair<int,int>>,
ios::sync_with_stdio(0); rb_tree_tag, void add(int where, long long what){
[Link](0); tree_order_statistics_node_update> for (where++; where <= n; where += where & -where){
int n,m; ordered_set; t[where] += what;
cin>>n>>m; }
main() }
for(int i=0;i<m;i++) { {
char a; ios::sync_with_stdio(0); void add(int from, int to, long long what) {
int b; [Link](0); add(from, what);
cin>>a>>b; int n; add(to + 1, -what);
if(a==’L’) int sz=0; }
cout<<get(b)<<endl; cin>>n;
else vector<int> ans(n,0); long long query(int where){
[Link](get(b)); long long sum = t[0];
} ordered_set t; for (where++; where > 0; where -= where & -where){
} int x,y; sum += t[where];
for(int i=0;i<n;i++) }
/*** { return sum;
Input cin>>x>>y; }
20 7 ans[t.order_of_key({x,++sz})]++; };
L 5 [Link]({x,sz});
D 5 }
L 4 3.5 dsu
L 5 for(int i=0;i<n;i++)
Sample Team Name (Sample University Name) 6

t[v] = ts++;
struct Dsu { c[k].push_back(v); node (int x) : l(NULL), r(NULL), val(x) {}
vector<int> p; r[v] = k; node () : l(NULL), r(NULL), val(-1) {}
};
Dsu(int n) { int x = 0, y = -1;
[Link](n); for (int i = 0; i < g[v].size(); ++i) { typedef node* pnode;
for (int i = 0; i < n; i++) { int w = g[v][i];
p[i] = i; if (w != f) { pnode update(pnode cur, int l, int r, int at, int what) {
} if (s[w] > x) { pnode ans = new node();
} x = s[w];
y = w; if (cur != NULL) {
int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]) } *ans = *cur;
; } } }
} if (l == r) {
int Join(int x, int y) { if (y != -1) { ans-> val = what;
int px = Find(x), py = Find(y); hld(y, v, k); return ans;
if (px == py) return 0; } }
p[px] = py; int m = (l + r) >> 1;
return 1; for (int i = 0; i < g[v].size(); ++i) { if (at <= m) ans-> l = update(ans-> l, l, m, at, what);
} int w = g[v][i]; else ans-> r = update(ans-> r, m + 1, r, at, what);
}; if (w != f && w != y) { return ans;
hld(w, v, w); }
}
} int get(pnode cur, int l, int r, int at) {
3.6 heavy light decomposition } if (cur == NULL) return 0;
if (l == r) return cur-> val;
struct TreeDecomposition { void init(int n) { int m = (l + r) >> 1;
vector<int> g[MAXN], c[MAXN]; for (int i = 0; i < n; ++i) { if (at <= m) return get(cur-> l, l, m, at);
int s[MAXN]; // subtree size g[i].clear(); else return get(cur-> r, m + 1, r, at);
int p[MAXN]; // parent id } }
int r[MAXN]; // chain root id }
int t[MAXN]; // index used in segtree/bit/...
int d[MAXN]; // depht void add(int a, int b) {
int ts; g[a].push_back(b); 3.8 persistent seg tree
g[b].push_back(a);
void dfs(int v, int f) { } /**
p[v] = f; * Problems:
s[v] = 1; void build() { * [Link]
if (f != -1) d[v] = d[f] + 1; ts = 0; *
else d[v] = 0; dfs(0, -1); * Important:
hld(0, 0, 0); * When using lazy propagation remembert to create new
for (int i = 0; i < g[v].size(); ++i) { } * versions for each push_down operation!!!
int w = g[v][i]; }; * */
if (w != f) {
dfs(w, v); struct node {
s[v] += s[w]; node *l, *r;
} 3.7 persistent array long long acc;
} int flip;
} struct node {
node *l, *r; node (int x) : l(NULL), r(NULL), acc(x), flip(0) {}
void hld(int v, int f, int k) { int val; node () : l(NULL), r(NULL), acc(0), flip(0) {}
Sample Team Name (Sample University Name) 7

}; } 3.9 persistent trie

int m = (l + r) >> 1;
typedef node* pnode; push_down(ans, l, r);
if (at <= m) ans-> l = update(ans-> l, l, m, at, what); // both tries can be tested with the problem: http://
pnode create(int l, int r) { else ans-> r = update(ans-> r, m + 1, r, at, what); [Link]/problemset/problem/916/D
if (l == r) return new node();
pnode cur = new node(); push_down(ans-> l, l, m);
int m = (l + r) >> 1; push_down(ans-> r, m + 1, r);
cur-> l = create(l, m); ans-> acc = get_val(ans-> l) + get_val(ans-> r); // Persistent binary trie (BST for integers)
cur-> r = create(m + 1, r); return ans; const int MD = 31;
return cur; }
} struct node_bin {
pnode flip(pnode cur, int l, int r, int a, int b) { node_bin *child[2];
pnode copy_node(pnode cur) { pnode ans = new node(); int val;
pnode ans = new node();
*ans = *cur; if (cur != NULL) { node_bin() : val(0) {
return ans; *ans = *cur; child[0] = child[1] = NULL;
} } }
if (l > b || r < a) };
void push_down(pnode cur, int l, int r) { return ans;
assert(cur); typedef node_bin* pnode_bin;
if (cur-> flip) { if (l >= a && r <= b) {
int len = r - l + 1; ans-> flip ^= 1; pnode_bin copy_node(pnode_bin cur) {
cur-> acc = len - cur-> acc; push_down(ans, l, r); pnode_bin ans = new node_bin();
if (cur-> l) { return ans; if (cur) *ans = *cur;
cur-> l = copy_node(cur-> l); } return ans;
cur-> l -> flip ^= 1; }
} int m = (l + r) >> 1;
if (cur-> r) { ans-> l = flip(ans-> l, l, m, a, b); pnode_bin modify(pnode_bin cur, int key, int inc, int id =
cur-> r = copy_node(cur-> r); ans-> r = flip(ans-> r, m + 1, r, a, b); MD) {
cur-> r -> flip ^= 1; push_down(ans-> l, l, m); pnode_bin ans = copy_node(cur);
} push_down(ans-> r, m + 1, r); ans->val += inc;
cur-> flip = 0; ans-> acc = get_val(ans-> l) + get_val(ans-> r); if (id >= 0) {
} return ans; int to = (key >> id) & 1;
} } ans->child[to] = modify(ans->child[to], key, inc, id - 1)
;
int get_val(pnode cur) { long long get_all(pnode cur, int l, int r) { }
assert(cur); assert(cur); return ans;
assert((cur-> flip) == 0); push_down(cur, l, r); }
if (cur) return cur-> acc; return cur-> acc;
return 0; } int sum_smaller(pnode_bin cur, int key, int id = MD) {
} if (cur == NULL) return 0;
void traverse(pnode cur, int l, int r) { if (id < 0) return 0; // strictly smaller
pnode update(pnode cur, int l, int r, int at, int what) { if (!cur) return; // if (id == - 1) return cur->val; // smaller or equal
pnode ans = copy_node(cur); cout << l << " - " << r << " : " << (cur-> acc) << " " <<
if (l == r) { (cur-> flip) << endl; int ans = 0;
assert(l == at); traverse(cur-> l, l, (l + r) >> 1); int to = (key >> id) & 1;
ans-> acc = what; traverse(cur-> l, 1 + ((l + r) >> 1), r); if (to) {
ans-> flip = 0; } if (cur->child[0]) ans += cur->child[0]->val;
return ans; ans += sum_smaller(cur->child[1], key, id - 1);
} else {
Sample Team Name (Sample University Name) 8

ans = sum_smaller(cur->child[0], key, id - 1); * If at some point after modifications we need to inspect
} const int MN = 1e5; // limit for array size all the
return ans; * elements in the array, we can push all the modifications
} struct seg_tree { to the
int n; // array size * leaves using the following code. After that we can just
int t[2 * MN]; traverse
// Persistent trie for strings. * elements starting with index n. This way we reduce the
const int MAX_CHILD = 26; seg_tree(int _n) : n(_n) {} complexity
struct node { * from O(n log(n)) to O(n) similarly to using build instead
node *child[MAX_CHILD]; void clear() { of n modifications.
int val; memset(t, 0, sizeof t); * */
node() : val(-1) { }
for (int i = 0; i < MAX_CHILD; i++) { void push() {
child[i] = NULL; void build() { // build the tree for (int i = 1; i < n; ++i) {
} for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i t[i<<1] += t[i];
} <<1|1]; t[i<<1|1] += t[i];
}; } t[i] = 0;
}
typedef node* pnode; // Single modification, range query. }
void modify(int p, int value) { // set value at position p
pnode copy_node(pnode cur) { for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + // Non commutative combiner functions.
pnode ans = new node(); t[p^1];
if (cur) *ans = *cur; } void modify(int p, const S& value) {
return ans; for (t[p += n] = value; p >>= 1; ) t[p] = combine(t[p<<1],
} int query(int l, int r) { // sum on interval [l, r) t[p<<1|1]);
int res = 0; }
pnode set_val(pnode cur, string &key, int val, int id = 0) { for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
pnode ans = copy_node(cur); if (l&1) res += t[l++]; S query(int l, int r) {
if (id >= int([Link]())) { if (r&1) res += t[--r]; S resl, resr;
ans->val = val; } for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
} else { return res; if (l&1) resl = combine(resl, t[l++]);
int t = key[id] - ’a’; } if (r&1) resr = combine(t[--r], resr);
ans->child[t] = set_val(ans->child[t], key, val, id + 1); }; }
} return combine(resl, resr);
return ans; // Range modification, single query. }
}
void modify(int l, int r, int value) {
pnode get(pnode cur, string &key, int id = 0) { for (l += n, r += n; l < r; l >>= 1, r >>= 1) { /**
if (id >= int([Link]()) || !cur) if (l&1) t[l++] += value; * segment tree for intervals
return cur; if (r&1) t[--r] += value; *
int t = key[id] - ’a’; } * */
return get(cur->child[t], key, id + 1); }
} const int MN = 100000 + 100;
int query(int p) { struct seg_tree {
int res = 0; int val[MN * 4 + 4];
for (p += n; p > 0; p >>= 1) res += t[p]; int pending[MN * 4 + 4];
3.10 segment tree return res;
} seg_tree() {
/** memset(val, -1, sizeof val);
* Taken from: [Link] /** memset(pending, -1, sizeof pending);
* */
Sample Team Name (Sample University Name) 9

} } node (T k) : key(k), left(0), right(0), parent(0) {}

}; };
void propagate(int node, int b, int e) {
if (pending[node] != -1) { struct splay_tree{
val[node] = pending[node];
if (b < e) { 3.11 sparse table
pending[node << 1] = pending[node]; node *root;
pending[node << 1 | 1] = pending[node]; // RMQ.
} const int MN = 100000 + 10; // Max number of elements void right_rot(node *x) {
pending[node] = -1; const int ML = 18; // ceil(log2(MN)); node *p = x->parent;
} if (x->parent = p->parent) {
} struct st { if (x->parent->left == p) x->parent->left = x;
int data[MN]; if (x->parent->right == p) x->parent->right = x;
void set(int node, int b, int e, int from, int to, int v) int M[MN][ML]; }
{ int n; if (p->left = x->right) p->left->parent = p;
if (b > to || e < from) return; x->right = p;
void init(const vector<int> &d) { p->parent = x;
if (b >= from && e <= to) { n = [Link](); }
pending[node] = v; for (int i = 0; i < n; ++i)
propagate(node, b, e); data[i] = d[i]; void left_rot(node *x) {
return; node *p = x->parent;
} build(); if (x->parent = p->parent) {
} if (x->parent->left == p) x->parent->left = x;
int mid = (b + e) >> 1; if (x->parent->right == p) x->parent->right = x;
void build() { }
set(node << 1, b, mid, from, to, v); for (int i = 0; i < n; ++i) if (p->right = x->left) p->right->parent = p;
set(node << 1 | 1, mid + 1, e, from, to, v); M[i][0] = data[i]; x->left = p;
} for (int j = 1, p = 2, q = 1; p <= n; ++j, p <<= 1, q <<= p->parent = x;
1) }
for (int i = 0; i + p - 1 < n; ++i)
M[i][j] = max(M[i][j - 1], M[i + q][j - 1]); void splay(node *x, node *fa = 0) {
int query(int node, int b, int e, int pos) { }
propagate(node, b, e); int query(int b, int e) { while( x->parent != fa and x->parent != 0) {
int k = log2(e - b + 1); node *p = x->parent;
if (b == e && b == pos) { return max(M[b][k], M[e + 1 - (1<<k)][k]); if (p->parent == fa)
return val[node]; } if (p->right == x)
} }; left_rot(x);
else
int mid = (b + e) >> 1; right_rot(x);
if (pos <= mid) else {
return query(node << 1, b, mid, pos); 3.12 splay tree node *gp = p->parent; //grand parent
return query(node << 1 | 1, mid + 1, e, pos); if (gp->left == p)
} using namespace std; if (p->left == x)
#include<bits/stdc++.h> right_rot(x),right_rot(x);
void set(int from, int to, int v) { #define D(x) cout<<x<<endl; else
return set(1, 0, MN - 1, from, to, v); left_rot(x),right_rot(x);
} typedef int T; else
if (p->left == x)
int query(int pos) { struct node{ right_rot(x), left_rot(x);
return query(1, 0, MN - 1, pos); node *left, *right, *parent; else
T key;
Sample Team Name (Sample University Name) 10

left_rot(x), left_rot(x); void clear(){ wavelet *node = new wavelet(lo, hi, mid);
} tree[nodes].c = 0;
} memset(tree[nodes].a, -1, sizeof tree[nodes].a); vector<int> data_l, data_r, ind_l, ind_r;
if (fa == 0) root = x; nodes++; int ls = 0, rs = 0;
} } for (int i = 0; i < int([Link]()); i++) {
int value = data[i];
void insert(T key) { void init(){ if (value <= mid) {
node *cur = root; nodes = 0; data_l.emplace_back(value);
node *pcur = 0; clear(); ind_l.emplace_back(ind[i]);
while (cur) { } ls++;
pcur = cur; } else {
if (key > cur->key) cur = cur->right; int add(const string &s, bool query = 0){ data_r.emplace_back(value);
else cur = cur->left; int cur_node = 0; ind_r.emplace_back(ind[i]);
} for(int i = 0; i < [Link](); ++i){ rs++;
cur = new node(key); int id = gid(s[i]); }
cur->parent = pcur; if(tree[cur_node].a[id] == -1){ node->map_left.emplace_back(ls);
if (!pcur) root = cur; if(query) return 0; node->map_right.emplace_back(rs);
else if (key > pcur->key ) pcur->right = cur; tree[cur_node].a[id] = nodes; node->values.emplace_back(value);
else pcur->left = cur; clear(); node->ori.emplace_back(ind[i]);
splay(cur); } }
} cur_node = tree[cur_node].a[id];
} if (lo < hi) {
node *find(T key) { if(!query) tree[cur_node].c++; node->left = init(data_l, ind_l, lo, mid);
node *cur = root; return tree[cur_node].c; node->right = init(data_r, ind_r, mid + 1, hi);
while (cur) { } }
if (key > cur->key) cur = cur->right; return node;
else if(key < cur->key) cur = cur->left; }; }
else return cur;
} int kth(wavelet *node, int to, int k) {
return 0; // returns the kth element in the sorted version of (a[0],
} 3.14 wavelet tree ..., a[to])
if (node->l == node->r) return node->m;
splay_tree(){ root = 0;}; // this can be tested in the problem: [Link] int c = node->map_left[to];
}; problems/ILKQUERY/ if (k < c)
return kth(node->left, c - 1, k);
struct wavelet { return kth(node->right, node->map_right[to] - 1, k - c);
vector<int> values, ori; }
3.13 trie vector<int> map_left, map_right;
int l, r, m; int pos_kth_ocurrence(wavelet *node, int val, int k) {
const int MN = 26; // size of alphabet wavelet *left, *right; // returns the position on the original array of the kth
const int MS = 100010; // Number of states. wavelet() : left(NULL), right(NULL) {} ocurrence of the value "val"
wavelet(int a, int b, int c) : l(a), r(b), m(c), left(NULL if (!node) return -1;
struct trie{ ), right(NULL) {}
struct node{ }; if (node->l == node->r) {
int c; if (int(node->[Link]()) <= k)
int a[MN]; wavelet *init(vector<int> &data, vector<int> &ind, int lo, return -1;
}; int hi) { return node->ori[k];
if (lo > hi || ([Link]() == 0)) return NULL; }
node tree[MS]; int mid = ((long long)(lo) + hi) / 2;
int nodes; if (lo + 1 == hi) mid = lo; // handle negative values if (val <= node->m)
Sample Team Name (Sample University Name) 11

return pos_kth_ocurrence(node->left, val, k); best = min(best, dist(p[i], p[j])); sort([Link](), [Link](), [](const point &a, const point &b
return pos_kth_ocurrence(node->right, val, k); return best; ) {
} } return a.x < b.x;
});
int ls = ([Link]() + 1) >> 1; vector<point> y([Link](), [Link]());
double l = (p[ls - 1].x + p[ls].x) * 0.5; sort([Link](), [Link](), [](const point &a, const point &b
4 Geometry vector<point> xl(ls), xr([Link]() - ls);
unordered_set<int> left;
) {
return a.y < b.y;
for (int i = 0; i < ls; ++i) { });
4.1 center 2 points + radious xl[i] = x[i]; return cp(p, x, y);
[Link](x[i].id); }
vector<point> find_center(point a, point b, long double r) { }
point d = (a - b) * 0.5; for (int i = ls; i < [Link](); ++i) {
if ([Link](d) > r * r) { xr[i - ls] = x[i];
return vector<point> (); } 4.3 triangles
}
point e = b + d; vector<point> yl, yr; Let a, b, c be length of the three sides of a triangle.
long double fac = sqrt(r * r - [Link](d)); vector<point> pl, pr;
vector<point> ans; [Link](ls); [Link]([Link]() - ls); p = (a + b + c) ∗ 0.5
point x = point(-d.y, d.x); [Link](ls); [Link]([Link]() - ls);
long double l = sqrt([Link](x)); for (int i = 0; i < [Link](); ++i) { The inradius is defined by:
x = x * (fac / l); if ([Link](y[i].id))
ans.push_back(e + x); yl.push_back(y[i]); s
x = point(d.y, -d.x); else (p − a)(p − b)(p − c)
x = x * (fac / l); yr.push_back(y[i]);
iR =
p
ans.push_back(e + x);
return ans; if ([Link](p[i].id)) The radius of its circumcircle is given by the formula:
} pl.push_back(p[i]);
else
pr.push_back(p[i]);
abc
} cR = p
4.2 closest pair problem (a + b + c)(a + b − c)(a + c − b)(b + c − a)
double dl = cp(pl, xl, yl);
struct point { double dr = cp(pr, xr, yr);
double x, y;
int id;
double d = min(dl, dr); 5 Graphs
vector<point> yp; [Link]([Link]());
point() {} for (int i = 0; i < [Link](); ++i) {
point (double a, double b) : x(a), y(b) {} if (fabs(y[i].x - l) < d) 5.1 SCC kosaraju
}; yp.push_back(y[i]);
} struct SCC {
double dist(const point &o, const point &p) { for (int i = 0; i < [Link](); ++i) { vector<vector<int> > g, gr;
double a = p.x - o.x, b = p.y - o.y; for (int j = i + 1; j < [Link]() && j < i + 7; ++j) { vector<bool> used;
return sqrt(a * a + b * b); d = min(d, dist(yp[i], yp[j])); vector<int> order, component;
} } int total_components;
}
double cp(vector<point> &p, vector<point> &x, vector<point> return d; SCC(vector<vector<int> > &adj) {
&y) { } g = adj;
if ([Link]() < 4) { int n = [Link]();
double best = 1e100; double closest_pair(vector<point> &p) { [Link](n);
for (int i = 0; i < [Link](); ++i) vector<point> x([Link](), [Link]()); for (int i = 0; i < n; i++)
for (int j = i + 1; j < [Link](); ++j) for (auto to : g[i])
Sample Team Name (Sample University Name) 12

gr[to].push_back(i); 5.2 board int v = g[u][i].to;

if (v == pi[u]) continue;
[Link](n, false); struct board { if (!vi[v]) {
for (int i = 0; i < n; i++) int n, m, r; pi[v] = u;
if (!used[i]) board(int a, int b, int c = 1) : n(a), m(b), r(c) {} Dfs(v);
GenTime(i); if (d[u] < low[v]) is_b[g[u][i].id] = true;
long long frec(int x, int y) {
[Link](n, false); // returns how many squares of r x r contain the cell (x, low[u] = min(low[u], low[v]);
[Link](n, -1); y) } else {
total_components = 0; long long a = min(x, n - r) - max(x - r + 1, 0) + 1; low[u] = min(low[u], d[v]);
for (int i = n - 1; i >= 0; i--) { long long b = min(y, m - r) - max(y - r + 1, 0) + 1; }
int v = order[i]; return a * b; }
if (!used[v]) { } }
vector<int> cur_component;
Dfs(cur_component, v); bool valid(int x, int y) { // Multiple edges from a to b are not allowed.
for (auto node : cur_component) return x >= 0 && x < n && y >= 0 && y < m; // (they could be detected as a bridge).
component[node] = total_components; } // If you need to handle this, just count
total_components++; }; // how many edges there are from a to b.
} void CompBridges() {
} fill([Link](), [Link](), -1);
} fill([Link](), [Link](), 0);
5.3 bridges fill([Link](), [Link](), 0);
void GenTime(int node) { fill([Link](), [Link](), 0);
used[node] = true; struct Graph { ticks = 0;
for (auto to : g[node]) vector<vector<Edge>> g; for (int i = 0; i < (int)[Link](); ++i)
if (!used[to]) vector<int> vi, low, d, pi, is_b; if (!vi[i]) Dfs(i);
GenTime(to); int bridges_computed; bridges_computed = true;
order.push_back(node); }
} int ticks, edges;
map<int, vector<Edge>> BridgesTree() {
void Dfs(vector<int> &cur, int node) { Graph(int n, int m) { if (!bridges_computed) CompBridges();
used[node] = true; [Link](n, vector<Edge>()); int n = [Link]();
cur.push_back(node); is_b.assign(m, 0); Dsu dsu([Link]());
for (auto to : gr[node]) [Link](n); for (int i = 0; i < n; i++)
if (!used[to]) [Link](n); for (auto e : g[i])
Dfs(cur, to); [Link](n); if (!is_b[[Link]]) [Link](i, [Link]);
} [Link](n);
edges = 0; map<int, vector<Edge>> tree;
vector<vector<int>> CondensedGraph() { bridges_computed = 0; for (int i = 0; i < n; i++)
vector<vector<int>> ans(total_components); } for (auto e : g[i])
for (int i = 0; i < int([Link]()); i++) { if (is_b[[Link]])
for (int to : g[i]) { void AddEdge(int u, int v) { tree[[Link](i)].emplace_back([Link]([Link]), [Link]
int u = component[i], v = component[to]; g[u].push_back(Edge(v, edges)); );
if (u != v) g[v].push_back(Edge(u, edges));
ans[u].push_back(v); edges++; return tree;
} } }
} };
return ans; void Dfs(int u) {
} vi[u] = true;
}; d[u] = low[u] = ticks++;
for (int i = 0; i < (int)g[u].size(); ++i) {
Sample Team Name (Sample University Name) 13

5.4 directed mst } if (out[v] > in[v]) start = v;

}
if (cur_id == 0) }
const int inf = 1000000 + 10; break; */
[Link](s);
struct edge { for (int i = 0; i < cur_nodes; ++i) reverse([Link](), [Link]());
int u, v, w; if (id[i] < 0) id[i] = cur_id++; trail = e.t;
edge() {} return true;
edge(int a,int b,int c) : u(a), v(b), w(c) {} for (int i = 0; i < [Link](); ++i) { }
}; int u = edges[i].u, v = edges[i].v, w = edges[i].w;
edges[i].u = id[u];
/** edges[i].v = id[v];
* Computes the minimum spanning tree for a directed graph if (id[u] != id[v])
* - edges : Graph description in the form of list of edges. edges[i].w -= lo[v];
5.6 karp min mean cycle
* each edge is: From node u to node v with cost w }
* - root : Id of the node to start the DMST. cur_nodes = cur_id; /**
* - n : Number of nodes in the graph. root = id[root]; * Finds the min mean cycle, if you need the max mean cycle
* */ } * just add all the edges with negative cost and print
* ans * -1
int dmst(vector<edge> &edges, int root, int n) { return ans; *
int ans = 0; } * test: uva, 11090 - Going in Cycle!!
int cur_nodes = n; * */
while (true) {
vector<int> lo(cur_nodes, inf), pi(cur_nodes, inf); const int MN = 1000;
for (int i = 0; i < [Link](); ++i) { 5.5 eulerian path struct edge{
int u = edges[i].u, v = edges[i].v, w = edges[i].w; int v;
if (w < lo[v] and u != v) { // Taken from [Link] long long w;
lo[v] = w; code/[Link] edge(){} edge(int v, int w) : v(v), w(w) {}
pi[v] = u; // Eulerian Trail };
}
} struct Euler { long long d[MN][MN];
ELV adj; IV t; // This is a copy of g because increments the size
lo[root] = 0; Euler(ELV Adj) : adj(Adj) {} // pass as reference if this does not matter.
for (int i = 0; i < [Link](); ++i) { void build(int u) { int karp(vector<vector<edge> > g) {
if (i == root) continue; while(! adj[u].empty()) { int n = [Link]();
if (lo[i] == inf) return -1; int v = adj[u].front().v;
} adj[u].erase(adj[u].begin()); [Link](n + 1); // this is important
int cur_id = 0; build(v);
vector<int> id(cur_nodes, -1), mark(cur_nodes, -1); } for (int i = 0; i < n; ++i)
for (int i = 0; i < cur_nodes; ++i) { t.push_back(u); if (!g[i].empty())
ans += lo[i]; } g[n].push_back(edge(i,0));
int u = i; }; ++n;
while (u != root and id[u] < 0 and mark[u] != i) { bool eulerian_trail(IV &trail) {
mark[u] = i; Euler e(adj); for(int i = 0;i<n;++i)
u = pi[u]; int odd = 0, s = 0; fill(d[i],d[i]+(n+1),INT_MAX);
} /*
if (u != root and id[u] < 0) { // Cycle for (int v = 0; v < n; v++) { d[n - 1][0] = 0;
for (int v = pi[u]; v != u; v = pi[v]) int diff = abs(in[v] - out[v]);
id[v] = cur_id; if (diff > 1) return false; for (int k = 1; k <= n; ++k) for (int u = 0; u < n; ++u) {
id[u] = cur_id++; if (diff == 1) { if (d[u][k - 1] == INT_MAX) continue;
} if (++odd > 2) return false; for (int i = g[u].size() - 1; i >= 0; --i)
Sample Team Name (Sample University Name) 14

d[g[u][i].v][k] = min(d[g[u][i].v][k], d[u][k - 1] + g[ void dfs(vector<vector<edge> > &g, int root, int pi = -1)
u][i].w); {
} if (pi == -1) {
L[root] = W[root] = 0;
bool flag = true; V out = {v ∈ V : v has positive out − degree} T[root] = -1;
}
for (int i = 0; i < n && flag; ++i) V in = {v ∈ V : v has positive in − degree} for (int i = 0; i < (int)g[root].size(); ++i) {
if (d[i][n] != INT_MAX) int to = g[root][i].v;
flag = false; E 0 = {(u, v) ∈ V out × V in : (u, v) ∈ E} if (to != pi) {
T[to] = root;
if (flag) { Then it can be shown, via König’s theorem, that G’ W[to] = g[root][i].w;
return true; // return true if there is no a cycle. L[to] = L[root] + 1;
has a matching of size m if and only if there exists n − m
} dfs(g, to, root);
vertex-disjoint paths that cover each vertex in G, where }
double ans = 1e15; n is the number of vertices in G and m is the maximum }
cardinality bipartite mathching in G’. }
for (int u = 0; u + 1 < n; ++u) {
if (d[u][n] == INT_MAX) continue; void init(vector<vector<edge> > &g, int root) {
double W = -1e15; Therefore, the problem can be solved by finding the max- // g is undirected
imum cardinality matching in G’ instead. dfs(g, root);
for (int k = 0; k < n; ++k) NOTE: If the paths are note necesarily disjoints, find int N = [Link](), i, j;
if (d[u][k] != INT_MAX)
W = max(W, (double)(d[u][n] - d[u][k]) / (n - k)); the transitive closure and solve the problem for disjoint for (i = 0; i < N; i++) {
paths. for (j = 0; 1 << j < N; j++) {
ans = min(ans, W); P[i][j] = -1;
} MI[i][j] = inf;
5.9 planar graph (euler) }
// printf("%.2lf\n", ans); }
cout << fixed << setprecision(2) << ans << endl; Euler’s formula states that if a finite, connected, planar
graph is drawn in the plane without any edge intersections, for (i = 0; i < N; i++) {
return false; P[i][0] = T[i];
}
and v is the number of vertices, e is the number of edges MI[i][0] = W[i];
and f is the number of faces (regions bounded by edges, }
including the outer, infinitely large region), then:
for (j = 1; 1 << j < N; j++)
5.7 konig’s theorem for (i = 0; i < N; i++)
f +v =e+2 if (P[i][j - 1] != -1) {
In any bipartite graph, the number of edges in a maximum P[i][j] = P[P[i][j - 1]][j - 1];
matching equals the number of vertices in a minimum vertex It can be extended to non connected planar graphs with MI[i][j] = min(MI[i][j-1], MI[ P[i][j - 1] ][j -
cover c connected components: 1]);
}
}
f +v =e+c+1
5.8 minimum path cover in DAG int query(int p, int q) {
int tmp, log, i;
Given a directed acyclic graph G = (V, E), we are to find 5.10 query with lca
the minimum number of vertex-disjoint paths to cover each int mmin = inf;
vertex in V. struct lowest_ca { if (L[p] < L[q])
0 int T[MN], L[MN], W[MN]; tmp = p, p = q, q = tmp;
We can construct a bipartite graph G = (V out ∪ int P[MN][ML], MI[MN][ML], MA[MN][ML];
V in, E 0 ) from G, where :
Sample Team Name (Sample University Name) 15

for (log = 1; 1 << log <= L[p]; log++); step++; }

log--; dist >>= 1; };
}
for (i = log; i >= 0; i--)
if (L[p] - (1 << i) >= L[q]) { return cur == p;
mmin = min(mmin, MI[p][i]); } 5.12 two sat (with kosaraju)
p = P[p][i]; };
} /**
* Given a set of clauses (a1 v a2)^(a2 v a3)....
if (p == q) * this algorithm find a solution to it set of clauses.
// return p; 5.11 tarjan scc * test: [Link]
return mmin; =1251
const int MN = 20002; **/
for (i = log; i >= 0; i--)
if (P[p][i] != -1 && P[p][i] != P[q][i]) { struct tarjan_scc { #include<bits/stdc++.h>
mmin = min(mmin, min(MI[p][i], MI[q][i])); int scc[MN], low[MN], d[MN], stacked[MN]; using namespace std;
p = P[p][i], q = P[q][i]; int ticks, current_scc; #define MAX 100000
} deque<int> s; // used as stack. #define endl ’\n’

// return T[p]; tarjan_scc() {} vector<int> G[MAX];

return min(mmin, min(MI[p][0], MI[q][0])); vector<int> GT[MAX];
} void init () { vector<int> Ftime;
memset(scc, -1, sizeof scc); vector<vector<int> > SCC;
int get_child(int p, int q) { // p is ancestor of q memset(d, -1, sizeof d); bool visited[MAX];
if (p == q) return -1; memset(stacked, 0, sizeof stacked); int n;
[Link]();
int i, log; ticks = current_scc = 0;
for (log = 1; 1 << log <= L[q]; log++) {} } void dfs1(int n){
log--; visited[n] = 1;
void compute(vector<vector<int> > &g, int u) {
for (i = log; i >= 0; i--) d[u] = low[u] = ticks++; for (int i = 0; i < G[n].size(); ++i) {
if (L[q] - (1 << i) > L[p]) { s.push_back(u); int curr = G[n][i];
q = P[q][i]; stacked[u] = true; if (visited[curr]) continue;
} for (int i = 0; i < g[u].size(); ++i) { dfs1(curr);
int v = g[u][i]; }
assert(P[q][0] == p); if (d[v] == -1)
return q; compute(g, v); Ftime.push_back(n);
} if (stacked[v]) { }
low[u] = min(low[u], low[v]);
int is_ancestor(int p, int q) { } void dfs2(int n, vector<int> &scc) {
if (L[p] >= L[q]) } visited[n] = 1;
return false; scc.push_back(n);
if (d[u] == low[u]) { // root
int dist = L[q] - L[p]; int v; for (int i = 0;i < GT[n].size(); ++i) {
do { int curr = GT[n][i];
int cur = q; v = [Link]();s.pop_back(); if (visited[curr]) continue;
int step = 0; stacked[v] = false; dfs2(curr, scc);
while (dist) { scc[v] = current_scc; }
if (dist & 1) } while (u != v); }
cur = P[cur][step]; current_scc++;
}
Sample Team Name (Sample University Name) 16

void kosaraju() { [Link](); 6 Math

memset(visited, 0, sizeof visited); [Link]();
for (int i = 0; i < 2 * n; ++i) {
for (int i = 0; i < 2 * n ; ++i) { G[i].clear(); 6.1 Lucas theorem
if (!visited[i]) dfs1(i); GT[i].clear();
} } For non-negative integers m and n and a prime p, the fol-
lowing congruence relation holds: :
memset(visited, 0, sizeof visited); // (a1 v a2) = (a1 -> a2) = ( a2 -> a1)
for (int i = [Link]() - 1; i >= 0; i--) { for (int i = 0; i < m ; ++i) {   Y k  
m mi
if (visited[Ftime[i]]) continue; cin >> u >> v; ≡ (mod p),
vector<int> _scc; int t1 = abs(u) - 1; n i=0
ni
dfs2(Ftime[i],_scc); int t2 = abs(v) - 1;
SCC.push_back(_scc); int p = t1 * 2 + ((u < 0)? 1 : 0);
} int q = t2 * 2 + ((v < 0)? 1 : 0);
where :
} G[p ^ 1].push_back(q);
G[q ^ 1].push_back(p); m = mk pk + mk−1 pk−1 + · · · + m1 p + m0 ,
/** GT[p].push_back(q ^ 1);
* After having the SCC, we must traverse each scc, if in GT[q].push_back(p ^ 1); and :
one SCC are -b y b, there is not a solution. }
* Otherwise we build a solution, making the first "node" n = nk pk + nk−1 pk−1 + · · · + n1 p + n0
that we find truth and its complement false. vector<int> val(2 * n, -1);
**/ cout << "Case " << ++nc <<": "; are the base p expansions

of m and n respectively. This uses
if (two_sat(val)) { the convention that m n = 0 if m ≤ n.
cout << "Yes" << endl;
bool two_sat(vector<int> &val) { vector<int> sol;
kosaraju(); for (int i = 0; i < 2 * n; ++i) 6.2 counting
for (int i = 0; i < [Link](); ++i) { if (i % 2 == 0 and val[i] == 1)
vector<bool> tmpvisited(2 * n, false); sol.push_back(i / 2 + 1); const int MN = 1e5 + 100;
for (int j = 0; j < SCC[i].size(); ++j) { cout << [Link]() ; long long fact[MN];
if (tmpvisited[SCC[i][j] ^ 1]) return 0;
if (val[SCC[i][j]] != -1) continue; for (int i = 0; i < [Link](); ++i) { void fill_fact() {
else { cout << " " << sol[i]; fact[0] = 1;
val[SCC[i][j]] = 0; } for (int i = 1; i < MN; i++) {
val[SCC[i][j] ^ 1] = 1; cout << endl; fact[i] = mult(fact[i - 1], i);
} } else { }
tmpvisited[SCC[i][j]] = 1; cout << "No" << endl; }
} }
} } long long perm_rep(vector<int> &frec) {
return 1; return 0; int total = 0;
} } long long den = 1;
for (int i = 0; i < (int)[Link](); i++) {
// Example of use den = mult(den, mod_inv(fact[frec[i]]));
total += frec[i];
int main() { }
return mult(fact[total], den);
int m, u, v, nc = 0, t; cin >> t; }
// n = "nodes" number, m = clauses number

while (t--) {
cin >> m >> n; 6.3 cumulative sum of divisors
Sample Team Name (Sample University Name) 17

struct cpx { }
/** double real, image; if (DFT == -1) for (int i = 0; i < len; i++) A[i].real /=
The function SOD(n) (sum of divisors) is defined cpx(double _real, double _image) { len, A[i].image /= len;
as the summation of all the actual divisors of real = _real; for (int i = 0; i < len; i++) a[i] = A[i];
an integer number n. For example, image = _image; return;
} }
SOD(24) = 2+3+4+6+8+12 = 35. cpx(){}
}; cpx in[1 << 20];
The function CSOD(n) (cumulative SOD) of an integer n, is
defined as below: cpx operator + (const cpx &c1, const cpx &c2) { void solve(int n) {
return cpx([Link] + [Link], [Link] + [Link]); memset(d, 0, sizeof d);
csod(n) = \sum_{i = 1}^{n} sod(i) } int t;
for (int i = 0; i < n; ++i) {
It can be computed in O(sqrt(n)): cpx operator - (const cpx &c1, const cpx &c2) { cin >> t;
*/ return cpx([Link] - [Link], [Link] - [Link]); d[t] = true;
} }
long long csod(long long n) { int m;
long long ans = 0; cpx operator * (const cpx &c1, const cpx &c2) { cin >> m;
for (long long i = 2; i * i <= n; ++i) { return cpx([Link]*[Link] - [Link]*[Link], [Link]*c2 vector<int> q(m);
long long j = n / i; .image + [Link]*[Link]); for (int i = 0; i < m; ++i)
ans += (i + j) * (j - i + 1) / 2; } cin >> q[i];
ans += i * (j - i);
} int rev(int id, int len) { for (int i = 0; i < MN; ++i) {
return ans; int ret = 0; if (d[i])
} for (int i = 0; (1 << i) < len; i++) { in[i] = cpx(1, 0);
ret <<= 1; else
if (id & (1 << i)) ret |= 1; in[i] = cpx(0, 0);
} }
6.4 fft return ret;
} FFT(in, MN, 1);
/** for (int i = 0; i < MN; ++i) {
* Fast Fourier Transform. cpx A[1 << 20]; in[i] = in[i] * in[i];
* Useful to compute convolutions. }
* computes: void FFT(cpx *a, int len, int DFT) { FFT(in, MN, -1);
* C(f star g)[n] = sum_m(f[m] * g[n - m]) for (int i = 0; i < len; i++)
* for all n. A[rev(i, len)] = a[i]; int ans = 0;
* test: icpc live archive, 6886 - Golf Bot for (int s = 1; (1 << s) <= len; s++) { for (int i = 0; i < [Link](); ++i) {
* */ int m = (1 << s); if (in[q[i]].real > 0.5 || d[q[i]]) {
cpx wm = cpx(cos( DFT * 2 * PI / m), sin(DFT * 2 * PI / m ans++;
)); }
using namespace std; for(int k = 0; k < len; k += m) { }
#include<bits/stdc++.h> cpx w = cpx(1, 0); cout << ans << endl;
#define D(x) cout << #x " = " << (x) << endl for(int j = 0; j < (m >> 1); j++) { }
#define endl ’\n’ cpx t = w * A[k + j + (m >> 1)];
cpx u = A[k + j]; int main() {
const int MN = 262144 << 1; A[k + j] = u + t; ios_base::sync_with_stdio(false);[Link](NULL);
int d[MN + 10], d2[MN + 10]; A[k + j + (m >> 1)] = u - t; int n;
w = w * wm; while (cin >> n)
} solve(n);
const double PI = acos(-1.0); } return 0;
Sample Team Name (Sample University Name) 18

} } matrix (int _r, int _c) : r (_r), c (_c) {

}; memset(m, 0, sizeof m);
}
6.5 fibonacci properties void print() {
6.7 sigma function for (int i = 0; i < r; ++i) {
Let A, B and n be integer numbers. for (int j = 0; j < c; ++j)
the sigma function is defined as: cout << m[i][j] << " ";
k =A−B (1) X cout << endl;
σx (n) = dx }
d|n
}
FA FB = Fk+1 FA2 + Fk FA FA−1 (2)
when x = 0 is called the divisor function, that counts int x[MN][MN];
matrix & operator *= (const matrix &o) {
n
X the number of positive divisors of n. memset(x, 0, sizeof x);
Fi2 = Fn+1 Fn (3) Now, we are interested in find for (int i = 0; i < r; ++i)
i=0 X for (int k = 0; k < c; ++k)
σ0 (d) if (m[i][k] != 0)
ev(n) = returns 1 if n is even. for (int j = 0; j < c; ++j) {
d|n
x[i][j] = (x[i][j] + ((m[i][k] * o.m[k][j]) % mod
n
X
2 if n is written as prime factorization: ) ) % mod;
Fi Fi+1 = Fn+1 − ev(n) (4) }
i=0 memcpy(m, x, sizeof(m));
k
Y return *this;
n
X n−1
X n= Piek }
Fi Fi−1 = Fi Fi+1 (5) i=1 };
i=0 i=0
we can demonstrate that: void matrix_pow(matrix b, long long e, matrix &res) {
memset(res.m, 0, sizeof res.m);
6.6 polynomials X k
Y for (int i = 0; i < b.r; ++i)
σ0 (d) = g(ek + 1) res.m[i][i] = 1;
const double pi = acos(-1); d|n i=1
struct poly { if (e == 0) return;
deque<double> coef; where g(x) is the sum of the first x positive numbers: while (true) {
double x_lo, x_hi; if (e & 1) res *= b;
if ((e >>= 1) == 0) break;
double evaluate(double x) { g(x) = (x ∗ (x + 1))/2 b *= b;
double ans = 0; }
for (auto it : coef) }
ans = (ans * x + it);
return ans;
7 Matrix
}
7.1 matrix 8 Misc
double volume(double x, double dx=1e-6) {
dx = (x_hi - x_lo) / 1000000.0; const int MN = 111;
double ans = 0; const int mod = 10000; 8.1 Template Java
for (double ix = x_lo; ix <= x; ix += dx) {
double rad = evaluate(ix); struct matrix { import [Link].*;
ans += pi * rad * rad * dx; int r, c; import [Link];
} int m[MN][MN];
return ans; public class Template {
Sample Team Name (Sample University Name) 19

} int date_to_days(int d, int m, int y)

public static void main(String []args) throws IOException {
{ class OutputWriter{ return (y - 1) * 365 + leap_years(y - 1) + (is_leap(y) ? B
Scanner in = new Scanner([Link]); BufferedWriter writer; [m] : A[m]) + d;
OutputWriter out = new OutputWriter([Link]); }
Task solver = new Task(); public OutputWriter(OutputStream stream){ void days_to_date(int days, int &d, int &m, int &y)
[Link](in, out); writer = new BufferedWriter(new OutputStreamWriter( {
[Link](); stream)); bool top100; // are we in the top 100 years of a 400 block
} } ?
bool top4; // are we in the top 4 years of a 100 block?
} public void print(int i) throws IOException { bool top1; // are we in the top year of a 4 block?
[Link](i);
class Task{ } y = 1;
public void solve(Scanner in, OutputWriter out){ top100 = top4 = top1 = false;
public void print(String s) throws IOException {
} [Link](s); y += ((days-1) / p400) * 400;
} } d = (days-1) % p400 + 1;

class Scanner{ public void print(char []c) throws IOException { if (d > p100*3) top100 = true, d -= 3*p100, y += 300;
public BufferedReader reader; [Link](c); else y += ((d-1) / p100) * 100, d = (d-1) % p100 + 1;
public StringTokenizer st; }
public void close() throws IOException { if (d > p4*24) top4 = true, d -= 24*p4, y += 24*4;
public Scanner(InputStream stream){ [Link](); else y += ((d-1) / p4) * 4, d = (d-1) % p4 + 1;
reader = new BufferedReader(new InputStreamReader( }
stream)); if (d > p1*3) top1 = true, d -= p1*3, y += 3;
st = null; } else y += (d-1) / p1, d = (d-1) % p1 + 1;
}
const int *ac = top1 && (!top4 || top100) ? B : A;
public String next(){ for (m = 1; m < 12; ++m) if (d <= ac[m + 1]) break;
while(st == null || ![Link]()){ 8.2 dates d -= ac[m];
try{ }
String line = [Link](); //
if(line == null) return null; // Time - Leap years
st = new StringTokenizer(line); //
}catch (Exception e){
8.3 fraction
throw (new RuntimeException()); // A[i] has the accumulated number of days from months
} previous to i struct frac{
} const int A[13] = { 0, 0, 31, 59, 90, 120, 151, 181, 212, long long x, y;
return [Link](); 243, 273, 304, 334 }; frac(long long a, long long b) {
} // same as A, but for a leap year long long g = __gcd(a, b);
const int B[13] = { 0, 0, 31, 60, 91, 121, 152, 182, 213, x = a / g;
public int nextInt(){ 244, 274, 305, 335 }; y = b / g;
return [Link](next()); // returns number of leap years up to, and including, y }
} int leap_years(int y) { return y / 4 - y / 100 + y / 400; } bool operator < (const frac &o) const {
public long nextLong(){ bool is_leap(int y) { return y % 400 == 0 || (y % 4 == 0 && return (x * o.y < y * o.x);
return [Link](next()); y % 100 != 0); } }
} // number of days in blocks of years };
public double nextDouble(){ const int p400 = 400*365 + leap_years(400);
return [Link](next()); const int p100 = 100*365 + leap_years(100);
} const int p4 = 4*365 + 1; 8.4 io
const int p1 = 365;
Sample Team Name (Sample University Name) 20

/* Returns the convolution of the two given vectors in time long long x1, y1;
// taken from : [Link] proportional to n*log(n). long long d = gcd(b % a, a, x1, y1);
solved/c-e/diablo/[Link] * The number of roots of unity to use nroots_unity must be x = y1 - (b / a) * x1;
// this is very fast as well : [Link] set so that the product of the first y = x1;
code/blob/master/code/[Link] * nroots_unity primes of the vector nth_roots_unity is return d;
greater than the maximum value of the }
typedef unsigned int u32; * convolution. Never use sizes of vectors bigger than 2^24,
#define BUF 524288 if you need to change the values of bool find_any_solution(long long a, long long b, long long c
struct Reader { * the nth roots of unity to appropriate primes for those , long long &x0,
char buf[BUF]; char b; int bi, bz; sizes. long long &y0, long long &g) {
Reader() { bi=bz=0; read(); } */ g = gcd(abs(a), abs(b), x0, y0);
void read() { vector<LL> convolve(const vector<LL> &a, const vector<LL> &b if (c % g) {
if (bi==bz) { bi=0; bz = fread(buf, 1, BUF, stdin); } , int nroots_unity = 2) { return false;
b = bz ? buf[bi++] : 0; } int N = 1 << ceil_log2([Link]() + [Link]()); }
void skip() { while (b > 0 && b <= 32) read(); } vector<LL> ans(N,0), fA(N), fB(N), fC(N);
u32 next_u32() { LL modulo = 1; x0 *= c / g;
u32 v = 0; for (skip(); b > 32; read()) v = v*10 + b-48; for (int times = 0; times < nroots_unity; times++) { y0 *= c / g;
return v; } fill([Link](), [Link](), 0); if (a < 0) x0 = -x0;
int next_int() { fill([Link](), [Link](), 0); if (b < 0) y0 = -y0;
int v = 0; bool s = false; for (int i = 0; i < [Link](); i++) fA[i] = a[i]; return true;
skip(); if (b == ’-’) { s = true; read(); } for (int i = 0; i < [Link](); i++) fB[i] = b[i]; }
for (; 48<=b&&b<=57; read()) v = v*10 + b-48; return s ? LL prime = nth_roots_unity[times].first;
-v : v; } LL inv_modulo = mod_inv(modulo % prime, prime); void shift_solution(long long &x, long long &y, long long a,
char next_char() { skip(); char c = b; read(); return c; } LL normalize = mod_inv(N, prime); long long b,
}; ntfft(fA, 1, nth_roots_unity[times]); long long cnt) {
ntfft(fB, 1, nth_roots_unity[times]); x += cnt * b;
for (int i = 0; i < N; i++) fC[i] = (fA[i] * fB[i]) % y -= cnt * a;
prime; }
ntfft(fC, -1, nth_roots_unity[times]);
9 Number theory for (int i = 0; i < N; i++) { long long find_all_solutions(long long a, long long b, long
LL curr = (fC[i] * normalize) % prime; long c,
LL k = (curr - (ans[i] % prime) + prime) % prime; long long minx, long long maxx, long long miny,
9.1 convolution k = (k * inv_modulo) % prime; long long maxy) {
ans[i] += modulo * k; long long x, y, g;
typedef long long int LL; } if (!find_any_solution(a, b, c, x, y, g)) return 0;
typedef pair<LL, LL> PLL; modulo *= prime; a /= g;
} b /= g;
inline bool is_pow2(LL x) { return ans;
return (x & (x-1)) == 0; } long long sign_a = a > 0 ? +1 : -1;
} long long sign_b = b > 0 ? +1 : -1;

inline int ceil_log2(LL x) { shift_solution(x, y, a, b, (minx - x) / b);

int ans = 0; 9.2 diophantine equations if (x < minx) shift_solution(x, y, a, b, sign_b);
--x; if (x > maxx) return 0;
while (x != 0) { long long gcd(long long a, long long b, long long &x, long long long lx1 = x;
x >>= 1; long &y) {
ans++; if (a == 0) { shift_solution(x, y, a, b, (maxx - x) / b);
} x = 0; if (x > maxx) shift_solution(x, y, a, b, -sign_b);
return ans; y = 1; long long rx1 = x;
} return b;
}
Sample Team Name (Sample University Name) 21

shift_solution(x, y, a, b, -(miny - y) / a); }

if (y < miny) shift_solution(x, y, a, b, -sign_a); void ext_euclid(long long a, long long b, long long &x, long return next != 1;
if (y > maxy) return 0; long &y, long long &g) { }
long long lx2 = x; x = 0, y = 1, g = b;
long long m, n, q, r;
shift_solution(x, y, a, b, -(maxy - y) / a); for (long long u = 1, v = 0; a != 0; g = a, a = r) { // Checks if a number is prime with prob 1 - 1 / (2 ^ it)
if (y > maxy) shift_solution(x, y, a, b, sign_a); q = g / a, r = g % a; // D(miller_rabin(99999999999999997LL) == 1);
long long rx2 = x; m = x - u * q, n = y - v * q; // D(miller_rabin(9999999999971LL) == 1);
x = u, y = v, u = m, v = n; // D(miller_rabin(7907) == 1);
if (lx2 > rx2) swap(lx2, rx2); } bool miller_rabin(long long n, int it = rounds) {
long long lx = max(lx1, lx2); } if (n <= 1) return false;
long long rx = min(rx1, rx2); if (n == 2) return true;
if (n % 2 == 0) return false;
if (lx > rx) return 0; for (int i = 0; i < it; ++i) {
return (rx - lx) / abs(b) + 1; 9.5 highest exponent factorial long long a = rand() % (n - 1) + 1;
} if (witness(a, n)) {
int highest_exponent(int p, const int &n){ return false;
int ans = 0; }
int t = p; }
9.3 discrete logarithm while(t <= n){ return true;
ans += n/t; }
t*=p;
// Computes x which a ^ x = b mod n. }
return ans;
long long d_log(long long a, long long b, long long n) { } 9.7 mod integer
long long m = ceil(sqrt(n));
long long aj = 1; template<class T, T mod>
map<long long, long long> M; struct mint_t {
for (int i = 0; i < m; ++i) { 9.6 miller rabin T val;
if () mint_t() : val(0) {}
M[aj] = i; const int rounds = 20; mint_t(T v) : val(v % mod) {}
aj = (aj * a) % n;
} // checks whether a is a witness that n is not prime, 1 < a mint_t operator + (const mint_t& o) const {
< n return (val + [Link]) % mod;
long long coef = mod_pow(a, n - 2, n); bool witness(long long a, long long n) { }
coef = mod_pow(coef, m, n); // check as in Miller Rabin Primality Test described mint_t operator - (const mint_t& o) const {
// coef = a ^ (-m) long long u = n - 1; return (val - [Link]) % mod;
long long gamma = b; int t = 0; }
for (int i = 0; i < m; ++i) { while (u % 2 == 0) { mint_t operator * (const mint_t& o) const {
if ([Link](gamma)) { t++; return (val * [Link]) % mod;
return i * m + M[gamma]; u >>= 1; }
} else { } };
gamma = (gamma * coef) % n; long long next = mod_pow(a, u, n);
} if (next == 1) return false; typedef mint_t<long long, 998244353> mint;
} long long last;
return -1; for (int i = 0; i < t; ++i) {
} last = next;
next = mod_mul(last, last, n); 9.8 mod inv
if (next == 1) {
9.4 ext euclidean return last != n - 1; long long mod_inv(long long n, long long m) {
} long long x, y, gcd;
Sample Team Name (Sample University Name) 22

ext_euclid(n, m, x, y, gcd); * but is different from 1 for all smaller powers */ }

if (gcd != 1) vector<PLL> nth_roots_unity {
return 0; {1224736769,330732430},{1711276033,927759239},{167772161,167489322},
return (x + m) % m;
} 9.12 primes
{469762049,343261969},{754974721,643797295},{1107296257,883865065}};

namespace primes {
PLL ext_euclid(LL a, LL b) { const int MP = 100001;
9.9 mod mul if (b == 0) bool sieve[MP];
return make_pair(1,0); long long primes[MP];
// Computes (a * b) % mod pair<LL,LL> rc = ext_euclid(b, a % b); int num_p;
long long mod_mul(long long a, long long b, long long mod) { return make_pair([Link], [Link] - (a / b) * [Link] void fill_sieve() {
long long x = 0, y = a % mod; ); num_p = 0;
while (b > 0) { } sieve[0] = sieve[1] = true;
if (b & 1) for (long long i = 2; i < MP; ++i) {
x = (x + y) % mod; //returns -1 if there is no unique modular inverse if (!sieve[i]) {
y = (y * 2) % mod; LL mod_inv(LL x, LL modulo) { primes[num_p++] = i;
b /= 2; PLL p = ext_euclid(x, modulo); for (long long j = i * i; j < MP; j += i)
} if ( ([Link] * x + [Link] * modulo) != 1 ) sieve[j] = true;
return x % mod; return -1; }
} return ([Link]+modulo) % modulo; }
} }

// Finds prime numbers between a and b, using basic primes

9.10 mod pow //Number theory fft. The size of a must be a power of 2 up to sqrt(b)
void ntfft(vector<LL> &a, int dir, const PLL &root_unity) { // a must be greater than 1.
// Computes ( a ^ exp ) % mod. int n = [Link](); vector<long long> seg_sieve(long long a, long long b) {
long long mod_pow(long long a, long long exp, long long mod) LL prime = root_unity.first; long long ant = a;
{ LL basew = mod_pow(root_unity.second, (prime-1) / n, prime a = max(a, 3LL);
long long ans = 1; ); vector<bool> pmap(b - a + 1);
while (exp > 0) { if (dir < 0) basew = mod_inv(basew, prime); long long sqrt_b = sqrt(b);
if (exp & 1) for (int m = n; m >= 2; m >>= 1) { for (int i = 0; i < num_p; ++i) {
ans = mod_mul(ans, a, mod); int mh = m >> 1; long long p = primes[i];
a = mod_mul(a, a, mod); LL w = 1; if (p > sqrt_b) break;
exp >>= 1; for (int i = 0; i < mh; i++) { long long j = (a + p - 1) / p;
} for (int j = i; j < n; j += m) { for (long long v = (j == 1) ? p + p : j * p; v <= b; v
return ans; int k = j + mh; += p) {
} LL x = (a[j] - a[k] + prime) % prime; pmap[v - a] = true;
a[j] = (a[j] + a[k]) % prime; }
a[k] = (w * x) % prime; }
} vector<long long> ans;
9.11 number theoretic transform w = (w * basew) % prime; if (ant == 2) ans.push_back(2);
} int start = a % 2 ? 0 : 1;
typedef long long int LL; basew = (basew * basew) % prime; for (int i = start, I = b - a + 1; i < I; i += 2)
typedef pair<LL, LL> PLL; } if (pmap[i] == false)
int i = 0; ans.push_back(a + i);
/* The following vector of pairs contains pairs (prime, for (int j = 1; j < n - 1; j++) { return ans;
generator) for (int k = n >> 1; k > (i ^= k); k >>= 1); }
* where the prime has an Nth root of unity for N being a if (j < i) swap(a[i], a[j]);
power of two. } vector<pair<int, int>> factor(int n) {
* The generator is a number g s.t g^(p-1)=1 (mod p) vector<pair<int, int>> ans;
Sample Team Name (Sample University Name) 23

if (n == 0) return ans; 10 Strings

for (int i = 0; primes[i] * primes[i] <= n; ++i) { int match(const string &str) const {
if ((n % primes[i]) == 0) { int res = 0;
int expo = 0; 10.1 Incremental Aho Corasick for(const Node *t : roots)
while ((n % primes[i]) == 0) { res += matchPMA(t, str);
expo++; class IncrementalAhoCorasic { return res;
n /= primes[i]; static const int Alphabets = 26; }
} static const int AlphabetBase = ’a’;
ans.emplace_back(primes[i], expo); struct Node { private:
} Node *fail; static void makePMA(vector<String>::const_iterator begin,
} Node *next[Alphabets]; vector<String>::const_iterator end, Node *nodes,
int sum; vector<Node*> &que) {
if (n > 1) { Node() : fail(NULL), next{}, sum(0) { } int nNodes = 0;
ans.emplace_back(n, 1); }; Node *root = new(&nodes[nNodes ++]) Node();
} for(auto it = begin; it != end; ++ it) {
return ans; struct String { Node *t = root;
} string str; for(char c : it->str) {
} int sign; Node *&n = t->next[c - AlphabetBase];
}; if(n == nullptr)
n = new(&nodes[nNodes ++]) Node();
public: t = n;
9.13 totient sieve //totalLen = sum of (len + 1) }
void init(int totalLen) { t->sum += it->sign;
[Link](totalLen); }
for (int i = 1; i < MN; i++) nNodes = 0; int qt = 0;
phi[i] = i; [Link](); for(Node *&n : root->next) {
[Link](); if(n != nullptr) {
for (int i = 1; i < MN; i++) [Link](); n->fail = root;
if (!sieve[i]) // is prime [Link](totalLen); que[qt ++] = n;
for (int j = i; j < MN; j += i) } } else {
phi[j] -= phi[j] / i;
n = root;
void insert(const string &str, int sign) { }
strings.push_back(String{ str, sign }); }
roots.push_back([Link]() + nNodes); for(int qh = 0; qh != qt; ++ qh) {
9.14 totient sizes.push_back(1); Node *t = que[qh];
nNodes += (int)[Link]() + 1; int a = 0;
long long totient(long long n) { auto check = [&]() { return [Link]() > 1 && [Link] for(Node *n : t->next) {
if (n == 1) return 0; ()[-1] == [Link]()[-2]; }; if(n != nullptr) {
long long ans = n; if(!check()) que[qt ++] = n;
for (int i = 0; primes[i] * primes[i] <= n; ++i) { makePMA([Link]() - 1, [Link](), [Link](), Node *r = t->fail;
if ((n % primes[i]) == 0) { que); while(r->next[a] == nullptr)
while ((n % primes[i]) == 0) n /= primes[i]; while(check()) { r = r->fail;
ans -= ans / primes[i]; int m = [Link](); n->fail = r->next[a];
} roots.pop_back(); n->sum += r->next[a]->sum;
} sizes.pop_back(); }
if (n > 1) { [Link]() += m; ++ a;
ans -= ans / n; if(!check()) }
} makePMA([Link]() - m * 2, [Link](), roots. }
return ans; back(), que); }
} }
}
Sample Team Name (Sample University Name) 24

static int matchPMA(const Node *t, const string &str) { int lmsr() {
int res = 0; string s; SuffixArray(const string &s) : N([Link]()) , s(s), P(1,
for(char c : str) { cin >> s; vector<int> (N, 0)), M(N) {
int a = c - AlphabetBase; int n = [Link](); for (int i = 0; i < N; ++i)
while(t->next[a] == nullptr) s += s; P[0][i] = (int) s[i];
t = t->fail; vector<int> f([Link](), -1);
t = t->next[a]; int k = 0; for (int skip = 1, level = 1; skip < N; skip *= 2, level
res += t->sum; for (int j = 1; j < 2 * n; ++j) { ++) {
} int i = f[j - k - 1]; P.push_back(vector<int>(N, 0));
return res; while (i != -1 && s[j] != s[k + i + 1]) { for (int i = 0 ; i < N; ++i) {
} if (s[j] < s[k + i + 1]) int next = ((i + skip) < N) ? P[level - 1][i + skip]
k = j - i - 1; : -10000;
i = f[i]; M[i] = entry(P[level - 1][i], next, i);
vector<Node> nodes; } }
int nNodes; if (i == -1 && s[j] != s[k + i + 1]) { sort([Link](), [Link]());
vector<String> strings; if (s[j] < s[k + i + 1]) { for (int i = 0; i < N; ++i)
vector<Node*> roots; k = j; P[level][M[i].p] = (i > 0 and M[i].a == M[i - 1].a
vector<int> sizes; } and M[i].b == M[i - 1].b) ? P[level][M[i - 1].p]
vector<Node*> que; f[j - k] = -1; : i;
}; } else { }
f[j - k] = i + 1; }
int main() { }
int m; } vector<int> getSuffixArray(){
while(~scanf("%d", &m)) { return k; vector<int> &rank = [Link]();
IncrementalAhoCorasic iac; } vector<pair<int, int> > inv([Link]());
[Link](600000); for (int i = 0; i < [Link](); ++i)
rep(i, m) { inv[i] = make_pair(rank[i], i);
int ty; sort([Link](), [Link]());
char s[300001]; 10.3 suffix array vector<int> sa([Link]());
scanf("%d%s", &ty, s); for (int i = 0; i < [Link](); ++i)
if(ty == 1) { /** sa[i] = inv[i].second;
[Link](s, +1); * O (n log^2 (n)) return sa;
} else if(ty == 2) { * See [Link] }
[Link](s, -1); for reference
} else if(ty == 3) { * */ // returns the length of the longest common prefix of s[i
int ans = [Link](s); ...L-1] and s[j...L-1]
printf("%d\n", ans); struct entry{ int lcp(int i, int j) {
fflush(stdout); int a, b, p; int len = 0;
} else { entry(){} if (i == j) return N - i;
abort(); entry(int x, int y, int z): a(x), b(y), p(z){} for (int k = [Link]() - 1; k >= 0 && i < N && j < N; --k)
} bool operator < (const entry &o) const { {
} return (a == o.a) ? (b == o.b) ? ( p < o.p) : (b < o.b) : if (P[k][i] == P[k][j]) {
} (a < o.a); i += 1 << k;
return 0; } j += 1 << k;
} }; len += 1 << k;
}
struct SuffixArray{ }
const int N; return len;
10.2 minimal string rotation string s; }
vector<vector<int> > P; };
// Lexicographically minimal string rotation vector<entry> M;
Sample Team Name (Sample University Name) 25

10.4 suffix automaton sa[cur].[Link](); vector<int> compute_z(const string &s){

sa[cur].num_paths = 0; int n = [Link]();
/* int p; vector<int> z(n,0);
* Suffix automaton: for (p = last; p != -1 && !sa[p].[Link](c); p = sa[p]. int l,r;
* This implementation was extended to maintain (online) the link) { r = l = 0;
* number of different substrings. This is equivalent to sa[p].next[c] = cur; for(int i = 1; i < n; ++i){
compute sa[cur].num_paths += sa[p].num_paths; if(i > r) {
* the number of paths from the initial state to all the tot_paths += sa[p].num_paths; l = r = i;
other } while(r < n and s[r - l] == s[r])r++;
* states. z[i] = r - l;r--;
* if (p == -1) { }else{
* The overall complexity is O(n) sa[cur].link = 0; int k = i-l;
* can be tested here: [Link] } else { if(z[k] < r - i +1) z[i] = z[k];
judge/en/problems/view/1530 int q = sa[p].next[c]; else {
* */ if (sa[p].len + 1 == sa[q].len) { l = i;
sa[cur].link = q; while(r < n and s[r - l] == s[r])r++;
struct state { } else { z[i] = r - l;r--;
int len, link; int clone = sz++; }
long long num_paths; sa[clone].len = sa[p].len + 1; }
map<int, int> next; sa[clone].next = sa[q].next; }
}; sa[clone].num_paths = 0; return z;
sa[clone].link = sa[q].link; }
const int MN = 200011; for (; p!= -1 && sa[p].next[c] == q; p = sa[p].link) {
state sa[MN << 1]; sa[p].next[c] = clone; int main(){
int sz, last; sa[q].num_paths -= sa[p].num_paths;
long long tot_paths; sa[clone].num_paths += sa[p].num_paths; //string line;cin>>line;
} string line = "alfalfa";
void sa_init() { sa[q].link = sa[cur].link = clone; vector<int> z = compute_z(line);
sz = 1; }
last = 0; } for(int i = 0; i < [Link](); ++i ){
sa[0].len = 0; last = cur; if(i)cout<<" ";
sa[0].link = -1; } cout<<z[i];
sa[0].[Link](); }
sa[0].num_paths = 1; cout<<endl;
tot_paths = 0;
} 10.5 z algorithm // must print "0 0 0 4 0 0 1"

void sa_extend(int c) { using namespace std; return 0;

int cur = sz++; #include<bits/stdc++.h> }
sa[cur].len = sa[last].len + 1;