4.1 Edmons-Karp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13
Fast and Fourier ICPC Team Notebook 4.2 Dinic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.3 Push-Relabel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Contents 4.4 Konig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.5 MCBM Augmenting Algorithm . . . . . . . . . . . . . . . . . . . . . 15
1 C++ 2 4.6 Hungarian Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1 C++ template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
4.7 Min-Cost Max-Flow Algorithm . . . . . . . . . . . . . . . . . . . . . 16
1.2 Opcion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4.8 Min-Cost Max-Flow Algorithm 2 . . . . . . . . . . . . . . . . . . . . 17
1.3 Bits Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4.9 Blossom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Custom Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5 Data Structures 18
1.6 Other . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5.1 Disjoint Set Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 SQRT Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Strings 4 5.3 Fenwick Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Z’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5.4 Fenwick Tree 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5.5 Segment Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Manacher Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.6 ST Lazy Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Minimum Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.7 Persistent ST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.8 Segtree 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7 Suffix Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.9 RSQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.8 Aho-Corasick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 5.10 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1

2.9 Suffix Automaton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 5.11 Sack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.10 Palindromic Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5.12 Heavy Light Decomposition . . . . . . . . . . . . . . . . . . . . . . . 22
5.13 Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Graph algorithms 7 5.14 Implicit Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1 Articulation Points and Bridges . . . . . . . . . . . . . . . . . . . . . 7 5.15 Implicit Treap Father . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Biconnected Components . . . . . . . . . . . . . . . . . . . . . . . . 8 5.16 Ordered Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5.17 Mo’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.4 Kosaraju: Strongly connected components . . . . . . . . . . . . . . . 9
3.5 Tarjan: Strongly connected components . . . . . . . . . . . . . . . . 9 6 Math 25
3.6 MST Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.1 Sieve of Eratosthenes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.7 MST Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.2 Count primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.8 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.3 Segmented Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.9 Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.4 Polynomial Multiplication . . . . . . . . . . . . . . . . . . . . . . . . 25
3.10 Shortest Path Faster Algorithm . . . . . . . . . . . . . . . . . . . . . 10 6.5 Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.11 Floyd-Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.6 FHT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.12 LCA Binary Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.7 Fibonacci Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.13 2 SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.8 Matrix Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.14 Centroid Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.9 Binary Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.15 Tree Binarization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.10 Euler’s Totient Function . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.16 Eulerian Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.11 Extended Euclidean (Diophantic) . . . . . . . . . . . . . . . . . . . . 27
6.12 Inversa modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Flows 13 6.13 Legendre’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.14 Mobious . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.15 Miller Rabin Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 String Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.16 Pollard Rho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
6.17 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . 29 Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.18 Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Bit tricks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.19 Gauss Jordan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.20 Gauss Jordan Modular . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.21 Berlekamp Massey . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1 C++
7 Dynamic Programming 32
7.1 Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7.2 Longest common subsequence . . . . . . . . . . . . . . . . . . . . . . 32
1.1 C++ template
7.3 Longest increasing subsequence . . . . . . . . . . . . . . . . . . . . . 32
#include <bits/stdc++.h>
7.4 Trick to merge intervals . . . . . . . . . . . . . . . . . . . . . . . . . 32
7.5 Trick Sets DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 #define fi first
7.6 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 #define se second
#define forn(i,n) for(int i=0; i< (int)n; ++i)
7.7 Knuth’s Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 33 #define for1(i,n) for(int i=1; i<= (int)n; ++i)
7.8 Convex Hull Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 #define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
7.9 CH Trick Dynamic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 #define ford(i,n) for(int i=(int)(n) - 1; i>= 0; --i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
8 Geometry 34 #define el ’\n’
8.1 Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 #define d(x) cout<< #x<< " " << x<<el
2

8.2 Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 #define ri(n) scanf("%d",&n)

8.3 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 #define sz(v) ((int)v.size())
#define all(v) v.begin(),v.end()
8.4 Polygon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 #define allr(v) v.rbegin(),v.rend()
8.5 Circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
8.6 Radial Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 using namespace std;
8.7 Coords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 typedef long long ll;
8.8 Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 typedef double ld;
typedef pair<int,int> ii;
8.9 Halfplane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 typedef pair<char,int> pci;
8.10 Sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 typedef tuple<int, int, int> tiii;
8.11 Polih . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 typedef pair<ll,ll> pll;
typedef vector<int> vi;
8.12 Line3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8.13 Point3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 const int inf = 1e9;
8.14 Plane3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 const int nax = 1e5+200;
const ld pi = acos(-1);
const ld eps= 1e-9;
9 Miscellaneous 43
9.1 Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 int dr[] = {1,-1,0, 0,1,-1,-1, 1};
int dc[] = {0, 0,1,-1,1, 1,-1,-1};
9.2 Expression Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
9.3 Ternary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 int main(){
ios_base::sync_with_stdio(false);

1
cin.tie(NULL); cout.tie(NULL);
10 Theory 45 cout << setprecision(20)<< fixed;

C++
DP Optimization Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 }
Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.2
// or
1.2 Opcion random_device rd
mt19937 / mt19937_64 rng(rd())

Opcion
// En caso de que no sirva #include <bits/stdc++.h> // Use it to shuffle a vector
#include <algorithm> shuffle(permutation.begin(), permutation.end(), rng)
#include <iostream> // Use it to generate a random number between [fr, to]
#include <iterator> uniform_int_distribution<T> / uniform_real_distribution<T
#include <sstream> > dis(fr, to);
#include <fstream> dis(rng)
#include <cassert>
#include <climits> int rand(int a, int b) {
#include <cstdlib> return uniform_int_distribution<int>(a, b)(rng);
#include <cstring> }
#include <string>
#include <cstdio>
#include <vector> 1.5 Custom Hash
#include <cmath>
#include <queue> struct custom_hash {
#include <deque> static ll splitmix64(ll x) {
#include <stack> // http://xorshift.di.unimi.it/splitmix64.c
#include <list> x += 0x9e3779b97f4a7c15;
#include <map> x = (x ˆ (x >> 30)) * 0xbf58476d1ce4e5b9;
#include <set> x = (x ˆ (x >> 27)) * 0x94d049bb133111eb;
#include <bitset> return x ˆ (x >> 31);
#include <iomanip> }
#include <unordered_map>
3

size_t operator()(ll x) const {

//// static const ll FIXED_RANDOM = chrono::
#include <tuple> steady_clock::now().time_since_epoch().count()
#include <random> ;
#include <chrono> return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<ll,int, custom_hash> mapa;
1.3 Bits Manipulation

mask |= (1<<n) // PRENDER BIT-N 1.6 Other

mask ˆ= (1<<n) // FLIPPEAR BIT-N
mask &= ˜(1<<n) // APAGAR BIT-N #pragma GCC optimize("O3")
if(mask&(1<<n)) // CHECKEAR BIT-N //(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
T = mask&(-mask); // LSO #pragma comment(linker, "/stack:200000000")
__builtin_ffs(mask); // INDICE DEL LSO //(UNCOMMENT WHEN NEEDED)
// iterar sobre los subconjuntos del conjunto S #pragma GCC optimize("Ofast,unroll-loops,no-stack-
for(int subset= S; subset; subset= (subset-1) & S) protector,fast-math")
for (int subset=0;subset=subset-S&S;) // Increasing #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,
order mmx,avx,tune=native")
// Custom comparator for set/map
struct comp {
1.4 Random bool operator()(const double& a, const double& b)

1
const {
// Declare number generator return a+EPS<b;}

C++
mt19937 / mt19937_64 rng(chrono::steady_clock::now(). };
time_since_epoch().count()) set<double,comp> w; // or map<double,int,comp>
pi[i] = j;
// double inf }
const double DINF=numeric_limits<double>::infinity(); return pi;
}
int main() { void kmp(string &t, string &p){ // O(|t| + |p|)
// Ouput a specific number of digits past the decimal vi phi = get_phi(p);
point, int matches = 0;
// in this case 5 for(int i = 0, j = 0; i < sz(t); ++i ) {
// #include <iomanip> while(j > 0 && t[i] != p[j] ) j = phi[j-1];
cout << setfill(’ ’) << setw(3) << 2 << endl; if(t[i] == p[j]) ++j;
cout.setf(ios::fixed); cout << setprecision(5); if(j == sz(p)) {
cout << 100.0/7.0 << endl; matches++;
cout.unsetf(ios::fixed j = phi[j-1];
}
// Output the decimal point and trailing zeros }
cout.setf(ios::showpoint); cout << 100.0 << endl; cout. }
unsetf(ios::showpoint); /// Automaton
/// Complexity O(n*C) where C is the size of the alphabet
// Output a + before positive values int aut[nax][26];
cout.setf(ios::showpos); cout << 100 << " " << -100 << void kmp_aut(string &p) {
endl; cout.unsetf(ios::showpos); int n = sz(p);
// Output numerical values in hexadecimal vi phi = get_phi(p);
cout << hex << 100 << " " << 1000 << " " << 10000 << forn(i, n+1) {
dec << endl; forn(c, 26) {
} if (i==n || (i>0 && ’a’+c!= p[i])) aut[i][c] = aut[
phi[i-1]][c];
else aut[i][c] = i + (’a’+c == p[i]);
4

}
2 Strings }
}
2.1 Z’s Algorithm /// Automaton
int wh[nax+2][MAXC]; //wh[i][j] = a donde vuelvo si
// O(|s|) estoy en i y pongo una j
vi z_function(string &s){ void build(string &s){
int n = s.size(); int lps=0;
vi z(n); wh[0][s[0]-’a’] = 1;
int x = 0, y = 0; fore(i,1,sz(s)){
for(int i = 1; i < n; ++i) { fore(j,0,MAXC-1) wh[i][j]=wh[lps][j];
z[i] = max(0, min(z[i-x], y-i+1)); if(i<sz(s)){
while (i+z[i] < n && s[z[i]] == s[i+z[i]]) wh[i][s[i]-’a’] = i+1;
x = i, y = i+z[i], z[i]++; lps = wh[lps][s[i]-’a’];
} }
return z; }
} }

2.2 KMP 2.3 Hashing

2
vi get_phi(string &s) { // O(|s|)

STRINGS
/// 1000234999, 1000567999, 1000111997, 1000777121,
int j = 0, n = sz(s); vi pi(n); 999727999, 1070777777
for1(i,n-1){ const int MODS[] = { 1001864327, 1001265673 };
while (j > 0 && s[i] != s[j]) j = pi[j-1]; const ii BASE(257, 367), ZERO(0, 0), ONE(1, 1);
j += (s[i] == s[j]); inline int add(int a, int b, const int& mod) { return a+b
2.4
>= mod ? a+b-mod : a+b; } if(i+k-f > r) l=i-k, r=i+k-f;
inline int sbt(int a, int b, const int& mod) { return a-b }
< 0 ? a-b+mod : a-b; } // forn(i,n) d[i] = (d[i]-1+f)*2 + 1-f;

Manacher Algorithm
inline int mul(int a, int b, const int& mod) { return 1ll }
*a*b%mod; }
inline ll operator ! (const ii a) { return (ll(a.fi)<<32)
|ll(a.se); } 2.5 Minimum Expression
inline ii operator + (const ii a, const ii b) {
return {add(a.fi, b.fi, MODS[0]), add(a.se, b.se, MODS
[1])}; int minExp(string &t) {
} int i = 0, j = 1, k = 0, n = sz(t), x, y;
inline ii operator - (const ii a, const ii b) { while (i < n && j < n && k < n) {
return {sbt(a.fi, b.fi, MODS[0]), sbt(a.se, b.se, MODS x = i+k;
[1])}; y = j+k;
} if (x >= n) x -= n;
inline ii operator * (const ii a, const ii b) { if (y >= n) y -= n;
return {mul(a.fi, b.fi, MODS[0]), mul(a.se, b.se, MODS if (t[x] == t[y]) ++k;
[1])}; else if (t[x] > t[y]) {
} i = j+1 > i+k+1 ? j+1 : i+k+1;
swap(i, j);
const int nax = 1e5+20; k = 0;
ii base[nax]; } else {
void prepare() { j = i+1 > j+k+1 ? i+1 : j+k+1;
base[0] = ONE; k = 0;
for1(i,nax-1) base[i] = base[i-1]*BASE; }
} }
template <class type> return i;
struct hashing { /// HACELEEE PREPAREEEE!!!
5

}
vector<ii> code;
hashing(type &t) {
code.resize(sz(t)+1);
code[0] = ZERO; 2.6 Trie
for1(i,sz(t))
code[i] = code[i-1]*BASE + ii{t[i-1], t[i-1]}; const static int N = 1<<21;
} const static int alpha = 26;
ii query(int l, int r) { /// [l,r] int trie[N][alpha], cnt[N], sz;
return code[r+1] - code[l]*base[r-l+1]; void init(){ memset(trie[0], 0 ,sizeof trie[0]); sz = 0;
} }
}; void add(const string &s){
int v= 0;
for(char ch: s){
int c = ch-’a’;
2.4 Manacher Algorithm int &next = trie[v][c];
if(!next){
// f = 1 para pares, 0 impar next = ++sz;
//a a a a a a memset(trie[next], 0, sizeof trie[next]);
//1 2 3 3 2 1 f = 0 impar }
//0 1 2 3 2 1 f = 1 par v= next;
void manacher(string &s, int f, vi &d){ }

2
int l=0, r=-1, n=sz(s); cnt[v]++;
}

STRINGS
d.assign(n,0);
forn(i, n){
int k=(i>r? (1-f) : min(d[l+r-i+ f], r-i+f)) + f;
while(i+k-f<n && i-k>=0 && s[i+k-f]==s[i-k]) ++k; 2.7 Suffix Array
d[i] = k - f; --k;
2.8
struct SuffixArray { // test line 11 int x = conv(c);
vi sa, lcp; if(!trie[cur][x]) trie[cur][x] = ++nodes;
SuffixArray(string& s, int lim=256){ cur = trie[cur][x];

Aho-Corasick
int n = sz(s) + 1, k = 0, a, b; }
s.pb(’$’); ++cnt_word[cur];
vi x(all(s)), y(n), ws(max(n, lim)), rank end_word[cur] = i; // for i > 0
(n); }
sa = lcp = y, iota(all(sa), 0); void build() { // HACELEEE build!!!!
for (int j = 0, p = 0; p < n; j = max(1, queue<int> q; q.push(0);
j * 2), lim = p) { while(sz(q)) {
p = j; int u = q.front(); q.pop();
// iota(all(y), n - j); for(int i = 0; i < alpha; ++i) {
// forn(i,n) if (sa[i] >= j) y[p++] int v = trie[u][i];
= sa[i] - j; if(!v) trie[u][i] = trie[ fail[u] ][i]; //
forn(i,n) y[i] = (sa[i] - j >= 0 construir automata
? 0 : n) + sa[i]-j; // this else q.push(v);
replace the two lines if(!u || !v) continue;
// before hopefully xd fail[v] = trie[ fail[u] ][i];
fill(all(ws), 0); fail_out[v] = end_word[ fail[v] ] ? fail[v] :
forn(i,n) ws[x[i]]++; fail_out[ fail[v] ];
for1(i,lim-1) ws[i] += ws[i - 1]; cnt_word[v] += cnt_word[ fail[v] ]; // obtener
for (int i = n; i--;) sa[--ws[x[y informacion del fail_padre
[i]]]] = y[i]; }
swap(x, y), p = 1, x[sa[0]] = 0; }
for1(i,n-1) a = sa[i - 1], b = sa }
[i], x[b] =
(y[a] == y[b] && y[a + j]
6

== y[b + j]) ? p - 1
: p++; 2.9 Suffix Automaton
}
for1(i,n-1) rank[sa[i]] = i; struct node {
for (int i = 0, j; i < n - 1; lcp[rank[i int len, link;
++]] = k) // lcp(i): lcp suffix i-1,i map<char, int> to;
for (k && k--, j = sa[rank[i] - bool terminal;
1]; };
s[i + k] == s[j +
k]; k++); const int nax = 1<<21;
} node st[nax];
}; int sz, last;
int occ[nax];
void sa_init() { ///// HACELEE INIT!!!
2.8 Aho-Corasick forn(i,sz) st[i] = node();
st[0].len = last = st[0].terminal = 0;
st[0].link = -1;
const static int N = 1<<21; sz=1;
const static int alpha = 26; }
int trie[N][alpha], fail[N], nodes, end_word[N], cnt_word
[N], fail_out[N]; void sa_extend(char c) {
inline int conv(char ch) { // Function for properly index int cur = sz++;

2
characters st[cur].len = st[last].len + 1;

STRINGS
return ((ch >= ’a’ && ch <= ’z’) ? ch-’a’ : ch-’A’+26); int p = last;
} while (p != -1 && !st[p].to.count(c)) {
void add(string &s, int i) { st[p].to[c] = cur;
int cur = 0; p = st[p].link;
for(char c : s) { }
2.10
if (p == -1) st[cur].link = 0; int link, len, p, to[SIGMA];
else { node(int len, int link=0,int p=0):
int q = st[p].to[c]; len(len),link(link),p(p){

Palindromic Tree
if (st[p].len + 1 == st[q].len) st[cur].link = q; memset(to,0,sizeof(to));
else { }
int w = sz++; };
st[w].len = st[p].len + 1; int last;
st[w].to = st[q].to; vector<node> st;
st[w].link = st[q].link; palindromic_tree():last(0){fore(i,-1,0)st.pb(node(i));}
while (p != -1 && st[p].to[c] == q) {
st[p].to[c] = w; void add(int i, const string &s){
p = st[p].link; int c = s[i]-’a’;
} int p = last;
st[q].link = st[cur].link = w; while(s[i-st[p].len-1]!=s[i]) p=st[p].link;
} if(st[p].to[c]){
} last = st[p].to[c];
last = cur; }else{
} int q=st[p].link;
void dfs(int v){ while(s[i-st[q].len-1]!=s[i]) q=st[q].link;
if(occ[v] != 0) return; q=max(1,st[q].to[c]);
occ[v] = st[v].terminal; last = st[p].to[c] = sz(st);
for(auto &e : st[v].to){ st.pb(node(st[p].len+2,q,p));
dfs(e.se); }
occ[v] += occ[e.se]; }
} };
}
7

string lcs(string &S, string &T){

sa_init(); 3 Graph algorithms
for (char c : S) sa_extend(c);
int v = 0, l = 0, best = 0, bestpos = 0; 3.1 Articulation Points and Bridges
forn(i, sz(T)){
while (v && !st[v].to.count(T[i])) { // Complexity: V + E
v = st[v].link , l = st[v].len ; // Given an undirected graph
} int n, timer, tin[nax], low[nax];
if (st[v].to.count(T[i])) { vi g[nax]; // adjacency list of graph
v = st[v].to[T[i]];
l++; void dfs(int u, int p) {
} tin[u] = low[u] = ++timer;
if (l > best) { int children=0;
best = l; for (int v : g[u]) {

3
bestpos = i; if (v == p) continue;
} if (tin[v]) low[u] = min(low[u], tin[v]);

GRAPH ALGORITHMS
} else {
// best guarda el tamano del longest common substring dfs(v, u);
return T.substr(bestpos - best + 1, best); low[u] = min(low[u], low[v]);
} if (low[v] > tin[u]) // BRIDGE
IS_BRIDGE(u, v);
if (low[v] >= tin[u] && p!=-1) // POINT
2.10 Palindromic Tree IS_CUTPOINT(u);
++children;
struct palindromic_tree{ }
static const int SIGMA = 26; }
struct node{ if(p == -1 && children > 1) // POINT
3.2
IS_CUTPOINT(u); [last].v);
} } while (last != i);
nbc++; //end biconnected

Biconnected Components
void find_articulations() { }
timer = 0; low[u] = min(low[u], low[v]);
forn(i,n) if(!tin[i]) dfs(i,-1); } else if (i != p && num[v] < num[u]) {
} st.push(i);
low[u] = min(low[u], num[v]);
}
3.2 Biconnected Components }
}
struct edge { void build_tree() {
int u, v, comp; //A que componente biconexa tree.clear(); id.resize(N); tree.reserve(2*N);
pertenece forn(u,N)
bool bridge; //Si la arista es un puente if (art[u]) id[u] = sz(tree); tree.pb({})
}; ;
for (auto &comp : comps) {
vector<int> g[nax]; //Lista de adyacencia sort(all(comp));
vector<edge> e; //Lista de aristas comp.resize(unique(all(comp)) - comp.begin());
stack<int> st; int node = sz(tree);
int low[nax], num[nax], cont; tree.pb({});
int art[nax]; //Si el nodo es un punto de articulacion for (int u : comp) {
//vector<vector<int>> comps; //Componentes biconexas if (art[u]) {
//vector<vector<int>> tree; //Block cut tree tree[id[u]].pb(node);
//vector<int> id; //Id del nodo en el block cut tree tree[node].pb(id[u]);
int nbc; //Cantidad de componentes biconexas }else id[u] = node;
int N, M; //Cantidad de nodos y aristas }
8

}
void add_edge(int u, int v){ }
g[u].pb(sz(e)); g[v].pb(sz(e)); void doit() {
e.pb({u, v, -1, false}); cont = nbc = 0;
} // comps.clear();
void dfs(int u, int p = -1) { forn(i,N) {
low[u] = num[u] = cont++; g[i].clear(); num[i] = -1; art[i] = 0;
for (int i : g[u]) { }
edge &ed = e[i]; forn(i,N){
int v = ed.uˆed.vˆu; if(num[i]<0) dfs(i), --art[i];
if(num[v]<0){ }
st.push(i); }
dfs(v, i);
if (low[v] > num[u]) ed.bridge =
true; //bridge

3
if (low[v] >= num[u]) {
3.3 Topological Sort

GRAPH ALGORITHMS
art[u]++; //articulation
int last; //start vi g[nax], ts;
biconnected bool seen[nax];
// comps.pb({}); void dfs(int u){
do { seen[u] = true;
last = st.top(); for(int v: g[u])
st.pop(); if (!seen[v])
e[last].comp = dfs(v);
nbc; ts.pb(u);
// comps.back().pb(e }
[last].u); void topo(int n){
// comps.back().pb(e forn(i,n) if (!seen[i]) dfs(i);
3.4
reverse(all(ts)); forn(i,n) if(num[i]==-1) tjn(i);
} }

Kosaraju: Strongly connected components

3.4 Kosaraju: Strongly connected components 3.6 MST Kruskal
vi g[nax], gr[nax], ts; // Complejidad O( E* log V)
int scc[nax]; struct edge{
bool seen[nax]; int u, v, w;
void dfs1(int u){ edge(int u, int v, int w):u(u),v(v),w(w){}
seen[u] = true; bool operator < (const edge &o) const{
for (int v: g[u]) return w < o.w;//if want max, change this
if (!seen[v]) }
dfs1(v); };
ts.pb(u); vector<edge> g, st;
} dsu uf; // union-find
void dfs(int u, int comp){ int kruskal(int n){
scc[u] = comp; uf.init(n);
for (int v : gr[u]) sort(all(g));
if (scc[v] == -1) int total = 0, u, v, w;
dfs(v, comp); for(int i = 0; i < sz(g) && uf.numSets!=1; ++i){
} u = g[i].u;
// Retorna la cantidad de componentes v = g[i].v;
int find_scc(int n){ w = g[i].w;
//TENER CREADO EL GRAFO REVERSADO gr if(!uf.isSameSet(u,v)){
forn(i,n) if(!seen[i]) dfs1(i); total+= w;
reverse(all(ts)); uf.unionSet(u,v);
9

int comp = 0; st.pb(g[i]);

for(int u: ts) }
if (scc[u] == -1) dfs(u, comp++); }
return comp; return total;
} }

3.5 Tarjan: Strongly connected components 3.7 MST Prim

vi low, num, comp, g[nax]; //Complexity O(E * log V)
int scc, timer; vector<ii> g[nax];
stack<int> st; bool seen[nax];
void tjn(int u) { priority_queue<ii> pq;
void process(int u) {

3
low[u] = num[u] = timer++; st.push(u); int v;
for(int v: g[u]) { seen[u] = true;

GRAPH ALGORITHMS
if(num[v]==-1) tjn(v); for (ii v: g[u])
if(comp[v]==-1) low[u] = min(low[u], low[v]); if (!seen[v.fi])
} pq.push(ii(-v.se, v.fi));
if(low[u]==num[u]) { }
do{ v = st.top(); st.pop(); comp[v]=scc; int prim(int n){
}while(u != v); process(0);
++scc; int total = 0, u, w;
} while (sz(pq)){
} ii e = pq.top(); pq.pop();
void callt(int n) { tie(w,v) = e; w*=-1;
timer = scc= 0; if (!seen[u])
num = low = comp = vector<int>(n,-1); total += w, process(u);
3.8
} dist[v] = min(dist[v], dist[u] + w);
return total; }
} }

Dijkstra
}
bool negcycle= false;
3.8 Dijkstra forn(u,n){
for(ii e: g[u]){
tie(v,w) = e;
// O ((V+E)*log V) if (dist[v] > dist[u] + w) negcycle = true;
vector <ii> g[nax]; }
int d[nax], p[nax]; }
void dijkstra(int s, int n){ }
forn(i,n) d[i] = inf, p[i] = -1;
priority_queue <ii, vector <ii>,greater<ii> > q;
d[s] = 0; 3.10 Shortest Path Faster Algorithm
q.push(ii(0, s));
int dist, u, v, w;
while(sz(q)){ // Complexity O(V*E) worst, O(E) on average.
tie(dist, u) = q.top(); vector<ii> g[nax];
q.pop(); bool inqueue[nax];
if (dist > d[u]) continue; int n;
for (ii e: g[u]){ bool spfa(int s, vi& dist) {
tie(v,w) = e; dist.assign(n, inf);
if (d[u] + w < d[v]){ vi cnt(n, 0);
d[v] = d[u] + w; queue<int> q;
p[v] = u; dist[s] = 0;
q.push(ii(d[v], v)); q.push(s);
inqueue[s] = true;
10

}
} int u, v, w;
} while(sz(q)) {
} u = q.front(); q.pop();
vi find_path(int t){ inqueue[u] = false;
vi path; for (ii e: g[u]) {
int cur = t; tie(v, w) = e;
while(cur != -1){ if (dist[u] + w < dist[v]) {
path.pb(cur); dist[v] = dist[u] + w;
cur = p[cur]; if (!inqueue[v]) {
} q.push(v);
reverse(all(path)); inqueue[v] = true;
return path; cnt[v]++;
} if (cnt[v] > n) return false; // negative
cycle

3
}
3.9 Bellman-Ford }

GRAPH ALGORITHMS
}
// O(E*V) list adjacency, O(Vˆ3) matrix }
return true;
vector<ii> g[nax]; }
int dist[nax];
void bellman_ford(int s, int n){
forn(i,n) dist[i] = inf;
dist[s] = 0; int v, w; 3.11 Floyd-Warshall
forn(i,n-1){
forn(u,n){ // Complejidad O(nˆ3)
for(ii e : g[u]){ int dist[nax][nax];
tie(v,w) = e; void floyd(){
3.12
// Hay que saber inicializar el array d. void tjn(int u) {
forn(k,n){ low[u] = num[u] = timer++; st.push(u); int v;
forn(u,n){ for(int v: g[u]) {

LCA Binary Lifting

forn(v,n){ if(num[v]==-1) tjn(v);
dist[u][v] = min(dist[u][v], dist[u][k] + dist[k if(comp[v]==-1) low[u] = min(low[u], low[v]);
][v]); }
} if(low[u]==num[u]) {
} do{ v = st.top(); st.pop(); comp[v]=scc;
} }while(u != v);
} ++scc;
}
}
3.12 LCA Binary Lifting bool solve_2SAT() {
int n = 2*N;
timer = scc= 0;
const int L = 24; num = low = comp = vi(n,-1);
int timer, up[nax][L+1], n; forn(i,n)
int in[nax], out[nax]; if(num[i]==-1) tjn(i);
vi g[nax]; truth = vector<bool>(N, false);
void dfs(int u, int p){ forn(i,N) {
in[u] = ++timer; if (comp[i] == comp[i + N]) return false;
up[u][0] = p; truth[i] = comp[i] < comp[i + N];
for1(i,L) up[u][i] = up[up[u][i-1]][i-1]; }
for(int v: g[u]){ return true;
if(v==p) continue; }
dfs(v,u); int neg(int x){
} if(x<N) return x+N;
out[u] = ++timer;
11

else return x-N;

} }
bool anc(int u, int v){ void add_edge(int x, int y){
return in[u]<= in[v] && out[u]>= out[v]; g[x].pb(y);
} }
void solve(int root){ void add_disjuntion(int x, int y){
timer = 0; add_edge(neg(x), y);
dfs(root,root); add_edge(neg(y), x);
} }
int lca(int u, int v){ void implies(int x, int y) {
if(anc(u,v)) return u; add_edge(x,y);
if(anc(v,u)) return v; add_edge(neg(y),neg(x));
for(int i= L; i>=0; --i){ }
if(!anc(up[u][i],v)) void make_true(int u) { add_edge(neg(u), u); }
u = up[u][i]; void make_false(int u) { make_true(neg(u)); }

3
} void make_eq(int x, int y){
return up[u][0]; implies(x, y);

GRAPH ALGORITHMS
} implies(y, x);
}
void make_dif(int x, int y){
3.13 2 SAT implies(neg(x), y);
implies(neg(y), x);
// Complexity O(V+E) }
int N;
vi low, num, comp, g[nax];
vector<bool> truth; 3.14 Centroid Decomposition
int scc, timer;
stack<int> st; int cnt[nax], depth[nax], f[nax], dist[25][nax];
3.15
vi g[nax]; int n;
int dfs(int u, int dep = -1, bool flag = 0, int dis = 0, int edges = 0;
int p = -1) { int out[nax], in[nax];

Tree Binarization
cnt[u] = 1;
if(flag) dist[dep][u] = dis; // Directed version (uncomment commented code for
for (int v : g[u]) undirected)
if (!depth[v] && v != p) cnt[u] += dfs(v, dep, flag, struct edge {
dis + 1, u); int v;
return cnt[u]; // list<edge>::iterator rev;
} edge(int v):v(v){}
int get_centroid (int u, int r, int p = -1) { };
for (int v : g[u]) list<edge> g[nax];
if (!depth[v] && v != p && cnt[v] > r) void add_edge(int a, int b){
return get_centroid(v, r, u); out[a]++;
return u; in[b]++;
} ++edges;
int decompose(int u, int d = 1) { g[a].push_front(edge(b));//auto ia=g[a].begin();
int centroid = get_centroid(u, dfs(u)>>1); // g[b].push_front(edge(a));auto ib=g[b].begin();
depth[centroid] = d; // ia->rev=ib;ib->rev=ia;
dfs(centroid, d); /// if distances is needed }
for (int v : g[centroid]) vi p;
if (!depth[v]) void go(int u){
f[decompose(v, d + 1)] = centroid; while(sz(g[u])){
return centroid; int v=g[u].front().v;
} //g[v].erase(g[u].front().rev);
int lca (int u, int v) { g[u].pop_front();
for (; u != v; u = f[u]) go(v);
}
12

if (depth[v] > depth[u])

swap(u, v); p.push_back(u);
return u; }
} vi get_path(int u){
int get_dist(int u, int v){ p.clear();
int dep_l = depth[lca(u,v)]; go(u);
return dist[dep_l][u] + dist[dep_l][v]; reverse(all(p));
} return p;
}
3.15 Tree Binarization /// for undirected uncomment and check for path existance
bool eulerian(vi &tour) { /// directed graph
vi g[nax]; int one_in = 0, one_out = 0, start = -1;
bool ok = true;
int son[nax], bro[nax]; for (int i = 0; i < n; i++) {
void binarize(int u, int p = -1){

3
if(out[i] && start == -1) start = i;
bool flag = 0; int prev = 0; if(out[i] - in[i] == 1) one_out++, start = i;

GRAPH ALGORITHMS
for(int v : g[u]){ else if(in[i] - out[i] == 1) one_in++;
if(v == p) continue; else ok &= in[i] == out[i];
if(flag) bro[prev] = v; }
else son[u] = v, flag = true; ok &= one_in == one_out && one_in <= 1;
binarize(v, u); if (ok) {
prev = v;
} tour = get_path(start);
} if(sz(tour) == edges + 1) return true;
}
return false;
}
3.16 Eulerian Path
return mf;
}
4 Flows };

4.1 Edmons-Karp
4.2 Dinic
// Complexity O(V*Eˆ2)
const ll inf = 1e18; // Corte minimo: vertices con dist[v]>=0 (del lado de src
) VS. dist[v]==-1 (del lado del dst)
struct EKarp{ // Para el caso de la red de Bipartite Matching (Sean V1
vector<int> q, dist, p; y V2 los conjuntos mas proximos a src y dst
vector<vector<ll>> cap, flow; respectivamente):
vector<vector<int>> g; // Reconstruir matching: para todo v1 en V1 ver las
int n, s, t; aristas a vertices de V2 con it->f>0, es arista del
Matching
EKarp(int n_){ // Min Vertex Cover: vertices de V1 con dist[v]==-1 +
n = n_; g.resize(n); vertices de V2 con dist[v]>0
cap = flow = vector<vector<ll>>(n,vector<ll>(n)); // Max Independent Set: tomar los vertices NO tomados por
} el Min Vertex Cover
void addEdge(int u, int v, ll c){ // Max Clique: construir la red de G complemento (debe
cap[u][v] = c; ser bipartito!) y encontrar un Max Independet Set
g[u].pb(v); g[v].pb(u); // Min Edge Cover: tomar las aristas del matching + para
} todo vertices no cubierto hasta el momento, tomar
cualquier arista de el
ll bfs(int s, int t) {
p.assign(n, -1); p[s] = -2; // Complexity O(Vˆ2*E)
queue<pair<int,ll>> q; const ll inf = 1e18;
13

q.push(pair<int,ll>(s, inf));
while (!q.empty()) { struct Dinic{
int u = q.front().fi; ll f = q.front().se; struct edge {
q.pop(); int to, rev; ll f, cap;
for(int v: g[u]){ edge(int to, int rev, ll cap, ll f=0) : to(to), rev(
if (p[v] == -1 && cap[u][v] - flow[u][v]>0) { rev), f(f), cap(cap) {}
p[v] = u; };
ll df = min(f, cap[u][v]-flow[u][v]); vector<vector<edge>> g;
if (v == t) return df; vector<int> q, dist, work;
q.push(pair<int,ll>(v, df)); int n, s, t;
} Dinic(int n_){
} n = n_; g.resize(n);
} q.resize(n);
return 0; }
}
ll maxFlow() { void addEdge(int s, int t, ll cap){
ll mf = 0; g[s].pb(edge(t, sz(g[t]), cap));
ll f; g[t].pb(edge(s, sz(g[s])-1, 0));
while (f = bfs(s,t)){ }
mf += f;
int v = t; bool bfs(){
while (v != s) { dist.assign(n,-1), dist[s]=0;
int qt=0;

4
int prev = p[v];
flow[v][prev] -= f; q[qt++]=s;

FLOWS
flow[prev][v] += f; for(int qh=0; qh<qt; ++qh){
v = prev; int u =q[qh];
} for(edge e: g[u]){
} int v=e.to;
4.3
if(dist[v]<0 && e.f < e.cap) return cut;
dist[v]=dist[u]+1, q[qt++]=v; }
} };

Push-Relabel
}
return dist[t]>=0;
} 4.3 Push-Relabel
ll dfs(int u, ll f){
if(u==t) return f; // Complexity O(Vˆ2 * sqrt(E)) o O(Vˆ3)
for(int &i=work[u]; i<sz(g[u]); ++i){ const ll inf = 1e17;
edge &e = g[u][i]; struct PushRelabel{
if(e.cap<=e.f) continue; struct edge {
int v=e.to; int to, rev; ll f, cap;
if(dist[v]==dist[u]+1){ edge(int to, int rev, ll cap, ll f = 0) : to(to), rev
ll df=dfs(v, min(f, e.cap-e.f)); (rev), f(f), cap(cap) {}
if(df>0){ };
e.f+=df, g[v][e.rev].f-= df; void addEdge(int s, int t, ll cap){
return df; g[s].pb(edge(t, sz(g[t]), cap));
} g[t].pb(edge(s, sz(g[s])-1, (ll)0));
} }
} int n, s, t;
return 0; vi height; vector<ll> excess;
} vector<vector<edge>> g;
ll maxFlow(int s_, int t_){ PushRelabel(int n_){
s = s_, t = t_;
ll max_flow=0; n = n_; g.resize(n);
while(bfs()){ }
void push(int u, edge &e){
14

work.assign(n,0);
while(ll delta=dfs(s,inf)) ll d = min(excess[u], e.cap - e.f);
max_flow+=delta; edge &rev = g[e.to][e.rev];
} e.f += d; rev.f -= d;
// todos los nodos con dist[u]!=-1 vs los que tienen excess[u] -= d; excess[e.to] += d;
dist[v]==-1 forman el min-cut, (u,v) }
return max_flow; void relabel(int u){
} ll d = inf;
for (edge e : g[u])
vector<ii> cut; if (e.cap - e.f > 0)
vector<bool> seen; d = min(d,(ll) height[e.to]);
void dfs_cut(int u){
seen[u] = 1; if (d < inf) height[u] = d + 1;
for(edge &e : g[u]){ }
if(!seen[e.to]){ vi find_max_height_vertices(int s, int t) {
if(dist[e.to]==-1 && e.cap!=0){ vi max_height;
cut.pb({u,e.to}); for (int i = 0; i < n; i++)
}else if(e.f < e.cap){ if (i != s && i != t && excess[i] > 0) {
dfs_cut(e.to); if (!max_height.empty() && height[i] > height[
} max_height[0]])
} max_height.clear();
} if (max_height.empty() || height[i] == height[
} max_height[0]])

4
vector<ii> min_cut(){ max_height.push_back(i);
seen.assign(n, false); }

FLOWS
dfs_cut(s); return max_height;
sort(all(cut)); }
cut.resize(unique(all(cut)) - cut.begin());
ll maxFlow(){
4.4
height.assign(n,0); excess.assign(n,0); }
ll max_flow = 0; bool pushed; while(!kq.empty()) {
vi current; int e = kq.front(); kq.pop();

Konig
if (s[e]%2==1) {
height[s] = n; excess[s] = inf; s[match[e]] = s[e]+1;
for(edge &e: g[s]) kq.push(match[e]);
push(s,e); } else {
while(!(current = find_max_height_vertices(s,t)). for(edge it: g[e])
empty()){ if (it.to < nodes-2 && s[it.to]==-1){
for(int v: current){ s[it->to] = s[e]+1;
pushed = false; kq.push(it->to);
if(excess[v]==0) continue; }
for(edge &e : g[v]){ }
if(e.cap - e.f>0 && height[v]== height[e.to]+1) }
{ }
pushed = true;
push(v,e);
} 4.5 MCBM Augmenting Algorithm
}
if(!pushed){ // O (V*E)
relabel(v); vi g[nax], seen, match;
break;
} int Aug(int l) { // return 1 if an
} augmenting path is found
} if (seen[l]) return 0; // return 0 otherwise
for (edge e : g[t]){ seen[l] = 1;
edge rev = g[e.to][e.rev]; for (int r: g[l])
15

max_flow += rev.f; if (match[r] == -1 || Aug(match[r])){

} match[r] = l; return 1;
return max_flow; // found 1 matching
} }
}; return 0;
//
no matching
}
4.4 Konig
int MCBM(int n, int vleft){
int ans = 0;
#define sz(c) ((int)c.size()) match.assign(n, -1); // V is the number of vertices
// asume que el dinic YA ESTA tirado in bipartite graph
// asume que nodes-1 y nodes-2 son la fuente y destino forn(l,vleft) { // vleft : vi with indices of
int match[maxnodes]; // match[v]=u si u-v esta en el vertices
matching, -1 si v no esta matcheado seen.assign(n, 0); // reset before
int s[maxnodes]; // numero de la bfs del koning each recursion
queue<int> kq; ans += Aug(l);
// s[e]%2==1 o si e esta en V1 y s[e]==-1-> lo agarras }
void konig() {//O(n) return ans;
forn(v,nodes-2) s[v] = match[v] = -1; }
forn(v,nodes-2)
for(edge it: g[v])
if (it.to < nodes-2 && it.f>0){

4
match[v]=it.to; match[it.to]=v; 4.6 Hungarian Algorithm

FLOWS
}
forn(v,nodes-2) // Complexity O(Vˆ3) maximiza
if (match[v]==-1){ const int nax = 300;
s[v]=0;kq.push(v); const int inf = 1e9;
4.7
struct KM { } km;
int W[nax][nax], n;
int mx[nax], my[nax]; // match arr

Min-Cost Max-Flow Algorithm

int lx[nax], ly[nax]; // label arrMAXN
int x[nax], y[nax]; // used arr 4.7 Min-Cost Max-Flow Algorithm
int hungary(int nd) {
int i; ///Complexity O(Vˆ2 * Eˆ2)
x[nd] = 1; const ll inf = 1e18;
forn(i,n) struct edge {
if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) { int to, rev; ll f, cap, cost;
y[i] = 1; edge(int to, int rev, ll cap, ll cost, ll f=0) : to(to)
if(my[i] == -1 || hungary(my[i])) { , rev(rev), cap(cap), cost(cost), f(f) {}
my[i] = nd; };
return 1; struct MCMF{
} int n;
} vector<vector<edge>> g;
return 0; void addEdge(int s, int t, ll cap, ll cost){
} g[s].pb(edge(t, sz(g[t]), cap, cost));
int run() { g[t].pb(edge(s, sz(g[s])-1, 0, -cost));
int k, d; }
memset(mx, -1, sizeof(mx)); MCMF(int n):n(n){
memset(my, -1, sizeof(my)); g.resize(n);
forn(i,n) }
lx[i] = 0, ly[i] = 0; void spfa(int v0, vector<ll>& d, vector<int>& p) {
forn(i,n) d.assign(n, inf); d[v0] = 0;
forn(j,n) vector<bool> inq(n,false);
lx[i] = max( lx[i] ,W[i][j]); queue<int> q;
16

forn(i,n) { q.push(v0);
while(1) { p.assign(n,-1);
memset(x, 0, sizeof(x)); while (!q.empty()) {
memset(y, 0, sizeof(y)); int u = q.front();
if(hungary(i)) break; q.pop();
d = inf; inq[u] = false;
forn(j,n) { for(int i= 0; i< g[u].size(); ++i){
if(x[j]) { edge v = g[u][i];
forn(k,n) if (v.cap - v.f > 0 && d[v.to] > d[u] + v.cost )
if(!y[k]) {
d = min(d,lx[j]+ly[k]-W[j][k]); d[v.to] = d[u] + v.cost;
} p[v.to] = v.rev;
} if (!inq[v.to]) {
if(d == inf) break; inq[v.to] = true;
forn(j,n) { q.push(v.to);
if(x[j]) lx[j] -= d; }
if(y[j]) ly[j] += d; }
} }
} }
} }
int res = 0; ll min_cost_flow(ll K, int s, int t) {
forn(i,n) { ll flow = 0, cost = 0;
vector<int> p;

4
if(my[i] != -1)
res += W[my[i]][i]; vector<ll> d;

FLOWS
} while (flow < K) {
return res; spfa(s, d, p);
} if (d[t] == inf) break;
// find max flow on that path
4.8
ll f = K - flow; tie(d,u)=q.top(); q.pop()
int cur = t; ;
while (cur != s) { if(d!=prio[u]) continue;

Min-Cost Max-Flow Algorithm 2

int u = g[cur][p[cur]].to; forn(i,sz(g[u])) {
int rev = g[cur][p[cur]].rev; edge &e=g[u][i];
ll c = g[u][rev].cap - g[u][rev].f; int v=e.to;
f = min(f, c); if(e.cap<=e.f)
cur = u; continue;
} tc nprio=prio[u]+
// apply flow e.cost+pot[u]-
flow += f; pot[v];
cost += f * d[t]; if(prio[v]>nprio)
cur = t; {
while (cur != s) { prio[v]=
int rev = g[cur][p[cur]].rev; nprio;
int u = g[cur][p[cur]].to; q.push({
g[u][rev].f += f; nprio,
g[cur][p[cur]].f -= f; v});
cur = u; prevnode[
} v]=u;
} prevedge
if(flow< K) return -1; [v]=i;
return cost; curflow[v
} ]=min(
}; curflow
[u], e
.cap-e
4.8 Min-Cost Max-Flow Algorithm 2 .f);
17

}
}
typedef ll tf; }
typedef ll tc; if(prio[t]==INFCOST) break;
const tf INFFLOW=1e9; forn(i,n) pot[i]+=prio[i];
const tc INFCOST=1e9; tf df=min(curflow[t], INFFLOW-
struct MCF{ flow);
int n; flow+=df;
vector<tc> prio, pot; vector<tf> curflow; vector< for(int v=t; v!=s; v=prevnode[v])
int> prevedge,prevnode; {
priority_queue<pair<tc, int>, vector<pair<tc, int edge &e=g[prevnode[v]][
>>, greater<pair<tc, int>>> q; prevedge[v]];
struct edge{int to, rev; tf f, cap; tc cost;}; e.f+=df; g[v][e.rev].f-=
vector<vector<edge>> g; df;
MCF(int n):n(n),prio(n),curflow(n),prevedge(n), flowcost+=df*e.cost;
prevnode(n),pot(n),g(n){} }
void add_edge(int s, int t, tf cap, tc cost) { }
g[s].pb((edge){t,sz(g[t]),0,cap,cost}); return {flow,flowcost};
g[t].pb((edge){s,sz(g[s])-1,0,0,-cost}); }
} };
pair<tf,tc> get_flow(int s, int t) {
tf flow=0; tc flowcost=0;
while(1){

4
q.push({0, s}); 4.9 Blossom

FLOWS
fill(all(prio),INFCOST);
prio[s]=0; curflow[s]=INFFLOW; /// Complexity: O(|E||V|ˆ2)
tc d; int u; /// Tested: https://tinyurl.com/oe5rnpk
while(sz(q)){ /// Max matching undirected graph
struct network { }
struct struct_edge { int v; struct_edge * n; }; }
typedef struct_edge* edge; int bfs(int s) {
int n; fill(all(inq), 0);
struct_edge pool[MAXE]; ///2*n*n; fill(all(f), -1);
edge top; for(int i = 0; i < n; i++) base[i] = i;
vector<edge> adj; q = queue<int>();
queue<int> q; q.push(s);
vector<int> f, base, inq, inb, inp, match; inq[s] = 1;
vector<vector<int>> ed; while(sz(q)) {
network(int n) : n(n), match(n, -1), adj(n), top(pool), int u = q.front(); q.pop();
f(n), base(n), for(edge e = adj[u]; e; e = e->n) {
inq(n), inb(n), inp(n), ed(n, vector< int v = e->v;
int>(n)) {} if(base[u] != base[v] && match[u] != v) {
void add_edge(int u, int v) { if((v == s) || (match[v] != -1 && f[match[v]]
if(ed[u][v]) return; != -1))
ed[u][v] = 1; blossom_contraction(s, u, v);
top->v = v, top->n = adj[u], adj[u] = top++; else if(f[v] == -1) {
top->v = u, top->n = adj[v], adj[v] = top++; f[v] = u;
} if(match[v] == -1) return v;
int get_lca(int root, int u, int v) { else if(!inq[match[v]]) {
fill(inp.begin(), inp.end(), 0); inq[match[v]] = 1;
while(1) { q.push(match[v]);
inp[u = base[u]] = 1; }
if(u == root) break; }
u = f[ match[u] ]; }
} }
18

while(1) { }
if(inp[v = base[v]]) return v; return -1;
else v = f[ match[v] ]; }
} int doit(int u) {
} if(u == -1) return 0;
void mark(int lca, int u) { int v = f[u];
while(base[u] != lca) { doit(match[v]);
int v = match[u]; match[v] = u; match[u] = v;
inb[ base[u ]] = 1; return u != -1;
inb[ base[v] ] = 1; }
u = f[v]; /// (i < net.match[i]) => means match
if(base[u] != lca) f[u] = v; int maximum_matching() {
} int ans = 0;
} forn(u,n)
void blossom_contraction(int s, int u, int v) { ans += (match[u] == -1) && doit(bfs(u));
int lca = get_lca(s, u, v); return ans;

5
fill(all(inb), 0); }
};

DATA STRUCTURES
mark(lca, u); mark(lca, v);
if(base[u] != lca) f[u] = v;
if(base[v] != lca) f[v] = u;
forn(u,n){
if(inb[base[u]]) { 5 Data Structures
base[u] = lca;
if(!inq[u]) { 5.1 Disjoint Set Union
inq[u] = 1;
q.push(u);
} // Complejidad aprox O(1)
} struct dsu{
5.2
vi p, r; int num_sets;
void init(int n){ 5.3 Fenwick Tree
p.assign(n, 0), r.assign(n, 1), num_sets = n;

SQRT Decomposition
iota(all(p), 0);
} struct fwtree{ // 1-indexed
int find_set(int i){ vector<int> bit;
return (p[i] == i ? i : p[i] = find_set(p[i])); int n;
} fwtree(int n):n(n){
bool is_same_set(int i, int j){ bit.assign(n + 1, 0);
return find_set(i) == find_set(j); }
} int rsq(int r) {
void union_set(int i, int j){ int sum = 0; for (; r; r -= r&-r ) sum += bit[r];
int x = find_set(i), y = find_set(j); return sum;
if(x == y) return; }
if(r[x] > r[y]) swap(x, y); int rsq(int l, int r) {
p[x] = y; return rsq(r) - (l == 1 ? 0 : rsq(l - 1));
r[y] += r[x], r[x] = 0; }
--num_sets; void upd(int r, int v) {
} for (; r <= n; r += r&-r) bit[r] += v;
}; }
};

5.2 SQRT Decomposition 5.4 Fenwick Tree 2D

// Complexity struct fwtree{ /// 1-indexed
// Preprocessing O(n) query O(n/sqrt(n) + sqrt(n)) vector<vector<ll>> bit;
19

// Update O(1) int n, m;

struct sqrt_decomp{ fwtree(){}
vi a, b; fwtree(int n, int m):n(n),m(m){
int n, len; bit = vector<vector<ll>>(n+1, vector<ll>(m+1,0));
sqrt_decomp(vi &arr){ // preprocessing }
a = arr; n = sz(a); len = sqrt(n) + 1; ll sum(int x, int y) {
b = vi(len); ll v = 0;
forn(i,n) b[i/len] += a[i]; for (int i = x; i > 0; i -= i&(-i) )
} for (int j = y; j > 0; j -= j&(-j) )
void update(int pos, int val){ v += bit[i][j];
int bpos = pos/len; return v;
b[bpos] += val - a[pos]; }
a[pos] = val;
} void add(int x, int y, ll dt) {
int query(int l, int r){ for (int i = x; i <= n; i += i&(-i) )
int sum = 0; for (int j = y; j <= m; j += j&(-j) )

5
int c_l = l / len, c_r = r / len; bit[i][j] += dt;

DATA STRUCTURES
if (c_l == c_r){ }
fore(i,l,r) sum += a[i]; };
}else{
fore(i,l,(c_l+1)*len-1) sum += a[i];
fore(i,c_l+1,c_r-1) sum += b[i]; 5.5 Segment Tree
fore(i,c_r*len,r) sum += a[i];
}
return sum; #define neutro 0
} struct stree{
}; int n; vector<int> t;
stree(int m){
5.6
n = m; t.resize(n<<2); t[v]= a[tl]; return ;
} }
stree(vector<int> &a){ int tm = tl + (tr-tl)/ 2;

ST Lazy Propagation
n = sz(a); build(v*2, tl, tm, a);
t.resize(n<<2); build(v*2+1, tm+1, tr, a);
build(1,0, n-1, a); t[v] = oper(t[v*2], t[v*2+1]);
} }
inline int oper(int a, int b){ return a+b; } void push(int v) {
void build(int v, int tl, int tr, vector<int> &a){ t[v*2] += lazy[v]; lazy[v*2] += lazy[v];
if(tl==tr){ t[v*2+1] += lazy[v]; lazy[v*2+1] += lazy[v];
t[v]= a[tl]; return ; lazy[v] = 0;
} }
int tm = (tr+tl)/ 2; void upd(int v, int tl, int tr, int l, int r, int val)
build(v*2, tl, tm, a); {
build(v*2+1, tm+1, tr, a); if(tl>r || tr<l) return ;
t[v] = oper(t[v*2],t[v*2+1]); if (l <= tl && tr <= r) {
} t[v] += val;
int query(int v, int tl, int tr, int l, int r){ lazy[v] += val; return ;
if(tl>r || tr<l) return neutro; }
if(l<=tl && tr<=r) return t[v]; push(v);
int tm = (tl+tr)/2; int tm = tl + (tr-tl)/ 2;
return oper(query(v*2, tl, tm, l, r), upd(v*2, tl, tm, l, r, val);
query(v*2+1, tm+1, tr, l, r)); upd(v*2+1, tm+1, tr, l, r, val);
} t[v] = oper(t[v*2], t[v*2+1]);
void upd(int v, int tl, int tr, int pos, int val){ }
if(tl==tr){ int query(int v, int tl, int tr, int l, int r) {
t[v] = val; return ; if(tl>r || tr<l) return neutro;
20

} if (l <= tl && tr <= r) return t[v];

int tm = (tr+tl)/ 2; push(v);
if(pos<= tm) upd(v*2, tl, tm, pos, val); int tm = tl + (tr-tl)/ 2;
else upd(v*2+1, tm+1, tr, pos, val); return oper(query(v*2, tl, tm, l, r),
t[v] = oper(t[v*2], t[v*2+1]); query(v*2+1, tm+1, tr, l, r));
} }
void upd(int pos, int val){ upd(1,0,n-1,pos,val); } void upd(int l, int r, int val){ upd(1,0,n-1,l, r,val);
int query(int l, int r){ return query(1,0,n-1,l,r); } }
}; int query(int l, int r){ return query(1,0,n-1,l,r); }
};

5.6 ST Lazy Propagation

5.7 Persistent ST
#define neutro -1e9
struct stree{ #define neutro 0

5
int n; vector<int> t, lazy; struct node{

DATA STRUCTURES
stree(int m){ int sum, l, r;
n = m; t.resize(n<<2); };
lazy.resize(n<<2); struct stree{
} vector<int> rts;
stree(vector<int> &a){ vector<node> t;
n = sz(a); t.resize(n<<2); lazy.resize(n<<2); int n, idx;
build(1,0, n-1, a); inline int oper(int a, int b){ return a+b; }
} int build(int tl, int tr, vector<int> &a){
inline int oper(int a, int b){ return max(a,b); } int v = idx++;
void build(int v, int tl, int tr, vector<int> &a){ if(tl==tr){
if(tl==tr){ t[v].sum = a[tl]; return v;
5.8
} st[i+n][j]=op(st[i+n][j<<1],st[i+n][j
int tm = (tl+tr)/2; <<1|1]);
t[v].l = build(tl, tm, a);

Segtree 2D
for(int i=n-1;i;--i)forn(j,2*m)
t[v].r = build(tm+1, tr, a); st[i][j]=op(st[i<<1][j],st[i<<1|1][j]);
t[v].sum = t[t[v].l].sum + t[t[v].r].sum; }
return v; void upd(int x, int y, ll v){
} st[x+n][y+m]=v;
stree(vector<int> &a){ for(int j=y+m;j>1;j>>=1)st[x+n][j>>1]=op(st[x+n][
n = sz(a); j],st[x+n][jˆ1]);
t.resize(# define nax); for(int i=x+n;i>1;i>>=1)for(int j=y+m;j;j>>=1)
idx = 0; st[i>>1][j]=op(st[i][j],st[iˆ1][j]);
rts.pb(0); }
build(0, n-1, a); ll query(int x0, int x1, int y0, int y1){ // [x0, x1) , [
} y0,y1)
int query(int v, int tl, int tr, int l, int r){ ll r=neutro;
if(tl>r || tr<l) return neutro; for(int i0=x0+n,i1=x1+n;i0<i1;i0>>=1,i1>>=1){
if(l<=tl && tr<= r){ int t[4],q=0;
return t[v].sum; if(i0&1)t[q++]=i0++;
} if(i1&1)t[q++]=--i1;
int tm = (tl+tr)/2; forn(k,q)for(int j0=y0+m,j1=y1+m;j0<j1;j0
return oper(query(t[v].l, tl, tm, l, r), query(t[v].r >>=1,j1>>=1){
, tm+1, tr, l, r)); if(j0&1)r=op(r,st[t[k]][j0++]);
} if(j1&1)r=op(r,st[t[k]][--j1]);
int upd(int prev, int tl, int tr, int pos, int val){ }
int v = idx++; t[v] = t[prev]; }
if(tl==tr){ return r;
t[v].sum = val; return v; }
21

}
int tm = (tl+tr)/2;
if(pos<=tm) t[v].l = upd(t[v].l, tl, tm, pos, val); 5.9 RSQ
else t[v].r = upd(t[v].r, tm+1, tr, pos, val);
t[v].sum = t[t[v].l].sum + t[t[v].r].sum; //K has to satisfy K> log nax + 1
return v; ll st[nax][K], a[nax], sum = 0;
} void init(int N){
int query(int v, int l, int r){ forn(i,N) st[i][0] = a[i];
return query(v, 0, n-1, l, r); for1(j,K-1)
} forn(i,N-(1 << j)+1)
void upd(int pos, int val){ st[i][j] = st[i][j-1] + st[i + (1 << (j - 1))][j -
int id = upd(rts.back(), 0, n-1, pos, val); 1];
rts.pb(id); }
} void get(int l, int r){
}; sum = 0;

5
for (int j = K-1; j >= 0; j--) {
if ((1 << j) <= r - l + 1) {

DATA STRUCTURES
sum += st[l][j];
5.8 Segtree 2D l += 1 << j;
}
int n,m; }
const ll neutro = 0; }
ll op(ll a, ll b){ return a+b;}
ll a[nax][nax],st[2*nax][2*nax];
void build(){ 5.10 RMQ
forn(i,n)forn(j,m)st[i+n][j+m]=a[i][j];
forn(i,n)for(int j=m-1;j;--j) //K has to satisfy K> log nax + 1
5.11
int st[nax][K], a[nax]; add(who[i],1);
int logp[nax]; add(u,1);
void init(int N){ /// Answer queries

Sack
// logp[1] = 0; if(!keep)
// for (int i = 2; i < nax; i++) logp[i] = logp[i/2] + for(int i = fr[u]; i<= to[u]; ++i)
1; add(who[i],-1);
}
forn(i,N) st[i][0] = a[i]; void solve(int root){
for1(j,K-1) timer = 0;
forn(i,N-(1 << j)+1) pre(root, root);
st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j dfs(root, root);
- 1]); }
}
int get(int l, int r){ //assuming L<=R
if(l>r) return inf; 5.12 Heavy Light Decomposition
// int j = logp[r - l + 1];
int j = 31 - __builtin_clz(r-l+1);
return min(st[l][j], st[r - (1 << j) + 1][j]); vector<int> g[nax];
} int len[nax], dep[nax], in[nax], out[nax], head[nax], par
[nax], idx;
void dfs_sz( int u, int d ) {
dep[u] = d;
5.11 Sack int &sz = len[u]; sz = 1;
for( auto &v : g[u] ) {
// Time Complexity O(N*log(N)) if( v == par[u] ) continue;
int timer; par[v] = u; dfs_sz(v, d+1);
int cnt[nax], big[nax], fr[nax], to[nax], who[nax]; sz += len[v];
22

vector<int> g[nax]; if(len[ g[u][0] ] < len[v]) swap(g[u][0], v);

int pre(int u, int p){ }
int sz = 1, tmp; return ;
who[timer] = u; }
fr[u] = timer++; void dfs_hld( int u) {
ii best = {-1, -1}; in[u] = idx++;
for(int v: g[u]){ arr[in[u]] = val[u]; /// to initialize the segment tree
if(v==p) continue; for( auto& v : g[u] ) {
tmp = pre(v,u); if( v == par[u] ) continue;
sz+=tmp; head[v] = (v == g[u][0] ? head[u] : v);
best = max(best, {tmp, v}); dfs_hld(v);
} }
big[u] = best.se; out[u] = idx-1;
to[u] = timer-1; }
return sz; void upd_hld( int u, int val ) {
} upd_DS(in[u], val);

5
void add(int u, int x) { /// x == 1 add, x == -1 delete }

DATA STRUCTURES
cnt[u] += x; int query_hld( int u, int v ) {
} int val = neutro;
void dfs(int u, int p, bool keep = true){ while( head[u] != head[v] ) {
for(int v: g[u]) if( dep[ head[u] ] < dep[ head[v] ] ) swap(u, v);
if(v!=p && v!=big[u]) val = val + query_DS(in[ head[u] ], in[u]);
dfs(v,u, 0); u = par[ head[u] ];
if(big[u]!=-1) dfs(big[u], u); }
/// add all small if( dep[u] > dep[v] ) swap(u, v);
for(int v: g[u]) val = val+query_DS(in[u], in[v]);
if(v!=p && v!=big[u]) return val;
for(int i = fr[v]; i<= to[v]; ++i) /// when updates are on edges use: (line 36)
5.13
/// if (dep[u] == dep[v]) return val; }
/// val = val+query_DS(in[u] + 1, in[v]); pitem kth(pitem t, int k){
} if(!t)return 0;

Treap
void build(int root) { if(k==cnt(t->l))return t;
idx = 0; /// DS index [0, n) return k<cnt(t->l)?kth(t->l,k):kth(t->r,k-cnt(t->
par[root] = head[root] = root; l)-1);
dfs_sz(root, 0); }
dfs_hld(root); pair<int,int> lb(pitem t, int key){ // position and value
/// initialize DS of lower_bound
} if(!t)return {0,1<<30}; // (special value)
if(key>t->key){
auto w=lb(t->r,key);w.fst+=cnt(t->l)+1;
5.13 Treap return w;
}
auto w=lb(t->l,key);
typedef struct item *pitem; if(w.fst==cnt(t->l))w.snd=t->key;
struct item { return w;
int pr,key,cnt; }
pitem l,r;
item(int key):key(key),pr(rand()),cnt(1),l(0),r
(0) {} 5.14 Implicit Treap
};
int cnt(pitem t){return t?t->cnt:0;}
void upd_cnt(pitem t){if(t)t->cnt=cnt(t->l)+cnt(t->r)+1;} // example that supports range reverse and addition
void split(pitem t, int key, pitem& l, pitem& r){ // l: < updates, and range sum query
key, r: >= key // (commented parts are specific to this problem)
if(!t)l=r=0; typedef struct item* pitem;
struct item {
23

else if(key<t->key)split(t->l,key,l,t->l),r=t;
else split(t->r,key,t->r,r),l=t; int pr,cnt,val;
upd_cnt(t); // int sum; // (paramters for range query)
} // bool rev;int add; // (parameters for lazy prop)
void insert(pitem& t, pitem it){ pitem l,r;
if(!t)t=it; item(int val): pr(rand()),cnt(1),val(val),l(0),r
else if(it->pr>t->pr)split(t,it->key,it->l,it->r) (0)/*,sum(val),rev(0),add(0)*/ {}
,t=it; };
else insert(it->key<t->key?t->l:t->r,it); void push(pitem it){
upd_cnt(t); if(it){
} /*if(it->rev){
void merge(pitem& t, pitem l, pitem r){ swap(it->l,it->r);
if(!l||!r)t=l?l:r; if(it->l)it->l->revˆ=true;
else if(l->pr>r->pr)merge(l->r,l->r,r),t=l; if(it->r)it->r->revˆ=true;
else merge(r->l,l,r->l),t=r; it->rev=false;
upd_cnt(t); }

5
} it->val+=it->add;it->sum+=it->cnt*it->add
;
void erase(pitem& t, int key){

DATA STRUCTURES
if(it->l)it->l->add+=it->add;
if(t->key==key)merge(t,t->l,t->r); if(it->r)it->r->add+=it->add;
else erase(key<t->key?t->l:t->r,key); it->add=0;*/
upd_cnt(t); }
} }
void unite(pitem &t, pitem l, pitem r){ int cnt(pitem t){return t?t->cnt:0;}
if(!l||!r){t=l?l:r;return;} // int sum(pitem t){return t?push(t),t->sum:0;}
if(l->pr<r->pr)swap(l,r); void upd_cnt(pitem t){
pitem p1,p2;split(r,l->key,p1,p2); if(t){
unite(l->l,l->l,p1);unite(l->r,l->r,p2); t->cnt=cnt(t->l)+cnt(t->r)+1;
t=l;upd_cnt(t); // t->sum=t->val+sum(t->l)+sum(t->r);
5.15
} void push_all(pitem t){
} if(t->f)push_all(t->f);
void merge(pitem& t, pitem l, pitem r){ push(t);

Implicit Treap Father

push(l);push(r); }
if(!l||!r)t=l?l:r; pitem root(pitem t, int& pos){ // get root and position
else if(l->pr>r->pr)merge(l->r,l->r,r),t=l; for node t
else merge(r->l,l,r->l),t=r; push_all(t);
upd_cnt(t); pos=cnt(t->l);
} while(t->f){
void split(pitem t, pitem& l, pitem& r, int sz){ // sz: pitem f=t->f;
desired size of l if(t==f->r)pos+=cnt(f->l)+1;
if(!t){l=r=0;return;} t=f;
push(t); }
if(sz<=cnt(t->l))split(t->l,l,t->l,sz),r=t; return t;
else split(t->r,t->r,r,sz-1-cnt(t->l)),l=t; }
upd_cnt(t);
}
void output(pitem t){ // useful for debugging 5.16 Ordered Set
if(!t)return;
push(t); #include <ext/pb_ds/assoc_container.hpp>
output(t->l);printf(" %d",t->val);output(t->r); #include <ext/pb_ds/tree_policy.hpp>
} using namespace __gnu_pbds;
// use merge and split for range updates and queries typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
//methods
5.15 Implicit Treap Father tree.find_by_order(k) //returns pointer to the k-th
smallest element
24

tree.order_of_key(x) //returns how many elements are

// node father is useful to keep track of the chain of smaller than x
each node //if element does not exist
// alternative: splay tree tree.end() == tree.find_by_order(k) //true
// IMPORTANT: add pointer f in struct item
void merge(pitem& t, pitem l, pitem r){
push(l);push(r);
if(!l||!r)t=l?l:r;
5.17 Mo’s Algorithm
else if(l->pr>r->pr)merge(l->r,l->r,r),l->r->f=t=
l; /// Complexity: O(|N+Q|*sqrt(|N|)*|ADD/DEL|)
else merge(r->l,l,r->l),r->l->f=t=r; /// Requires add(), delete() and get_ans()
upd_cnt(t); struct query {
} int l, r, idx;
void split(pitem t, pitem& l, pitem& r, int sz){ };
if(!t){l=r=0;return;} int S; // s = sqrt(n)
push(t); bool cmp (query a, query b) {

5
if(sz<=cnt(t->l)){ int x = a.l/S;

DATA STRUCTURES
split(t->l,l,t->l,sz);r=t; if (x != b.l/S) return x < b.l/S;
if(l)l->f=0; return (x&1 ? a.r < b.r : a.r > b.r);
if(t->l)t->l->f=t; }
} void solve(){
else { S = sqrt(n); // n = size of array
split(t->r,t->r,r,sz-1-cnt(t->l));l=t; sort(all(q), cmp);
if(r)r->f=0; int l = 0, r = -1;
if(t->r)t->r->f=t; forn(i, sz(q)){
} while (r < q[i].r) add(++r);
upd_cnt(t); while (l > q[i].l) add(--l);
} while (r > q[i].r) del(r--);
while (l < q[i].l) del(l++); int j = max(start_idx, p) * p - start;
ans[q[i].idx] = get_ans(); for (; j < S; j += p)
} block[j] = false;
} }
if (k == 0)
block[0] = block[1] = false;
for (int i = 0; i < S && start + i <= n; i++) {
6 Math if (block[i])
result++;
}
6.1 Sieve of Eratosthenes }
return result;
// O(n) }
// pr contains prime numbers
// lp[i] == i if i is prime
// else lp[i] is minimum prime factor of i
const int nax = 1e7; 6.3 Segmented Sieve
int lp[nax+1];
vector<int> pr; // It can be sped up if change for an // Complexity O((R-L+1)*log(log(R)) + sqrt(R)*log(log(R))
array )
void sieve(){ // R-L+1 roughly 1e7 R-- 1e12
fore(i,2,nax-1){ vector<bool> segmentedSieve(ll L, ll R) {
if (lp[i] == 0) { // generate all primes up to sqrt(R)
lp[i] = i; pr.pb(i); ll lim = sqrt(R);
} vector<bool> mark(lim + 1, false);
for (int j=0, mult= i*pr[j]; j<sz(pr) && pr[j]<=lp[i] vector<ll> primes;
&& mult<nax; ++j, mult= i*pr[j]) for (ll i = 2; i <= lim; ++i) {
25

lp[mult] = pr[j]; if (!mark[i]) {

} primes.emplace_back(i);
} for (ll j = i * i; j <= lim; j += i)
mark[j] = true;
}
}
6.2 Count primes vector<bool> isPrime(R - L + 1, true);
for (ll i : primes)
int count_primes(int n) { for (ll j = max(i * i, (L + i - 1) / i * i); j <= R;
const int S = 10000; j += i)
vector<int> primes; isPrime[j - L] = false;
int nsqrt = sqrt(n); if (L == 1)
vector<char> is_prime(nsqrt + 1, true); isPrime[0] = false;
fore(i,2,nsqrt){ return isPrime;
if (is_prime[i]) { }
primes.pb(i);
for (int j = i * i; j <= nsqrt; j += i)
is_prime[j] = false; 6.4 Polynomial Multiplication
}
}
int result = 0; int ans[grado1+grado2+1];
vector<char> block(S); forn(c,grado1+grado2+1) ans[c] = 0;

6
for (int k = 0; k * S <= n; k++) { forn(pos,grado1+1){
fill(all(block), true); forn(ter,grado2+1)

MATH
int start = k * S; ans[pos + ter] += pol1[pos] * pol2[ter];
for (int p : primes) { }
int start_idx = (start + p - 1) / p;
6.5
forn(i,sz(res)) res[i] = floor(imag(out[i]) / (4
6.5 Fast Fourier Transform * n) +0.5);
return res;

Fast Fourier Transform

}
typedef double ld;
const ld PI = acos(-1.0L); vl convMod(const vl &a, const vl &b, const int &M) {
const ld one = 1; if (a.empty() || b.empty()) return {};
typedef complex<ld> C; vl res(sz(a) + sz(b) - 1);
typedef vector<ld> vd; int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(
sqrt(M));
void fft(vector<C>& a) { vector<C> L(n), R(n), outs(n), outl(n);
int n = sz(a), L = 31 - __builtin_clz(n); forn(i,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i]
static vector<complex<ld>> R(2, 1); % cut);
static vector<C> rt(2, 1); // (ˆ 10% faster if forn(i,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i]
double) % cut);
for (static int k = 2; k < n; k *= 2) { fft(L), fft(R);
R.resize(n); rt.resize(n); forn(i,n) {
auto x = polar(one, PI / k); int j = -i & (n - 1);
fore(i,k,2*k-1) rt[i] = R[i] = i&1 ? R[i outl[j] = (L[i] + conj(L[j])) * R[i] /
/2] * x : R[i/2]; (2.0 * n);
} outs[j] = (L[i] - conj(L[j])) * R[i] /
vi rev(n); (2.0 * n) / 1i;
forn(i,n) rev[i] = (rev[i / 2] | (i & 1) << L) / }
2; fft(outl), fft(outs);
forn(i,n) if (i < rev[i]) swap(a[i], a[rev[i]]); forn(i,sz(res)) {
for (int k = 1; k < n; k *= 2) ll av = ll(real(outl[i])+.5), cv = ll(
for (int i = 0; i < n; i += 2 * k) forn(j imag(outs[i])+.5);
ll bv = ll(imag(outl[i])+.5) + ll(real(
26

,k) {
// C z = rt[j+k] * a[i+j+k]; // outs[i])+.5);
(25% faster if hand-rolled) res[i] = ((av % M * cut + bv) % M * cut +
/// include-line cv) % M;
auto x = (ld *)&rt[j+k], y = (ld }
return res;
*)&a[i+j+k]; /// }
exclude-line
C z(x[0]*y[0] - x[1]*y[1], x[0]*y
[1] + x[1]*y[0]); //
/ exclude-line 6.6 FHT
a[i + j + k] = a[i + j] - z;
a[i + j] += z;
} ll c1[MAXN+9],c2[MAXN+9]; // MAXN must be power of 2 !!
} void fht(ll* p, int n, bool inv){
for(int l=1;2*l<=n;l*=2)for(int i=0;i<n;i+=2*l)
typedef vector<ll> vl; forn(j,l){
vl conv(const vl& a, const vl& b) { ll u=p[i+j],v=p[i+l+j];
if (a.empty() || b.empty()) return {}; if(!inv)p[i+j]=u+v,p[i+l+j]=u-v; // XOR
vl res(sz(a) + sz(b) - 1); else p[i+j]=(u+v)/2,p[i+l+j]=(u-v)/2;
int L = 32 - __builtin_clz(sz(res)), n = 1 << L; //if(!inv)p[i+j]=v,p[i+l+j]=u+v; // AND
vector<C> in(n), out(n); //else p[i+j]=-u+v,p[i+l+j]=u;
copy(all(a), begin(in)); //if(!inv)p[i+j]=u+v,p[i+l+j]=u; // OR
forn(i,sz(b)) in[i].imag(b[i]); //else p[i+j]=v,p[i+l+j]=u-v;

6
fft(in); }
for (C& x : in) x *= x; }

MATH
forn(i,n) out[i] = in[-i & (n - 1)] - conj(in[i]) // like polynomial multiplication, but XORing exponents
; // instead of adding them (also ANDing, ORing)
fft(out); vector<ll> multiply(vector<ll>& p1, vector<ll>& p2){
6.7
int n=1<<(32-__builtin_clz(max(sz(p1),sz(p2))-1))
;
forn(i,n)c1[i]=0,c2[i]=0; 6.9 Binary Exponentiation

Fibonacci Matrix
forn(i,sz(p1))c1[i]=p1[i];
forn(i,sz(p2))c2[i]=p2[i]; int binpow(int b, int e) {
fht(c1,n,false);fht(c2,n,false); int ans = 1;
forn(i,n)c1[i]*=c2[i]; for (; e; b = 1LL*b*b%mod, e /= 2)
fht(c1,n,true); if (e&1) ans = 1LL*ans*b%mod;
return vector<ll>(c1,c1+n); return ans;
} }

6.7 Fibonacci Matrix 6.10 Euler’s Totient Function

// Pair Fn and Fn+1 int phi(int n) { // O(sqrt(n))
ii fib (int n) { if(n==1) return 0;
if (n == 0) return {0, 1}; int ans = n;
ii p = fib(n >> 1); for (int i = 2; 1ll*i*i <= n; i++) {
int c = p.fi * (2 * p.se - p.fi); if(n % i == 0) {
int d = p.fi * p.fi + p.se * p.se; while(n % i == 0) n /= i;
if (n & 1) return ii(d, c + d); ans -= ans / i;
else return ii(c, d); }
} }
if(n > 1) ans -= ans / n;
return ans;
}
6.8 Matrix Exponentiation //////////////////
27

vi phi_(int n) { // O(n loglogn)

struct matrix{ // define N vi phi(n + 1);
int r, c, m[N][N]; phi[0] = 0;
matrix(int r, int c):r(r),c(c){ for1(i,n) phi[i] = i;
memset(m, 0, sizeof m); fore(i,2,n){
} if(phi[i] != i) continue;
matrix operator *(const matrix &b){ for (int j = i; j <= n; j += i)
matrix c = matrix(this->r, b.c); phi[j] -= phi[j] / i;
forn(i,this->r){ }
forn(k,b.r){ }
if(!m[i][k]) continue;
forn(j,b.c){ ////////// with linear sieve when i is not a prime number
c.m[i][j] += m[i][k]*b.m[k][j]; if (lp[i] == lp[i / lp[i]])
} phi[i] = phi[i / lp[i]] * lp[i];
} else
} phi[i] = phi[i / lp[i]] * (lp[i] - 1);
return c;
}
}; 6.11 Extended Euclidean (Diophantic)
matrix pow(matrix &b, ll e){
matrix c = matrix(b.r, b.c);
forn(i,b.r) c.m[i][i] = 1; // a*x+b*y = g
while(e){ ll gcde(ll a, ll b, ll& x, ll& y) {

6
if(e&1LL) c = c*b; x = 1, y = 0;
b = b*b , e/=2; ll x1 = 0, y1 = 1, a1 = a, b1 = b;

MATH
} ll q;
return c; while (b1) {
} q = a1 / b1;
6.12
tie(x, x1) = make_tuple(x1, x - q * x1); }
tie(y, y1) = make_tuple(y1, y - q * y1); // If k is composite k = k1ˆp1 * k2ˆp2 * ... * kmˆpm
tie(a1, b1) = make_tuple(b1, a1 - q * b1); // min 1..m ai/ pi where ai is fact_pow(n, ki)

Inversa modular
}
return a1;
}
6.14 Mobious
bool find_any_solution(ll a, ll b, ll c, ll &x0, ll &y0,
ll &g) { int mu[nax], f[nax], h[nax];
g = gcde(abs(a), abs(b), x0, y0); void pre(){
if (c % g) return false; mu[0] = 0; mu[1] = 1;
x0 *= c / g; for(int i = 1; i<nax; ++i){
y0 *= c / g; if(mu[i]==0) continue;
if (a < 0) x0 = -x0; for(int j= i+i; j<nax; j+=i){
if (b < 0) y0 = -y0; mu[j] -= mu[i];
return true; }
} }
for(int i = 1; i < nax; ++i){
for(int j = i; j < nax; j += i){
6.12 Inversa modular f[j] += h[i]*mu[j/i];
}
// O(mod) }
const int mod; }
int inv[mod]; ////////
void precalc(){ void pre(){
inv[1] = 1; mu[0] = 0; mu[1] = 1;
fore(i,2,N){
28

fore(i,2,mod-1) inv[i] = (mod - (mod/i) * inv[mod%i] %

mod) % mod; if (lp[i] == 0) {
} lp[i] = i; mu[i] = -1;
pr.pb(i);
///////////////////////////////////// }
ll inverse(ll a, ll m){ for (int j=0, mult= i*pr[j]; j<sz(pr) && pr[j]<=lp[i]
ll x, y; && mult<=N; ++j, mult= i*pr[j]){
ll g = gcde(a, m, x, y); if(i%pr[j]==0) mu[mult] = 0;
if (g != 1) { else mu[mult] = mu[i]*mu[pr[j]];
cout << "No solution!"; lp[mult] = pr[j];
return -1; }
}else{ }
x = (x % m + m) % m; }
return x;
}
}
6.15 Miller Rabin Test

6.13 Legendre’s Formula ll mulmod(ll a, ll b, ll m) {

ll r=a*b-(ll)((long double)a*b/m+.5)*m;
return r<0?r+m:r;
// Complexity O(log_k (n)) }
// If k is prime ll binpow(ll b, ll e, ll m){
int fact_pow (int n, int k) { ll r = 1;

6
int x = 0; while(e){
while(n) { if(e&1) r = mulmod(r, b,m);

MATH
n /= k; x += n; b = mulmod(b,b,m);
} e = e/2;
return x; }
6.16
return r; else d=__gcd(y-x,n);
} }
return d==n?rho(n):d;

Pollard Rho
bool is_prime(ll n, int a, ll s, ll d){ }
if(n==a) return true; void fact(ll n, map<ll,int>& f){ //O (lg n)ˆ3
ll x=binpow(a,d,n); if(n==1)return;
if(x==1 || x+1==n)return true; if(rabin(n)){f[n]++;return;}
forn(k,s-1){ ll q=rho(n);fact(q,f);fact(n/q,f);
x=mulmod(x,x,n); }
if(x==1) return false;
if(x+1==n) return true;
}
return false; 6.17 Chinese Remainder Theorem
}
int ar[]={2,3,5,7,11,13,17,19,23,29,31,37}; pll extendedEuclid(ll a, ll b){ // a * x + b * y = __gcd(
bool rabin(ll n){ // true iff n is prime a,b)
if(n==2) return true; ll x,y;
if(n<2 || n%2==0) return false; if (b==0) return {1,0};
ll s=0,d=n-1; auto p=extendedEuclid(b,a%b);
while(d%2==0)++s,d/=2; x=p.se;
forn(i,12) if(!is_prime(n,ar[i],s,d)) return y=p.fi-(a/b)*x;
false; if(a*x+b*y==-__gcd(a,b)) x=-x, y=-y;
return true; return {x,y};
} }
pair<pll,pll> diophantine(ll a, ll b, ll r) {
/////////////////////////////////////// //a*x+b*y=r where r is multiple of __gcd(a,b);
ll d=__gcd(a,b);
bool isPrime(ll n) { a/=d; b/=d; r/=d;
29

if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3; auto p = extendedEuclid(a,b);

ll A[] = {2, 325, 9375, 28178, 450775, 9780504, p.fi*=r; p.se*=r;
1795265022}; // assert(a*p.fi+b*p.se==r);
ll s=0,d=n-1; return {p,{-b,a}}; // solutions: p+t*ans.se
while(d%2==0)++s,d/=2; }
for (ll a : A) { // ˆ count trailing zeroes ll inv(ll a, ll m) {
ll p = binpow(a%n, d, n), i = s; assert(__gcd(a,m)==1);
while (p != 1 && p != n - 1 && a % n && i ll x = diophantine(a,m,1).fi.fi;
--) return ((x%m)+m)%m;
p = mulmod(p, p, n); }
if (p != n-1 && i != s) return 0; #define MOD(a,m) (((a)%m+m)%m)
} pll sol(tuple<ll,ll,ll> c){ //requires inv, diophantine
return 1; ll a=get<0>(c), x1=get<1>(c), m=get<2>(c), d=__gcd(a,m)
} ;
if(d==1) return pll(MOD(x1*inv(a,m),m), m);
else return x1%d ? pll({-1LL,-1LL}) : sol(make_tuple(a/
d,x1/d,m/d));
6.16 Pollard Rho }
pair<ll,ll> crt(vector< tuple<ll,ll,ll> > &cond) { //
ll rho(ll n){ returns: (sol, lcm)
if(!(n&1))return 2; ll x1=0,m1=1,x2,m2;
ll x=2,y=2,d=1; for(auto &t: cond){
ll c=rand()%n+1; tie(x2,m2)=sol(t);

6
while(d==1){ if((x1-x2)%__gcd(m1,m2))return {-1,-1};
x=(mulmod(x,x,n)+c)%n; if(m1==m2)continue;

MATH
y=(mulmod(y,y,n)+c)%n; ll k=diophantine(m2,-m1,x1-x2).fi.se,l=m1
y=(mulmod(y,y,n)+c)%n; *(m2/__gcd(m1,m2));
if(x>=y)d=__gcd(x-y,n); x1=MOD((__int128_t)m1*k+x1,l); m1=l;
6.18
} mn=b[i]/A[i][y],x=i;
return sol(make_tuple(1,x1,m1)); assert(x>=0); // cˆT x is unbounded
} //cond[i]={ai,bi,mi} ai*xi=bi (mi); assumes lcm fits in pivot(x,y);

Simplex
ll }
vector<double> r(m);
forn(i,n)if(Y[i]<m)r[Y[i]]=b[i];
return {z,r};
6.18 Simplex }

vector<int> X,Y;
vector<vector<double> > A; 6.19 Gauss Jordan
vector<double> b,c;
double z; int gauss(vector<vector<double>> &a, vector<double> &ans)
int n,m; {
void pivot(int x,int y){ int n = sz(a), m = sz(a[0]) - 1;
swap(X[y],Y[x]); vi where(m, -1);
b[x]/=A[x][y]; for(int col=0, row=0; col<m && row<n; ++col) {
forn(i,m)if(i!=y)A[x][i]/=A[x][y]; int sel = row;
A[x][y]=1/A[x][y]; fore(i,row,n-1)
forn(i,n)if(i!=x&&abs(A[i][y])>eps){ if(abs(a[i][col]) > abs(a[sel][col])) sel = i;
b[i]-=A[i][y]*b[x]; if(abs(a[sel][col]) < eps) continue;
forn(j,m)if(j!=y)A[i][j]-=A[i][y]*A[x][j
]; fore(i,col,m) swap (a[sel][i], a[row][i]);
A[i][y]=-A[i][y]*A[x][y]; where[col] = row;
} forn(i,n){
z+=c[y]*b[x]; if (i != row) {
forn(i,m)if(i!=y)c[i]-=c[y]*A[x][i]; double c = a[i][col] / a[row][col];
30

c[y]=-c[y]*A[x][y]; for (int j=col; j<=m; ++j) a[i][j] -= a[row][j] *

} c;
pair<double,vector<double> > simplex( // maximize cˆT x s }
.t. Ax<=b, x>=0 }
vector<vector<double> > _A, vector<double ++row;
> _b, vector<double> _c){ }
// returns pair (maximum value, solution vector)
A=_A;b=_b;c=_c; ans.assign(m, 0);
n=sz(b);m=sz(c);z=0.; forn(i,m){
X=vector<int>(m);Y=vector<int>(n); if(where[i] != -1) ans[i] = a[where[i]][m] / a[where[
forn(i,m)X[i]=i; i]][i];
forn(i,n)Y[i]=i+m; }
while(1){ forn(i,n){
int x=-1,y=-1; double sum = 0;
double mn=-eps; forn(j,m) sum += ans[j] * a[i][j];
forn(i,n)if(b[i]<mn)mn=b[i],x=i; if(abs(sum - a[i][m]) > eps) return 0;
if(x<0)break; }
forn(i,m)if(A[x][i]<-eps){y=i;break;} forn(i,m) if(where[i] == -1) return 1e9; /// infinitas
assert(y>=0); // no solution to Ax<=b soluciones
pivot(x,y); return 1;
} }
while(1){
double mx=eps;

6
int x=-1,y=-1; 6.20 Gauss Jordan Modular
forn(i,m)if(c[i]>mx)mx=c[i],y=i;

MATH
if(y<0)break; const int eps = 0, mod = 1e9+7;
double mn=1e200;
forn(i,n)if(A[i][y]>eps&&b[i]/A[i][y]<mn) int gauss(vector<vi> &a, vi &ans) {
6.21
int n = sz(a), m = sz(a[0]) - 1; forn(j,sz(ls)) c.pb(-ls[j]*k%mod)
vi where(m, -1); ;
for(int col=0, row=0; col<m && row<n; ++col) { if(sz(c)<sz(cur)) c.resize(sz(cur

Berlekamp Massey
int sel = row; ));
fore(i,row,n-1) forn(j,sz(cur)) c[j]=(c[j]+cur[j
if(abs(a[i][col]) > abs(a[sel][col])) sel = i; ])%mod;
if(abs(a[sel][col]) <= eps) continue; if(i-lf+sz(ls)>=sz(cur)) ls=cur,
lf=i,ld=(t-x[i])%mod;
fore(i,col,m) swap (a[sel][i], a[row][i]); cur=c;
where[col] = row; }
forn(i,sz(cur)) cur[i]=(cur[i]%mod+mod)%
forn(i,n){ mod;
if (i != row) { return cur;
int c = 1LL*a[i][col] * inv(a[row][col])%mod; }
for (int j=col; j<=m; ++j) a[i][j] = (mod + a[i][ int m; //length of recurrence
j] - (1LL*a[row][j] * c)%mod)%mod; //a: first terms
} //h: relation
}
++row; vector<ll> a, h, t_, s, t;
} //calculate p*q mod f
inline vector<ll> mull(vector<ll> p, vector<ll> q
ans.assign(m, 0); ){
forn(i,m){ forn(i,2*m) t_[i]=0;
if(where[i] != -1) ans[i] = 1LL*a[where[i]][m] * inv( forn(i,m) if(p[i])
a[where[i]][i])%mod; forn(j,m)
} t_[i+j]=(t_[i+j]+p[i]*q[j
forn(i,n){ ])%mod;
ll sum = 0; for(int i=2*m-1;i>=m;--i) if(t_[i])
31

forn(j,m) sum = (sum + 1LL*ans[j] * a[i][j])%mod; forn(j,m)

if(abs(sum - a[i][m]) > eps) return 0; t_[i-j-1]=(t_[i-j-1]+t_[i
} ]*h[j])%mod;
forn(i,m) if(where[i] == -1) return 1e9; /// infinitas forn(i,m) p[i]=t_[i];
return p;
soluciones }
return 1; inline ll calc(ll k){
} if(k < sz(a)) return a[k];
forn(i,m) s[i]=t[i]=0;
s[0]=1;
6.21 Berlekamp Massey if(m!=1) t[1]=1;
else t[0]=h[0];
// taken from https://codeforces.com/blog/entry/61306 while(k){
struct ber_ma{
vi BM(vi &x){ if(k&1LL) s = mull(s,t);
vi ls,cur; int lf,ld; t = mull(t,t); k/=2;
forn(i,sz(x)){ }
ll t=0; ll su=0;
forn(j,sz(cur)) t=(t+x[i-j-1]*(ll forn(i,m) su=(su+s[i]*a[i])%mod;
return (su%mod+mod)%mod;
)cur[j])%mod; }
if((t-x[i])%mod==0) continue; ber_ma(vi &x){
if(!sz(cur)){ vi v = BM(x); m=sz(v);
cur.resize(i+1); h.resize(m), a.resize(m), s.resize(m);

6
lf=i; ld=(t-x[i])%mod; t.resize(m), t_.resize(2*m);
continue;

MATH
forn(i,m) h[i]=v[i],a[i]=x[i];
} }
ll k=-(x[i]-t)*inv(ld,mod); };
vi c(i-lf-1); c.pb(k);
int j = upper_bound(d.begin(), d.end(), a[i]) - d.
begin();
7 Dynamic Programming if (d[j-1] < a[i] && a[i] < d[j]) d[j] = a[i];
}
7.1 Edit Distance int ans = 0;
for (int i = 0; i <= n; i++) {
// O(m*n) donde cada uno es el tamano de cada string if (d[i] < inf) ans = i;
int editDist(string &s1, string &s2){ }
int m = sz(s1), n = sz(s2); return ans;
int dp[m+1][n+1]; }
forn(i,m+1)
forn(j,n+1){
if (i==0) dp[i][j] = j; 7.4 Trick to merge intervals
else if (j==0) dp[i][j] = i;
else if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j
-1]; // Option 1
else dp[i][j] = 1 + min({dp[i][j-1], // Insert for(int len= 0; len<n; ++len){
dp[i-1][j], // Remove for(int l= 0; l<n-len; ++l){
dp[i-1][j-1]}); // Replace int r= l+len;
} dp[l][r]= max(dp[l+1][r], dp[l][r-1]);
return dp[m][n]; }
} }
// Option 2
for(int l= n-1; l>=0; --l){
for(int r= l; r<n ; ++r){
7.2 Longest common subsequence dp[l][r]= max(dp[l+1][r], dp[l][r-1]);
}
32

const int nax = 1005; }

int dp[nax][nax];
int lcs(const string &s, const string &t){
int n = sz(s), m = sz(t); 7.5 Trick Sets DP
forn(j,m+1) dp[0][j] = 0;
forn(i,n+1) dp[i][0] = 0; // Complexity O(N*2ˆN)
for1(i,n){ const int N;
for1(j,m){ int dp[1<<N][N+1];
dp[i][j] = max(dp[i-1][j], dp[i][j-1]); int F[1<<N];
if (s[i-1] == t[j-1]){ int A[1<<N];
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1); // ith bit is ON S(mask, i) = S(mask, i-1)

7
} // ith bit is OFF S(mask,i) = S(mask, i-1) + S(maskˆ(1<<i
} ), i-1)

DYNAMIC PROGRAMMING
}
return dp[n][m]; //iterative version
} forn(mask,(1<<N)){
dp[mask][0] = A[mask]; //handle base case
separately (leaf states)
forn(i,N){
7.3 Longest increasing subsequence if(mask & (1<<i))
dp[mask][i+1] = dp[mask][i] + dp[
// Complejidad n log n maskˆ(1<<i)][i];
int lis(const vi &a) { else
int n = a.size(); dp[mask][i+1] = dp[mask][i];
vi d(n+1, inf); }
d[0] = -inf; F[mask] = dp[mask][N];
}
for (int i = 0; i < n; i++) { //memory optimized, super easy to code.
7.6
forn(i,(1<<N)) F[i] = A[i]; k[l][r]= i;
forn(i,N) }
forn(mask,(1<<N)){ }

Divide and Conquer

if(mask & (1<<i)) F[mask] += F[maskˆ(1<<i)]; ans+= C[l][r];
} }
}
cout<< dp[0][n-1]<<el;
}
7.6 Divide and Conquer
const ll inf = 1e18; 7.8 Convex Hull Trick
const int nax = 1e3+20, kax = 20;
ll C[nax][nax], dp[kax][nax]; struct line {
int n; ll m, b;
ll eval(ll x) { return m * x + b; }
void compute(int k, int l, int r, int optl, int optr){ ld inter(line &l) { return (ld) (b - l.b) / (l.m - m);
if(l>r) return ; }
int mid= (l+r)/2, opt; };
pll best= {inf,-1};
for(int i= max(mid,optl); i<= optr ; ++i ){ struct cht {
best = min(best, {dp[k-1][i+1] + C[mid][i] ,i} ); vector<line> lines;
} vector<ld> inter;
tie(dp[k][mid], opt) = best; int n;
compute(k,l, mid-1, optl, opt); inline bool ok(line &a, line &b, line &c) {
compute(k,mid+1, r, opt, optr); return a.inter(c) > a.inter(b);
} }
void add(line &l) { /// m1 < m2 < m3 ...
33

inside main(){ n = sz(lines);

fore(k,1,K) // definir el caso base k = 0. if(n && lines.back().m == l.m && lines.back().b >= l.
compute(k,0,n-1,0,n-1); b) return;
} if(n == 1 && lines.back().m == l.m && lines.back().b
< l.b) lines.pop_back(), n--;
while(n >= 2 && !ok(lines[n-2], lines[n-1], l)) {
7.7 Knuth’s Optimization --n;
lines.pop_back(); inter.pop_back();
}
const int nax = 1e3+20; lines.pb(l); n++;
const ll inf = LONG_LONG_MAX; if(n >= 2) inter.pb(lines[n-2].inter(lines[n-1]));
ll dp[nax][nax]; }
int k[nax][nax]; ll get_max(ld x) {

7
int C[nax][nax]; // puede depender de k if(sz(lines) == 0) return LLONG_MIN;

DYNAMIC PROGRAMMING
int main(){ if(sz(lines) == 1) return lines[0].eval(x);
for(int len=2; len<n; ++len){ int pos = lower_bound(all(inter), x) - inter.begin();
for(int l=0; l< n-len; ++l){ return lines[pos].eval(x);
}
int r= l+len; };
ll &ans= dp[l][r];
if(len== 2){
k[l][r]= l+1;
ans= C[l][r]; 7.9 CH Trick Dynamic
continue;
} typedef ll T;
ans= inf; const T is_query=-(1LL<<62);
for(int i= k[l][r-1]; i<= k[l+1][r]; ++i ){ struct line {
if(ans> dp[l][i]+ dp[i][r]){ T m,b;
ans= dp[l][i] + dp[i][r]; mutable multiset<line>::iterator it,end;
const line *succ(multiset<line>::iterator it) bool operator==(pt p){return abs(x-p.x)<=eps&&abs
const { (y-p.y)<=eps;}
return (++it == end ? nullptr : &*it); bool operator!=(pt p){ return !operator==(p);}
} bool operator<(pt p)const{ // for convex hull/set
bool operator < (const line &rhs) const { /map
if(rhs.b!=is_query) return m < rhs.m; return x<p.x-eps||(abs(x-p.x)<=eps&&y<p.y
const line *s = succ(it); -eps);}
if(!s) return 0; pt operator+(pt p){return pt(x+p.x,y+p.y);}
return b-s->b < (ld)(s->m-m)*rhs.m; pt operator-(pt p){return pt(x-p.x,y-p.y);}
} pt operator*(ld t){return pt(x*t,y*t);}
}; pt operator/(ld t){return pt(x/t,y/t);}
struct CHT : public multiset<line> { ///DOT
bool bad(iterator y) { ld operator*(pt p){return x*p.x+y*p.y;}
iterator z = next(y); // pt operator%(pt p){ // 3D
if(y==begin()) { // return pt(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y
if(z==end())return false; *p.x);}
return y->m == z->m && y->b <= z ld angle(pt p){ ///[0, pi]
->b; ld co = *this*p/(norm()*p.norm());
} return acos(max(-1.0L, min(1.0L, co)));
iterator x = prev(y); }
if(z == end()) return y->m==x->m&&y->b==x pt unit(){return *this/norm();}
->b; ld operator%(pt p){return x*p.y-y*p.x;}
return (ld)(x->b-y->b)*(z->m-y->m)>=(ld)( /// 2D from now on
y->b-z->b)*(y->m-x->m); bool left(pt p, pt q){ // is it to the left of
} directed line pq?
iterator next(iterator y){return ++y;} return (q-p)%(*this-p)>eps;
iterator prev(iterator y){return --y;} }
34

void add(T m, T b) { int left_int(pt p, pt q){ // is it to the left of

iterator y = insert((line){m,b}); directed line pq?
y->it = y; y->end = end(); ld cro = (q-p)%(*this-p);
if(bad(y)){ erase(y); return; } if(cro < eps)
while(next(y)!=end() && bad(next(y))) return -1;
erase(next(y)); else
while(y!=begin() && bad(prev(y)))erase( return (abs(cro) <= eps ? 0 : 1);
prev(y)); }
} pt rot(pt r){return pt(*this%r,*this*r);}
T eval(T x) { /// max pt rot(ld a){return rot(pt(sin(a),cos(a)));}
line l = *lower_bound((line){x,is_query}) pt rotp(ld a, pt p){
; pt aux = (*this - p).rot(a);
return l.m*x+l.b; return aux + p;
} }
}; };
pt ccw90(1,0), cw90(-1,0);
8 Geometry int sgn(ld x){
if(x<0)
return -1;

8
8.1 Point else if(abs(x) <= eps)
return 0;

GEOMETRY
struct pt { // for 3D add z coordinate else
ld x,y; return 1;
pt(ld x, ld y):x(x),y(y){} }
pt(){} //pt zero = pt(0,0,0); //for 3D
ld norm2(){return *this**this;}
ld norm(){return sqrt(norm2());} ld orient(pt a, pt b, pt c){ ///C: >0 left, ==0 on AB,
8.2
<0 right int sgn2(ld x){return x<0?-1:1;}
return (b-a)%(c-a); struct ln {
} pt p, pq; //POINT + DIRECTION

Line
ln(pt p, pt q) : p(p), pq(q-p){}
ld small_angle(pt p, pt q){ ///[0, pi] ([0, 180]) ln(ld a, ld b, ld c) : p(b == 0 ? pt(-c/a, 0) :
return acos(max(-1.0L, min((p*q)/(p.norm()*q.norm()), pt(0, -c/b)), pq(pt(b, -a)){} ///ax + by + c =
1.0L))); 0
} ln(){}
ld dir_ang_CW(pt a, pt b, pt c){ ///Vertex = B, from BA bool has(pt r){return dist(r)<=eps;} ///check if
-> BC (CW) point belongs
if(orient(a,b,c) >= 0){ bool seghas(pt r){return has(r)&&(r-p)*(r-(p+pq))
return small_angle(a-b, c-b); <=eps;} ///check if point belongs to segment
} else{ PQ
return 2*pi - small_angle(a-b, c-b); // bool operator /(ln l){return (pq.unit()ˆl.pq.unit
} ()).norm()<=eps;} // 3D
} bool operator/(ln l){return abs(pq.unit()%l.pq.
unit())<=eps;} /// PARALLEL CHECK
ld dir_ang_CCW(pt a, pt b, pt c){ ///Vertex = B, from BA bool operator==(ln l){return *this/l&&has(l.p);}
-> BC (CCW) pt operatorˆ(ln l){ /// intersection ln-ln
if(orient(a,b,c) <= 0){ if(*this/l) return pt(inf,inf);
return small_angle(a-b, c-b); pt r=l.p+l.pq*((p-l.p)%pq/(l.pq%pq));
} else{ // if(!has(r)){return pt(NAN,NAN,NAN);} //
return 2*pi - small_angle(a-b, c-b); check only for 3D
} return r;
} }
ld angle(ln l){return pq.angle(l.pq);} ///angle
bool in_angle_CW(pt a, pt b, pt c, pt p){ ///is P bet. 2 lines
inside ang(ABC) CW
35

int side(pt r){return has(r)?0:sgn2(pq%(r-p));}

return dir_ang_CW(a, b, p) <= dir_ang_CW(a, b, c); /// 1=L, 0= on, -1=R
} pt proj(pt r){return p+pq*((r-p)*pq/pq.norm2());}
bool in_angle_CCW(pt a, pt b, pt c, pt p){ ///is P pt refl(pt r){return proj(r)*2-r;}
inside ang(ABC) CW ld dist(pt r){return (r-proj(r)).norm();}
return dir_ang_CCW(a, b, p) <= dir_ang_CCW(a, b, c); ld dist2(pt r){return (r - proj(r)).norm2();}
} // ls dist(ln l){ // only 3D
// if(*this/l)return dist(l.p);
///3D - ORIENT // return abs((l.p-p)*(pqˆl.pq))/(pqˆl.pq).
ld orient(pt p, pt q, pt r, pt s){ return (q-p)%(r-p)|(s norm();
-p);} // }
bool coplanar(pt p, pt q, pt r, pt s){ ln rot(auto a){return ln(p,p+pq.rot(a));} /// 2D
return abs(orient(p, q, r, s)) < eps; respecto a P
} ln perp_at(pt r){return ln(r, r+pq.rot(ccw90));}
bool skew(pt p, pt q, pt r, pt s){ ///skew := bool cmp_proj(pt r, pt s){return pq*r<pq*s;}
neither intersecting/parallel int cmp_int(pt r, pt s){
return abs(orient(p, q, r, s)) > eps; ///lines: PQ, if(pq*r < pq*s)
RS return -1;
} else
ld orient_norm(pt p, pt q, pt r, pt n){ ///n := normal return (pq*r == pq*s ? 0 : 1);
to a given plane PI }

8
return (q-p)%(r-p)|n;/// equivalent to 2D cross on PI ( ln trans(pt d){ return ln(p + d, pq);} ///d = dir.

GEOMETRY
of ortogonal proj) vec
} };
ln bisec(ln l, ln m){ /// angle bisector
pt p=lˆm;
8.2 Line return ln(p, p+l.pq.unit()+m.pq.unit());
}
8.3
ln bisec(pt p, pt q){ /// segment bisector (2D) ( // p3 n = l1.d%l2.d;
mediatriz) // if(n == zero){ ///parallel
return ln((p+q)*.5,p).rot(ccw90); // return l1.dist(l2.o);

Convex Hull
} // }
///Segments // return abs((l2.o - l1.o)|n)/abs(n);
bool in_disk(pt a, pt b, pt p){return (a-p)*(b-p) <= 0;} //}
bool on_seg(pt a, pt b, pt p){ return orient(a,b,p) == 0 ///AGREGAR COMO ENCONTRAR LOS PUNTOS
&& in_disk(a,b,p);}
bool proper_inter(pt a, pt b, pt c, pt d, pt &out){
ld oa = orient(c,d,a),
ob = orient(c,d,b), 8.3 Convex Hull
oc = orient(a,b,c),
od = orient(a,b,d); // CCW order
if(oa*ob<0 && oc*od<0){ // Includes collinear points (change sign of EPS in left
out = (a*ob - b*oa) / (ob-oa); to exclude)
return true; vector<pt> chull(vector<pt> p){
} if(sz(p)<3)return p;
return false; vector<pt> r;
} sort(all(p)); // first x, then y
struct cmpX { forn(i,sz(p)){ // lower hull
bool operator()(pt a, pt b){ while(sz(r) >=2 && r.back().left(r[sz(r)
return make_pair(a.x, a.y) < make_pair(b.x, b.y); -2], p[i]))
} r.pop_back();
}; r.pb(p[i]);
}
set<pt,cmpX> seg_inter(pt a, pt b, pt c, pt d){ ///AB, CD r.pop_back();
pt out; int k = sz(r);
36

if(proper_inter(a,b,c,d,out)) return {out}; for(int i = sz(p)-1 ; i>=0 ; --i){ // upper hull

set<pt,cmpX> s; while(sz(r) >= k+2 && r.back().left(r[sz(
if(on_seg(c,d,a)) s.insert(a); r)-2], p[i]))
if(on_seg(c,d,b)) s.insert(b); r.pop_back();
if(on_seg(a,b,c)) s.insert(c); r.pb(p[i]);
if(on_seg(a,b,d)) s.insert(d); }
return s; r.pop_back();
} return r;
ld seg_pt(pt a, pt b, pt p){ ///DISTANTCE FROM P -> SEG. }
AB
if(a!=b){
ln l(a,b); 8.4 Polygon
/// a <= proj(p) && proj(p) <= b
if(l.cmp_proj(a,p) && l.cmp_proj(p,b)) return l.dist( int sgn(double x){return x<-eps?-1:x>eps;}
p); struct pol {
}
return min((p-a).norm(), (p-b).norm()); int n; vector<pt> p;
} pol(){}
pol(vector<pt> _p){p=_p;n = sz(p);}
ld seg_seg(pt a, pt b, pt c, pt d){ ///DISTANCE FROM SEG double area(){

8
. AB -> SEG. CD
pt aux; double r=0.;

GEOMETRY
if(proper_inter(a,b,c,d,aux)) return 0; forn(i,n) r += p[i]%p[(i+1)%n];
return min({seg_pt(a,b,c),seg_pt(a,b,d),seg_pt(c,d,a), return abs(r)/2; // negative if CW,
seg_pt(c,d,b)}); positive if CCW
} }
//ld dist(ln l1, ln3 l2){ ///for 3D bool isConvex() {
bool pos=false, neg=false;
8.4
for (int i=0; i<n; i++) { [0])) return false;
int o = orient(p[i], p[(i+1)%n], p[(i+2)%n]); int a=1, b=sz(p)-1; // returns true if
if (o > 0) pos = true; point on boundary

Polygon
if (o < 0) neg = true; while(b-a > 1){ // (change sign
} of EPS in left
return !(pos && neg); int c = (a+b)/2; // to
} return false in such case)
pt centroid(){ // (barycenter) if(!q.left(p[0],p[c])) a=c;
pt r(0,0); double t=0; ///REVISAR else b=c;
}
forn(i,n){ return !q.left(p[a],p[a+1]);
r = r+(p[i]+p[(i+1)%n])*(p[i]%p[( }
i+1)%n]);
t += p[i]%p[(i+1)%n]; pt farthest(pt v){ /// O(log(n)) only CONVEX
} if(n < 10){
return r/t/3; int k=0;
} for1(i,n-1) if(v*(p[i]-p[k]) >
bool has(pt q){ /// O(n) eps) k=i;
forn(i,n) return p[k];
}
if(ln(p[i],p[(i+1)%n]).seghas(q)) if(n == sz(p)) p.pb(p[0]);
return true; //lies on a segment pt a = p[1]-p[0];
int cnt=0; int s=0, e=n, ua=v*a>eps;
forn(i,n){ if(!ua && v*(p[n-1]-p[0]) <= eps) return
int j = (i+1)%n; p[0];
int k = sgn((q-p[j])%(p[i]-p[j])) while(1){
;
int u = sgn(p[i].y - q.y),v=sgn(p int m = (s+e)/2; pt c=p[m+1]-p[m
];
37

[j].y - q.y);
if(k>0 && u<0 && v>=0)cnt++; int uc = v*c> eps;
if(k<0 && v<0 && u>=0)cnt--; if(!uc && v*(p[m-1]-p[m]) <= eps)
} return p[m];
return cnt!=0; if(ua && (!uc||v*(p[s]-p[m]) >
} eps))e=m;
else if(ua || uc || v*(p[s]-p[m])
void remove_col(){ ///for haslog >= -eps) s=m, a=c, ua=uc;
vector<pt> s; else e=m;
forn(i, n){ assert(e>s+1);
line l(p[(i-1+n)%n], p[(i+1)%n]); }
if (!l.seghas(p[i])) s.pb(p[i]); }
}
p.swap(s); pol cut(ln l){ // cut CONVEX polygon by line l
} vector<pt> q; // returns part at left of
l.pq
void normalize(){ /// (call before haslog, remove forn(i,n){
collinear first) int d0 = sgn(l.pq%(p[i]-l.p)), d1
remove_col(); = sgn(l.pq%(p[(i+1)%n]-l.p));
if(p[2].left(p[0],p[1])) reverse(all(p)); if(d0 >= 0) q.pb(p[i]);
int pi = min_element(all(p)) - p.begin(); ln m(p[i], p[(i+1)%n]);

8
vector<pt> s(n); if(d0*d1<0 && !(l/m)) q.pb(lˆm);
forn(i,n) s[i] = p[(pi+i)%n];

GEOMETRY
}
p.swap(s); return pol(q);
} }
bool haslog(pt q){ /// O(log(n)) only CONVEX. ld intercircle(circle c){ /// area of
Call normalize first intersection with circle
if(q.left(p[0],p[1]) || q.left(p.back(),p ld r = 0.;
8.5
forn(i,n){ r = max(r,(b[i]-a[j]).norm2());
int j = (i+1)%n; ld w = c. if((b[(i+1)%sz(b)]-b[i])%(a[(j+1)%sz(a)]-a[j]) <=
intertriangle(p[i], p[j]); eps) break;

Circle
if((p[j]-c.o)%(p[i]-c.o) > 0) r+= }
w; }
else r-=w; return r;
} }
return abs(r);
}
ld callipers(){ // square distance: pair of most 8.5 Circle
distant points
ld r=0; // prereq: convex, ccw, NO struct circle {
COLLINEAR POINTS pt o; ld r;
for(int i=0,j=n<2?0:1; i<j; ++i){ circle(pt o, ld r):o(o),r(r){}
for(;;j=(j+1)%n){ circle(pt x, pt y, pt z){o=bisec(x,y)ˆbisec(x,z);
r = max(r,(p[i]-p[j]). r=(o-x).norm();}///circumcircle
norm2()); bool has(pt p){return (o-p).norm()<=r+eps;}
if((p[(i+1)%n]-p[i])%(p[( vector<pt> operatorˆ(circle c){ // ccw
j+1)%n]-p[j]) <= eps) vector<pt> s;
break; ld d = (o - c.o).norm();
} if(d > r+c.r+eps || d+min(r,c.r)+eps <
} max(r,c.r)) return s;
return r; ld x = (d*d - c.r*c.r + r*r)/(2*d);
} ld y = sqrt(r*r - x*x);
}; pt v = (c.o - o)/d;
// Dynamic convex hull trick s.pb(o + v*x - v.rot(ccw90)*y);
vector<pol> w; if(y>eps) s.pb(o + v*x + v.rot(ccw90)*y);
38

void add(pt q){ // add(q), O(logˆ2(n)) return s;

vector<pt> p = {q}; }
while(sz(w) && sz(w.back().p) < 2*sz(p)){ vector<pt> operatorˆ(ln l){
for(pt v: w.back().p) p.pb(v); vector<pt> s;
w.pop_back(); pt p=l.proj(o);
} ld d=(p-o).norm();
w.pb(pol(chull(p))); if(d-eps>r)return s;
} if(abs(d-r)<=eps){s.pb(p);return s;}
ll query(pt v){ // max(q*v:q in w), O(logˆ2(n)) d=sqrt(r*r-d*d);
ll r = -inf; s.pb(p+l.pq.unit()*d);
for(auto& p : w) r = max(r, p.farthest(v)*v); s.pb(p-l.pq.unit()*d);
return r; return s;
} }
/// max_dist between 2 points (pa, pb) of 2 conv. vector<pt> tang(pt p){
polygons (a,b) ld d = sqrt((p-o).norm2()-r*r);
ll rot_cal(vector<pt>& a, vector<pt>& b){ return *thisˆcircle(p,d);
pair<ll, int> start = {-1, -1}; }
if(sz(a) == 1) swap(a, b); bool in(circle c){ // non strict
ld d = (o-c.o).norm();
forn(i, sz(a)){ return d+r <= c.r+eps;

8
start = max(start, {(b[0] - a[i]).norm2(), i}); }
} ld intertriangle(pt a, pt b){ // area of

GEOMETRY
intersection with oab
if(sz(b) == 1) return start.fi; if(abs((o-a)%(o-b))<=eps)return 0.;
ll r = 0; vector<pt> q = {a}, w = *thisˆln(a,b);
for(int i = 0, j = start.se; i<sz(b); ++i){ if(sz(w)==2) for(auto p:w) if((a-p)*(b-p)
for(;;j=(j+1)%sz(a)){ <-eps) q.pb(p);
q.pb(b);
8.6
if(sz(q)==4 && (q[0]-q[1])*(q[2]-q[1])> struct Cmp { // IMPORTANT: add const in pt operator -
eps) swap(q[1],q[2]); pt r;
ld s=0; Cmp(pt r):r(r){}

Radial Order
forn(i, sz(q)-1){ int cuad(const pt &a)const {
if(!has(q[i]) || !has(q[i+1])) s if(a.x>0 && a.y>=0) return 0;
+=r*r*(q[i]-o).angle(q[i+1]-o) if(a.x<=0 && a.y>0) return 1;
/2; if(a.x<0 && a.y<=0) return 2;
else s+=abs((q[i]-o)%(q[i+1]-o) if(a.x>=0 && a.y<0) return 3;
/2); assert(a.x==0&&a.y==0);
} return -1;
return s; }
} bool cmp(const pt& p1, const pt& p2)const {
}; int c1=cuad(p1), c2=cuad(p2);
if(c1==c2) return p1.y*p2.x < p1.x*p2.y;
vector<ld> intercircles(vector<circle> c){ return c1<c2;
vector<ld> r(sz(c)+1); // r[k]: area covered by }
at least k circles bool operator()(const pt& p1, const pt& p2)const
forn(i,sz(c)){ // O(nˆ2 log n) (high {
constant) return cmp(p1-r,p2-r);
int k=1; Cmp s(c[i].o); }
vector<pair<pt,int> > p = };
{{c[i].o+pt(1,0)*c[i].r,0},{c[i].o-pt
(1,0)*c[i].r,0}};
forn(j, sz(c))if(j!=i){ 8.7 Coords
bool b0 = c[i].in(c[j]), b1=c[j].
in(c[i]); struct coords{
if(b0 && (!b1||i<j))k++; p3 o, dx, dy, dz;
39

else if(!b0 && !b1){ coords(){}

auto v = c[i]ˆc[j]; coords(p3 p, p3 q, p3 r){ ///Creates a R3 space
if(sz(v)==2){ with X-Y plane at PQR
p.pb({v[0],1}); o = p;
p.pb({v[1],-1}); dx = unit(q-p);
if(s(v[1],v[0]))k dz = unit(dx%(r-p));
++; dy = dz%dx;
} }
}
} pt pos2(p3 p){ return pt((p-o)*dx, (p-o)*dy);}
sort(p.begin(),p.end(), ///2D Coordinates of the orthogonal proj
[&](pair<pt,int> a, pair<pt,int> p3 pos3(p3 p){ return p3((p-o)*dx, (p-o)*dy, (p-o)*dz)
b){return s(a.fi,b.fi);}); ;} ///3D Coordinates in new R3-space
forn(j,sz(p)){ };
pt p0 = p[j?j-1:sz(p)-1].fi, p1 =
p[j].fi;
ld a=(p0-c[i].o).angle(p1-c[i].o) 8.8 Plane
;
r[k] += (p0.x-p1.x)*(p0.y+p1.y)
/2+c[i].r*c[i].r*(a-sin(a))/2; struct plane {
k+=p[j].se; pt a, n; // n: normal unit vector

8
} plane(pt a, pt b, pt c): a(a),n(((b-a)ˆ(c-a)).
} unit()){}

GEOMETRY
return r; plane(){}
} bool has(pt p){return abs((p-a)*n) <= eps;}
///DONE
double angle(plane w){return acos(n*w.n);}
8.6 Radial Order double dist(pt p){return abs((p-a)*n);}
///DONE
8.9
bool inter(ln l, pt& r){ //LINE-PLANE --> POINT return s;
double x = n*(l.p+l.pq-a), y = n*(l.p-a); }
if(abs(x-y) <= eps) return false;

Halfplane
r = (l.p*x-(l.p+l.pq)*y)/(x-y);
return true;
} 8.10 Sphere
bool inter(plane w, ln& r){//PLANE-PLANE --> LINE
pt nn = nˆw.n;pt v = nˆnn;double d = w.n* p3 sph_deg(ld r, ld lat, ld lon){
v;
if(abs(d) <= eps) return false; lat *= pi/180, lon *= pi/180;
pt p = a+v*(w.n*(w.a-a)/d); return p3(r*cos(lat)*cos(lon), r*cos(lat)*sin(lon), r*
r = ln(p,p+nn); sin(lat));
return true; }
} p3 sph(ld r, ld lat, ld lon){
pt proj(pt p){inter(ln(p,p+n),p); return p;} return p3(r*cos(lat)*cos(lon), r*cos(lat)*sin(lon), r*
///DONE sin(lat));
}; }
int sph_ln_inter(p3 o, ld r, ln3 l, pair<p3,p3> &out){
ld h2 = r*r - l.sq_dist(o);
8.9 Halfplane if(h2 < 0) return 0; ///no intersection
p3 p = l.proj(o);
p3 h = l.d*sqrt(h2)/abs(l.d); ///media cuerda
// polygon intersecting left side of hps out = {p-h, p+h};
struct hp: public ln{ return 1 + (h2>0);
ld angle; }
hp(){}
hp(pt a, pt b){p=a; pq=b-a; angle=atan2(pq.y,pq.x ld sph_dist(p3 o, ld r, p3 a, p3 b){ ///if A,B not in
);} sphere -> takes radial projections (from O)
40

bool operator<(hp b)const{return angle<b.angle;} return r * angle(a-o, b-o);

bool out(pt q){return pq%(q-p)<-eps;} }
};
bool valid_seg(p3 a, p3 b){ ///Accepts A==B
vector<pt> intersect(vector<hp> b){ return a%b != zero || (a*b) > 0; ///Denies opposite to
vector<pt>bx = {{inf,inf},{-inf,inf},{-inf,-inf each other (seg not well defined)
},{inf,-inf}}; }
forn(i,4) b.pb(hp(bx[i],bx[(i+1)%4]));
sort(all(b)); bool proper_inter(p3 a, p3 b, p3 c, p3 d, p3 &out){
int n=sz(b), q=1, h=0; p3 ab = a%b, cd = c%d;
vector<hp> c(sz(b)+10); int oa = sgn(cd*a),
forn(i,n){ ob = sgn(cd*b),
while(q<h&&b[i].out(c[h]ˆc[h-1])) h--; oc = sgn(ab*c),
while(q<h&&b[i].out(c[q]ˆc[q+1])) q++; od = sgn(ab*d);
c[++h]=b[i]; out = ab%cd * od;
if(q<h&&abs(c[h].pq%c[h-1].pq)<eps){ return (oa != ob && oc != od && oa != oc);
if(c[h].pq*c[h-1].pq<=0) return }
{}; bool on_seg(p3 a, p3 b, p3 p){ ///segment = [A,B]
h--; p3 n = a%b;
if(b[i].out(c[h].p)) c[h]=b[i]; if(n == zero){

8
} return a%p == zero && (a*p) > 0;
}

GEOMETRY
}
while(q<h-1&&c[q].out(c[h]ˆc[h-1]))h--; return (n*p) == 0 && (n*(a%p)) >= 0 && (n*(b%p)) <= 0;
while(q<h-1&&c[h].out(c[q]ˆc[q+1]))q++; }
if(h-q<=1)return {};
c[h+1]=c[q]; struct dir_set : vector<p3> {
vector<pt> s; using vector::vector; ///import constructors
fore(i,q,h) s.pb(c[i]ˆc[i+1]); void insert(p3 p){
8.11
for(p3 q : *this) return abs(vec_area2(p))/2.0;
if(p%q == zero) return; }
pb(p);

Polih
} struct edge{
}; int v;
bool same; ///:= is common edge in same order?
dir_set seg_inter(p3 a, p3 b, p3 c, p3 d){ };
assert(valid_seg(a, b) && valid_seg(c, d));
p3 out; void reorient(vector<vector<p3>> &faces){ ///given a
if(proper_inter(a, b, c, d, out)) return {out}; series of faces, make orientations (normal vec’s)
dir_set s; consistent
if(on_seg(c, d, a)) s.insert(a); int n = sz(faces);
if(on_seg(c, d, b)) s.insert(b); ///Find common edges + create adjacency graph
if(on_seg(a, b, c)) s.insert(c); vector<vector<edge>> g(n);
if(on_seg(a, b, d)) s.insert(d); map<pair<p3,p3>, int> es;
return s; forn(u, n){
} int m = sz(faces[u]);
forn(i, m){
ld angle_sph(p3 a, p3 b, p3 c){ p3 a = faces[u][i], b = faces[u][(i+1)%m];
return angle(a%b, a%c); ///let’s look at edge [a, b];
} if(es.count({a,b})){ ///seen in same order
ld oriented_angle_sph(p3 a, p3 b, p3 c){ int v = es[{a,b}];
if((a%b*c) >= 0) g[u].pb({v, true});
return angle_sph(a, b, c); g[v].pb({u, true});
else } else if(es.count({b,a})){ ///seen in diff order
return 2*pi - angle_sph(a, b, c); int v = es[{b,a}];
} g[u].pb({v, false});
g[v].pb({u, false});
41

ld area_sph(ld r, vector<p3> &p){ ///for solid } else{ ///not seen yet

angle -> r = 1 es[{a,b}] = u;
int n = sz(p); }
ld sum = -(n-2)*pi; }
forn(i,n) }
sum += oriented_angle_sph(p[(i+1)%n], p[(i+2)%n], p[i ///bfs to find which faces should be flipped
]); vector<bool> seen(n, false), flip(n);
return r*r*sum; flip[0] = false;
} queue<int> q; q.push(0);
while(sz(q)){
int winding_number(vector<vector<p3>> &faces){ int u = q.front(); q.pop();
ld sum = 0; for(edge e: g[u]){
for(vector<p3> f: faces) if(seen[e.v]) continue;
sum += remainder(area_sph(1, f), 4*pi); seen[e.v] = true;
return round(sum / (4*pi)); flip[e.v] = flip[u]ˆe.same; ///If the edge was in
} same order
q.push(e.v); ///one of the two
should be flipped
8.11 Polih }
}

8
p3 vec_area2(vector<p3> &p){ ///normal vector to the ///perform the flips
surface forn(i, n){

GEOMETRY
p3 a = zero; if(flip[i])
forn(i, n) reverse(all(faces[u]));
a = a + p[i]%p[(i+1)%sz(p)]; }
return a; }
}
ld area(vector<p3> &p){ ld volume(vector<vector<p3>> &faces){
8.12
ld vol = 0; return l1.d%l2.d == zero;
for(vector<p3> f: faces){ }
vol += (vec_area2(f)*f[0]); bool perp(ln3 l1, ln3 l2){

Line3
} return (l1.d|l2.d) == 0;
return abs(vol)/6.0; ///could be <0 if normals }
point to inside
} ///PLANE - LN3
ld angle(plane p, ln3 l){
return pi/2 - small_angle(p.n, l.d);
}
8.12 Line3 bool parallel(plane p, ln3 l){
return (p.n|l.d) == 0;
struct ln3{ ///Remove "3" if not 2D needed }
p3 d, o; ///direction, origin bool perp(plane p, ln3 l){
ln3(){} return p.n%l.d == zero;
ln3(p3 p, p3 q) : d(q-p), o(p){} ///given 2 points }
ln3(plane p1, plane p2){ ///given 2 planes ln3 perp_at(plane p, p3 o){
d = p1.n%p2.n; return line(o, o+p.n);
o = (p2.n%p1.d - p1.n%p2.d)%d/sq(d); }
} plane perp_at(ln3 l, p3 o){
ld sq_dist(p3 p){ return sq(d%(p-o)/sq(d));} return plane(l.d, o);
ld dist(p3 p){ return sqrt(sq_dist(p));} }
bool cmp_proj(p3 p1, p3 p2){ return (d|p1) < (d|p2);}
int cmp(p3 p, p3 q){
if((d|p) < (d|q)){ 8.13 Point3
return -1;
} else if((d|p) == (d|q)){
42

struct p3{
return 0; ld x, y, z;
} else{ p3() {}
return 1; p3 (ld xx, ld yy, ld zz){x = xx, y = yy, z = zz;}
} ///scalar operators
} p3 operator*(ld f){ return p3(x*f, y*f, z*f);}
p3 proj(p3 p){ return o + d*(d|(p-o))/sq(d);} p3 operator/(ld f){ return p3(x/f, y/f, z/f);}
p3 refl(p3 p){ return proj(p)*2 - p;} ///p3 operators
p3 inter(plane p){ return o - d*p.side(o)/(d|p.n);} p3 operator-(p3 p){ return p3(x-p.x, y-p.y, z-p.z);}
}; p3 operator+(p3 p){ return p3(x+p.x, y+p.y, z+p.z);}
p3 operator%(p3 p){ return p3(y*p.z - z*p.y, z*p.x - x*
///LN3 - LN3 p.z, x*p.y - y*p.x);} /// (|p||q|sin(ang))*
ld dist(ln3 l1, ln3 l2){ normal
p3 n = l1.d%l2.d;
if(n == zero){ ///parallel ld operator|(p3 p){ return x*p.x + y*p.y + z*p.z;}
return l1.dist(l2.o); ///Comparators
} bool operator==(p3 p){ return tie(x,y,z) == tie(p.x,p.y
return abs((l2.o - l1.o)|n)/abs(n); ,p.z);}
} bool operator!=(p3 p){ return !operator==(p);}
bool operator<(p3 p){ return tie(x,y,z) < tie(p.x,p.y,p
p3 closest(ln3 l1, ln3 l2){ ///closest point ON line .z);}

8
l1 TO line l2 };
p3 n2 = l2.d%(l1.d%l2.d); p3 zero = p3(0,0,0);

GEOMETRY
return l1.o + l1.d*((l2.o-l1.o)|n2)/(l1.d|n2)); template <typename T> int sgn(T x){
} return (T(0) < x) - (x < T(0));
ld angle (ln3 l1, ln3 l2){ }
return small_angle(l1.d, l2.d);
} ///BASICS
bool parallel(ln3 l1, ln3 l2){ ld sq(p3 p){ return p|p;}
8.14
ld abs(p3 p){ return sqrt(sq(p));} ///PLANE - PLANE
p3 unit(p3 p) { return p/abs(p);} ld angle(plane p1, plane p2){
return small_angle(p1.n, p2.n);

Plane3
///ANGLES }
ld angle(p3 p, p3 q){ ///[0, pi] bool parallel(plane p1, plane p2){
ld co = (p|q)/abs(p)/abs(q); return p1.n%p2.n == zero;
return acos(max(-1.0, min(1.0, co))); }
} bool perp(plane p1, plane p2){
ld small_angle(p3 p, p3 q){ ///[0, pi/2] return (p1.n|p2.n) == 0;
return acos(min(abs(p|q)/abs(p)/abs(q), 1.0)) }
}
///PLANE - LN3
///3D - ORIENT ld angle(plane p, ln3 l){
ld orient(p3 p, p3 q, p3 r, p3 s){ return (q-p)%(r-p)|(s return pi/2 - small_angle(p.n, l.d);
-p);} }
bool coplanar(p3 p, p3 q, p3 r, p3 s){ bool parallel(plane p, ln3 l){
return abs(orient(p, q, r, s)) < eps; return (p.n|l.d) == 0;
} }
bool skew(p3 p, p3 q, p3 r, p3 s){ ///skew := bool perp(plane p, ln3 l){
neither intersecting/parallel return p.n%l.d == zero;
return abs(orient(p, q, r, s)) > eps; ///lines: PQ, }
RS ln3 perp_at(plane p, p3 o){
} return line(o, o+p.n);
ld orient_norm(p3 p, p3 q, p3 r, p3 n){ ///n := normal }
to a given plane PI plane perp_at(ln3 l, p3 o){
return (q-p)%(r-p)|n;/// equivalent to 2D cross on PI ( return plane(l.d, o);
of ortogonal proj) }
43

9 Miscellaneous
8.14 Plane3
9.1 Counting Sort
struct plane{ ///ax + by + cz = d <=> n|(x, y, z) = d (
all points with p|n = d) // it suppose that every element is non-negative
p3 n; ld d; ///normal, offset // in other case just translate to the right the elements
plane() {} void counting_sort(vi &a){
plane(p3 n, ld d) : n(n), d(d) {} int n = sz(a);
plane(p3 n, p3 p) : n(n), d(n|p) {} /// int maximo = *max_element(all(a));
given normal, point vector<int> cnt(maximo+1);
plane(p3 p, p3 q, p3 r) : plane((q-p)%(r-p), p) {} /// forn(i,n) ++cnt[a[i]];
given 3 points (uses previous line!!) for(int i = 0, j = 0; i <= maximo; ++i)
///point operators while(cnt[i]--) a[j++] = i;
ld side(p3 p){ return (n|p) - d;} ///>0 side }

9
pointed by n (above), ==0 on plane, <0 below
ld dist(p3 p){ return abs(side(p))/abs(n);}

MISCELLANEOUS
bool has(pt p){return dist(p) <= eps;} 9.2 Expression Parsing
p3 proj(p3 p){ return p - n*side(p)/sq(n);}
p3 refl(p3 p){ return p - n*2*side(p)/sq(n);}
///translations bool delim(char c) {
plane translate(p3 t){ return plane(n, d+(n|t));} return c == ’ ’;
}
plane shift_up(ld dis) { return plane(n, d+dis*abs(n)) bool is_op(char c) {
;}
}; return c == ’+’ || c == ’-’ || c == ’*’ || c == ’/’;
}
bool is_unary(char c) { char cur_op = s[i];
return c == ’+’ || c==’-’; if (may_be_unary && is_unary(cur_op))
} cur_op = -cur_op;
int priority (char op) { while (sz(op) && (
if (op < 0) return 3; // unary operator (cur_op >= 0 && priority(op.top()) >= priority(
if (op == ’+’ || op == ’-’) return 1; cur_op)) ||
if (op == ’*’ || op == ’/’) return 2; (cur_op < 0 && priority(op.top()) >
return -1; priority(cur_op))
} )) {
void process_op(stack<int>& st, char op) { process_op(st, op.top());
op.pop();
if (op < 0) { }
int l = st.top(); st.pop(); op.push(cur_op);
switch (-op) { may_be_unary = true;
case ’+’: st.push(l); break; } else {
case ’-’: st.push(-l); break; int number = 0;
} while (i < sz(s) && isalnum(s[i]))
} else { number = number * 10 + s[i++] - ’0’;
int r = st.top(); st.pop(); --i;
int l = st.top(); st.pop(); st.push(number);
switch (op) { may_be_unary = false;
case ’+’: st.push(l + r); break; }
case ’-’: st.push(l - r); break; }
case ’*’: st.push(l * r); break;
case ’/’: st.push(l / r); break; while(sz(op)){
} process_op(st, op.top());
} op.pop();
} }
44

return st.top();
int evaluate(string& s) { }
stack<int> st;
stack<char> op;
bool may_be_unary = true;
forn(i,sz(s)) { 9.3 Ternary Search
if (delim(s[i]))
continue; double ternary_search(double l, double r) {
if (s[i] == ’(’) { while (r - l > eps) {
op.push(’(’); double m1 = l + (r - l) / 3;
may_be_unary = true; double m2 = r - (r - l) / 3;
} else if (s[i] == ’)’) { double f1 = f(m1), f2 = f(m2);
while (op.top() != ’(’) { if (f1 < f2) l = m1;
process_op(st, op.top()); else r = m2;
op.pop(); }
} return f(l); //return the maximum of
op.pop(); f(x) in [l, r]
may_be_unary = false; }
} else if (is_op(s[i])) {
10 Theory Binomial coefficients
Number of ways to pick a multiset of size k from n elements: n+k−1

k
Number of n-tuples of non-negative integers with sum s: s+n−1 , at most s: s+n

DP Optimization Theory s−1
n−1 n

Name Original Recurrence Sufficient Condition From To Number of n-tuples of positive integers with sum s: n−1
CH 1 dp[i] = minj<i {dp[j] + b[j] ∗ b[j] ≥ b[j + 1] Option- O(n2 ) O(n) Number of lattice paths from (0, 0) to (a, b), restricted to east and north steps:
a+b

a[i]} ally a[i] ≤ a[i + 1] a
n
n1 nk
Multinomial theorem. (a1 + · · · + ak )n =
P
CH 2 dp[i][j] = mink<j {dp[i − b[k] ≥ b[k+1] Option- O(kn2 ) O(kn) P n1 ,...,nk a1 . . . ak , where
1][k] + b[k] ∗ a[j]} ally a[j] ≤ a[j + 1] ni ≥ 0 and ni = n.
D&Q dp[i][j] = mink<j {dp[i − A[i][j] ≤ A[i][j + 1] O(kn2 ) O(kn log n)
n n!
1][k] + C[k][j]} = M (n1 , . . . , nk ) =
Knuth dp[i][j] = A[i, j − 1] ≤ A[i, j] ≤ O(n3 ) O(n2 ) n1 , . . . , n k n1 ! . . . nk !
mini<k<j {dp[i][k] + A[i + 1, j] M (a, . . . , b, c, . . . ) = M (a + · · · + b, c, . . . )M (a, . . . , b)
dp[k][j]} + C[i][j]
Catalan numbers.
Notes:
(2n)! 2(2n+1)
ˆ Cn = n+1
1 2n

n = (n+1)!n! con n ≥ 0, C0 = 1 y Cn+1 = n+2 Cn
ˆ A[i][j] - the smallest k that gives the optimal answer, for example in dp[i][j] = Pn−1
Cn = i=0 Ci Cn−1−i
dp[i − 1][k] + C[k][j]
ˆ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440,
ˆ C[i][j] - some given cost function 9694845, 35357670
ˆ We can generalize a bit in the following way dp[i] = minj<i {F [j] + b[j] ∗ a[i]}, ˆ Cn is the number of: properly nested sequences of n pairs of parentheses;
45

where F [j] is computed from dp[j] in constant time rooted ordered binary trees with n + 1 leaves; triangulations of a convex
(n + 2)-gon.

Combinatorics Derangements. Number of permutations of n = 0, 1, 2, . . . elements without

Sums fixed points is 1, 0, 1, 2, 9, 44, 265, 1854, 14833, . . . Recurrence: Dn = (n−1)(Dn−1 +
Pn n
n! n
k = n(n + 1)/2 k = (n−k)!k!
Dn−2 ) = nD n−1 + (−1) . Corollary: number of permutations with exactly k fixed
Pbk=0 n n−1
n
points is k Dn−k .
+ n−1

k = (a + b)(b − a + 1)/2 k =
Pnk=a 2 n+1
k
n+1
k−1
n
Stirling numbers of 1st kind. sn,k is (−1)n−k times the number of permu-
k = n(n + 1)(2n + 1)/6 k = n−k+1 k
Pk=0
n 3 n n−k n tations of n elements with exactly k permutation cycles. |sn,k | = |sn−1,k−1 | + (n −
k = n2 (n + 1)2 /4 = k+1 k Pn k n
Pk=0
n
k+1
n
n n−1
1)|sn−1,k |. k=0 sn,k x = x
k 4 = (6n5 + 15n4 + 10n3 − n)/30 k = n−k nd
Stirling numbers of 2 kind. Sn,k is the number of ways to partition a
Pnk=0 5 n n−k+1
k
n

k = (2n6 + 6n5 + 5n4 − n2 )/12 k = set of n elements into P exactly k non-empty subsets. Sn,k = Sn−1,k−1 + kSn−1,k .
Pnk=0 k n+1
k
28.8
k−1
n
Pnk=0 x k= (x − 1)/(x − 1) 12! ≈ 2 Sn,1 = Sn,n = 1. xn = k=0 Sn,k xk
k=0 kx = (x − (n + 1)xn+1 + nxn+2 )/(x − 1)2 20! ≈ 261.1 Bell numbers. Bn is the number of partitions of n elements. B0 , . . . =
2
1 + x + x + · · · = 1/(1 − x) 1, 1, 2, 5, 15,
P52,n
203,. . .
n Pn
Bn+1 = k=0 k Bk = k=1 Sn,k . Bell triangle: Br = ar,1 = ar−1,r−1 ,
ˆ Hockey-stick identity
Pn i
n+1
ar,c = ar−1,c−1 + ar,c−1 .
= Pm−1 1
Pn n+1

i=r r r+1 Bernoulli numbers. k=0 k n = n+1 k=0 k Bk mn+1−k .
Pm m+1 1
ˆ Number of ways to color n-objects with r-colors if all colors must be used at j=0 j Bj = 0. B0 = 1, B1 = − 2 . Bn = 0, for all odd n 6= 1.
least
Pr once Pr Eulerian numbers. E(n, k) is the number of permutations with exactly k
r r
r−k n

k=0 k (−1) k o k=0 r−k (−1)k (r − k)n descents (i : πi < πi+1 ) / ascents (πi > πi+1 ) / excedances (πi > i) / k + 1 weak
excedances (πi ≥ i). Pollard-ρ. Choose random x1 , and let xi+1 = x2i − 1 (mod n). Test
Formula: E(n, k) = (k + 1)E(n − 1, k) + (n − k)E(n − 1, k − 1). xn = gcd(n, x2k +i −
√ x2k ) as possible n’s factors for k = 0, 1, . . . Expected time to find
Pn−1 x+k
k=0 E(n, k) n .
a factor: O( m), where m is smallest prime power in n’s factorization. That’s
Burnside’s O(n1/4 ) if you check n = pk as a special case before factorization.
P lemma. The number of orbits under group G’s action on set X: n
|X/G| = |G|1
g∈G |Xg |, where Xg = {x ∈ X : g(x) = x}. (“Average number of
Fermat primes. A Fermat prime is a prime of form 22 + 1. The only known
fixed points.”) Fermat primes are 3, 5, 17, 257, 65537. A number of form 2n + 1 is prime only if
Let w(x) be weight of x’s orbit. Sum of all orbits’ weights:
P it is a Fermat prime.
o∈X/G w(o) =
1
P P Fermat’s Theorem. Let m be a prime and x and m coprimes, then:
|G| g∈G x∈Xg w(x).
ˆ xm−1 ≡ 1 mod m

Number Theory ˆ xk mod m = xk mod (m−1)

mod m
Linear diophantine equation. ax + by = c. Let d = gcd(a, b). A solu- ˆ x φ(m)
≡ 1 mod m
tion exists iff d|c. If (x0 , y0 ) is any solution, then all solutions are given by
(x, y) = (x0 + db t, y0 − ad t), t ∈ Z. To find some solution (x0 , y0 ), use extended Perfect numbers. n > 1 is called perfect if it equals sum of its proper divisors
GCD to solve ax0 + by0 = d = gcd(a, b), and multiply its solutions by dc . and 1. Even n is perfect iff n = 2p−1 (2p − 1) and 2p − 1 is prime (Mersenne’s). No
Linear diophantine equation in n variables: a1 x1 + · · · + an xn = c has solu- odd perfect numbers are yet found.
tions iff gcd(a1 , . . . , an )|c. To find some solution, let b = gcd(a2 , . . . , an ), solve Carmichael numbers. A positive composite n is a Carmichael number
a1 x1 + by = c, and iterate with a2 x2 + · · · = y. (an−1 ≡ 1 (mod n) for all a: gcd(a, n) = 1), iff n is square-free, and for all prime
Extended GCD divisors p of n, p − 1 divides n − 1. Qk
Number/sum of divisors. τ (pa1 1 . . . pakk ) = j=1 (aj + 1). σ(pa1 1 . . . pakk ) =
// Finds g = gcd(a,b) and x, y such that ax+by=g. Qk pjaj +1 −1
46

// Bounds: |x|<=b+1, |y|<=a+1. j=1 pj −1 .

τ (n)
void gcdext(int &g, int &x, int &y, int a, int b) Product of divisors. µ(n) = n 2

{ if (b == 0) { g = a; x = 1; y = 0; } k(k+1)
else { gcdext(g, y, x, b, a % b); y = y - (a / b) * x; } } ˆ if p is a prime, then: µ(pk ) = p 2

Multiplicative inverse of a modulo m: x in ax + my = 1, or aφ(m)−1 (mod m). ˆ if a and b are coprimes, then: µ(ab) = µ(a)τ (b) µ(b)τ (a)
Chinese Remainder Theorem. System x ≡ ai (mod mi ) for i = 1, . . . , n, Euler’s phi function. φ(n) = |{m ∈ N, m ≤ n, gcd(m, n) = 1}|.
with pairwise relatively-prime mi has a unique solution modulo M = m1 m2 . . . mn :
φ(m)φ(n) gcd(m,n)
M
x = a1 b1 m 1
+ · · · + an bn mM
n
M
(mod M ), where bi is modular inverse of m i
modulo ˆ φ(mn) = φ(gcd(m,n)) .
mi .
System x ≡ a (mod m), x ≡ b (mod n) has solutions iff a ≡ b (mod g), ˆ φ(p) = p − 1 si p es primo
where g = gcd(m, n). The solution is unique modulo L = mn g , and equals: ˆ φ(pa ) = pa (1 − p1 ) = pa−1 (p − 1)
x ≡ a + T (b − a)m/g ≡ b + S(a − b)n/g (mod L), where S and T are integer
solutions of mT + nS = gcd(m, n). ˆ φ(n) = n(1 − 1
p1 )(1 − 1
p2 )...(1 − 1
pk ) donde pi es primo y divide a n
Prime-counting function. π(n) = |{p ≤ n : p is prime}|. n/ ln(n) < π(n) <
1.3n/ ln(n). π(1000) = 168, π(106 ) = 78498, π(109 ) = 50 847 534. n-th prime Euler’s theorem. aφ(n) ≡ 1 (mod n), if gcd(a, n) = 1.
≈ n ln n. Wilson’s theorem. p is prime iff (p − 1)! ≡ −1 (mod p).
Miller-Rabin’s primality test. Given n = 2r s + 1 with odd s, and a random Mobius function. µ(1) = 1. µ(n) = 0, if n is not squarefree. µ(n) = (−1)s ,
integer 1 < a < n. if n is the product of s distinct
P primes. Let f , F be Pfunctions on positive integers.
j
If as ≡ 1 (mod n) or a2 s ≡ −1 (mod n) for some 0 ≤ j ≤ r − 1, then n is a If for all n ∈ N , F (n) = d|n f (d), then f (n) = d|n µ(d)F ( nd ), and vice versa.
φ(n) = d|n µ(d) nd .
P P
probable prime. With bases 2, 7 and 61, the test indentifies all composites below d|n µ(d) = 1.
232 . Probability of failure for a random a is at most 1/4. 2
P Q P
If f is multiplicative, then d|n µ(d)f (d) = p|n (1 − f (p)), d|n µ(d) f (d) =
Q
(1 + f (p)). Postage stamps/McNuggets problem. Let a, b be relatively-prime inte-
Pp|n
d|n µ(d) = e(n) = [n == 1]. gers. There are exactly 12 (a − 1)(b − 1) numbers not of form ax + by (x, y ≥ 0), and
Sf (n) = p=1 (1 + f (pi ) + f (p2i ) + ... + f (pei i )), p - primes(n).
Q the largest is (a − 1)(b − 1) − 1 = ab − a − b.
Fermat’s two-squares theorem. Odd prime p can be represented as a sum
Legendre symbol. If p is an odd prime, a ∈ Z, then ap equals 0, if p|a; 1 if a of two squares iff p ≡ 1 (mod 4). A product of two sums of two squares is a sum
p−1
is a quadratic residue modulo p; and −1 otherwise. Euler’s criterion: ap = a( 2 ) of two squares. Thus, n is a sum of two squares iff every prime of form p = 4k + 3
occurs an even number of times in n’s factorization.
(mod p).
Qk ki RSA. Let p and q be random distinct large primes, n = pq. Choose a small odd
Jacobi symbol. If n = pa1 1 · · · pakk is odd, then a a

n = i=1 pi . integer e, relatively prime to φ(n) = (p − 1)(q − 1), and let d = e−1 (mod φ(n)).
Primitive roots. If the order of g modulo m (min n > 0: g ≡ 1 (mod m)) n Pairs (e, n) and (d, n) are the public and secret keys, respectively. Encryption is
is φ(m), then g is called a primitive root. If Zm has a primitive root, then it has done by raising a message M ∈ Zn to the power e or d, modulo n.
φ(φ(m)) distinct primitive roots. Zm has a primitive root iff m is one of 2, 4, pk ,
2pk , where p is an odd prime. If Zm has a primitive root g, then for all a coprime to
m, there exists unique integer i = indg (a) modulo φ(m), such that g i ≡ a (mod m). String Algorithms
indg (a) has logarithm-like properties: ind(1) = 0, ind(ab) = ind(a) + ind(b). Burrows-Wheeler inverse transform. Let B[1..n] be the input (last column of
If p is prime and a is not divisible by p, then congruence xn ≡ a (mod p) has sorted matrix of string’s rotations.) Get the first column, A[1..n], by sorting B.
gcd(n, p − 1) solutions if a(p−1)/ gcd(n,p−1) ≡ 1 (mod p), and no solutions otherwise. For each k-th occurence of a character c at index i in A, let next[i] be the index
(Proof sketch: let g be a primitive root, and g i ≡ a (mod p), g u ≡ x (mod p). of corresponding k-th occurence of c in B. The r-th fow of the matrix is A[r],
xn ≡ a (mod p) iff g nu ≡ g i (mod p) iff nu ≡ i (mod p).) A[next[r]], A[next[next[r]]], ...
Discrete logarithm problem. Find x from ax ≡ b (mod m). Can√be solved Huffman’s algorithm. Start with a forest, consisting of isolated vertices.
√ Repeatedly merge two trees with the lowest weights.
in O( m) time and space with a meet-in-the-middle trick. Let n = d me, and
47

x = ny − z. Equation becomes any ≡ baz (mod m). Precompute all values that
the RHS can take for z = 0, 1, . . . , n − 1, and brute force y on the LHS, each time
checking whether there’s a corresponding value for RHS.
Graph Theory
Pythagorean triples. Integer solutions of x2 + y 2 = z 2 All relatively prime Euler’s theorem. For any planar graph, V − E + F = 1 + C, where V is the
triples are given by: x = 2mn, y = m2 −n2 , z = m2 +n2 where m > n, gcd(m, n) = 1 number of graph’s vertices, E is the number of edges, F is the number of faces in
and m 6≡ n (mod 2). All other triples are multiples of these. Equation x2 +y 2 = 2z 2 graph’s planar drawing, and C is the number of connected components. Corollary:
is equivalent to ( x+y 2 x−y 2 2 V − E + F = 2 for a 3D polyhedron.
2 ) +( 2 ) =z .
Vertex covers and independent sets. Let M , C, I be a max matching, a
ˆ Given an arbitrary pair of integers m and n with m > n > 0: min vertex cover, and a max independent set. Then |M | ≤ |C| = N − |I|, with
a = m2 − n2 , b = 2mn, c = m2 + n2 equality for bipartite graphs. Complement of an MVC is always a MIS, and vice
versa. Given a bipartite graph with partitions (A, B), build a network: connect
ˆ The triple generated by Euclid’s formula is primitive if and only if m and n source to A, and B to sink with edges of capacities, equal to the corresponding
are coprime and not both odd. nodes’ weights, or 1 in the unweighted case. Set capacities of the original graph’s
ˆ To generate all Pythagorean triples uniquely: edges to the infinity. Let (S, T ) be a minimum s-t cut. Then a maximum(-weighted)
a = k(m2 − n2 ), b = k(2mn), c = k(m2 + n2 ) independent set is I = (A ∩ S) ∪ (B ∩ T ), and a minimum(-weighted) vertex cover
is C = (A ∩ T ) ∪ (B ∩ S).
ˆ If m and n are two odd integer such that m > n, then: Matrix-tree theorem. Let matrix T = [tij ], where tij is the number of mul-
2 2 2 2
a = mn, b = m −n2 , c = m 2+n tiedges between i and j, for i 6= j, and tii = −degi . Number of spanning trees of
a graph is equal to the determinant of a matrix obtained by deleting any k-th row
ˆ If n = 1 or 2 there are no solutions. Otherwise and k-th column from T .
2 2
n is even: (( n4 − 1)2 + n2 = ( n4 + 1)2 ) Euler tours. Euler tour in an undirected graph exists iff the graph is con-
2 2
n is odd: (( n 2−1 )2 + n2 = ( n 2+1 )2 ) nected and each vertex has an even degree. Euler tour in a directed graph exists
Prufer code of a tree. Label vertices with integers 1 to n. Repeatedly re-
iff in-degree of each vertex equals its out-degree, and underlying undirected graph move the leaf with the smallest label, and output its only neighbor’s label, until
is connected. Construction: only one edge remains. The sequence has length n − 2. Two isomorphic trees have
doit(u):
the same sequence, and every sequence of integers from 1 and n corresponds to a
for each edge e = (u, v) in E, do: erase e, doit(v)
tree. Corollary: the number of labelled trees with n vertices is nn−2 .
prepend u to the list of vertices in the tour
Erdos-Gallai theorem. A sequence of integers {d1 , d2 , . . . , dn }, with n − 1 ≥
Stable marriages problem. While there is a free man m: let w be the most-
P d2 ≥ · · · ≥ dn ≥ 0 is a degree sequence
d1 ≥ Pn of some undirected simple graph iff
preferred woman to whom he has not yet proposed, and propose m to w. If w is di is even and d1 +· · ·+dk ≤ k(k−1)+ i=k+1 min(k, di ) for all k = 1, 2, . . . , n−1.
free, or is engaged to someone whom she prefers less than m, match m with w, else
deny proposal.
Stoer-Wagner’s min-cut algorithm. Start from a set A containing an ar- Games
bitrary vertex.
P While A 6= V , add to A the most tightly connected vertex (z ∈
/A Grundy numbers. For a two-player, normal-play (last to move wins) game on a
such that x∈A w(x, z) is maximized.) Store cut-of-the-phase (the cut between the graph (V, E): G(x) = mex({G(y) : (x, y) ∈ E}), where mex(S) = min{n ≥ 0 : n 6∈
last added vertex and rest of the graph), and merge the two vertices added last. S}. x is losing iff G(x) = 0.
Repeat until the graph is contracted to a single vertex. Minimum cut is one of the Sums of games.
cuts-of-the-phase. ˆ Player chooses a game and makes a move in it. Grundy number of a position
Tarjan’s offline LCA algorithm. (Based on DFS and union-find structure.) is xor of grundy numbers of positions in summed games.

DFS(x): ˆ Player chooses a non-empty subset of games (possibly, all) and makes moves
ancestor[Find(x)] = x in all of them. A position is losing iff each game is in a losing position.
for all children y of x:
ˆ Player chooses a proper subset of games (not empty and not all), and makes
48

DFS(y); Union(x, y); ancestor[Find(x)] = x

seen[x] = true moves in all chosen ones. A position is losing iff grundy numbers of all games
for all queries {x, y}: are equal.
if seen[y] then output "LCA(x, y) is ancestor[Find(y)]"
ˆ Player must move in all games, and loses if can’t move in some game. A
Strongly-connected components. Kosaraju’s algorithm. position is losing if any of the games is in a losing position.
1. Let GT be a transpose G (graph with reversed edges.) Misère Nim. A position with pile sizes a1 , a2 , . . . , an ≥ 1, not all equal to 1,
1. Call DFS(GT ) to compute finishing times f [u] for each vertex u. is losing iff a1 ⊕ a2 ⊕ · · · ⊕ an = 0 (like in normal nim.) A position with n piles of
3. For each vertex u, in the order of decreasing f [u], perform DFS(G, u). size 1 is losing iff n is odd.
4. Each tree in the 3rd step’s DFS forest is a separate SCC.
2-SAT. Build an implication graph with 2 vertices for each variable – for the
variable and its inverse; for each clause x ∨ y add edges (x, y) and (y, x). The Bit tricks
formula is satisfiable iff x and x are in distinct SCCs, for all x. To find a satisfiable Clearing the lowest 1 bit: x & (x - 1), all trailing 1’s: x & (x + 1)
assignment, consider the graph’s SCCs in topological order from sinks to sources Setting the lowest 0 bit: x | (x + 1)
(i.e. Kosaraju’s last step), assigning ‘true’ to all variables of the current SCC (if it Enumerating subsets of a bitmask m:
hasn’t been previously assigned ‘false’), and ‘false’ to all inverses. x=0; do { ...; x=(x+1+˜m)&m; } while (x!=0);
Randomized algorithm for non-bipartite matching. Let G be a sim- __builtin_ctz/__builtin_clz returns the number of trailing/leading zero
ple undirected graph with even |V (G)|. Build a matrix A, which for each edge bits.
(u, v) ∈ E(G) has Ai,j = xi,j , Aj,i = −xi,j , and is zero elsewhere. Tutte’s theorem: __builtin_popcount(unsigned x) counts 1-bits (slower than table lookups).
G has a perfect matching iff det G (a multivariate polynomial) is identically zero. For 64-bit unsigned integer type, use the suffix ‘ll’, i.e. __builtin_popcountll.
Testing the latter can be done by computing the determinant for a few random XOR Let’s say F(L,R) is XOR of subarray from L to R.
values of xi,j ’s over some field. (e.g. Zp for a sufficiently large prime p) Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1)
Math √
Great circle distance or geographical distance
Stirling’s approximation z! = Γ(z + 1) = 2π z z+1/2 e−z (1 + 1
+ 1
−
139
12z 288z 2 ˆ d = great distance, φ = latitude, λ = longitude, ∆ = difference (all the values
51840z 3 + . . . ) in radians)
2 n
(x−a)
Taylor series. f (x) = f (a)+ x−a 0
1! f (a)+ 2! f (2) (a)+· · ·+ (x−a)
n! f (n) (a)+. . . .
x3 x5 x7
sin x = x − 3! + 5! − 7! + . . . ˆ σ = central angle, angle form for the two vector
3 5
ln x = 2(a + a3 + a5 + . . . ), where a = x−1 2 q
x+1 . ln x = 2 ln x. ˆ d = r ∗ σ, σ = 2 ∗ arcsin( sin2 ( ∆φ 2 ∆λ
3 5 7 2 ) + cos(φ1 ) cos(φ2 ) sin ( 2 ))
arctan x = x − x3 + x5 − x7 + . . . , arctan x = arctan c + arctan 1+xc
x−c
(e.g c=.2)
π = 4 arctan 1, π = 6 arcsin 21 Theorems
Fibonacci Period Si p es primo , π(pk ) = pk−1 π(p)
ˆ There is always a prime between numbers n2 and (n + 1)2 , where n is any
π(2) = 3 π(5) = 20
positive integer
Si n y m son coprimos π(n ∗ m) = lcm(π(n), π(m))
List of Primes ˆ There is an infinite number of pairs of the from {p, p + 2} where both p and
1e5 3 19 43 49 57 69 103 109 129 151 153 p + 2 are primes.
1e6 33 37 39 81 99 117 121 133 171 183
1e7 19 79 103 121 139 141 169 189 223 229 ˆ Every even integer greater than 2 can be expressed as the sum of two primes.
1e8 7 39 49 73 81 123 127 183 213
2-SAT Rules ˆ Every integer greater than 2 can be written as the sum of three primes.
p → q ≡ ¬p ∨ q
ˆ ad ≡ ad mod φ(n) mod n
p → q ≡ ¬q → ¬p
if a ∈ Zn∗ or a ∈
/ Zn∗ and d mod φ(n) 6= 0
p ∨ q ≡ ¬p → q
49

p ∧ q ≡ ¬(p → ¬q) ˆ ad ≡ aφ(n) mod n

¬(p → q) ≡ p ∧ ¬q / Zn∗ and d mod φ(n) = 0
if a ∈
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → q) ∨ (p → r) ≡ p → (q ∨ r) ˆ thus, for all a, n and d (with d ≥ log2 (n))
(p → r) ∧ (q → r) ≡ (p ∧ q) → r ad ≡ aφ(n)+d mod φ(n) mod n
(p → r) ∨ (q → r) ≡ (p ∨ q) → r
(p ∧ q) ∨ (r ∧ s) ≡ (p ∨ r) ∧ (p ∨ s) ∧ (q ∨ r) ∧ (q ∨ s) Law of sines and cosines
ˆ a, b, c: lenghts, A, B, C: opposite angles, d: circumcircle
Summations
Pn 2 n(n+1)(2n+1) ˆ a
= b
= c
=d
ˆ i=1 i = 6
sin(A) sin(B) sin(C)

Pn 3 n(n+1) 2 ˆ c2 = a2 + b2 − 2ab cos(C)

ˆ i=1 i = ( 2 )
Pn 4 n(n+1)(2n+1)(3n2 +3n−1)
Heron’s Formula
ˆ i=1 i = 30
ˆ s= a+b+c
2
Pn 5 (n(n+1))2 (2n2 +2n−1)
ˆ i=1 i = 12
ˆ Area =
p
Pn n+1
s(s − a)(s − b)(s − c)
ˆ i
i=0 x =
x
x−1
−1
para x 6= 1
ˆ a, b, c there are the lenghts of the sides
Compound Interest
Legendre’s Formula Largest power of k, x, such that n! is divisible by k x
ˆ N is the initial population, it grows at a rate of R. So, after X years the
popularion will be N × (1 + R)X ˆ If k is prime, x = n
k + n
k2 + n
k3 + ...
Qm
ˆ If k is composite k = k1p1 ∗ k2p2 . . . km
pm
ˆ Number of divisors of n! The answer is j=1 (ej + 1)
aj
x = min1≤j≤m { pj } where aj is Legendre’s formula for kj
e +1
Qm pj j −1
ˆ Divisor Formulas of n! Find all prime numbers ≤ n {p1 , . . . , pm } Let’s define ˆ Sum of divisors of n! The answer is j=1 ej −1
ej as Legendre’s formula for pj
50