Short, verified implementations worth having ready. Each links to the page that explains it — paste from here, understand from there.
Modular arithmetic
const ll MOD = 1e9 + 7;
ll pw(ll b, ll e, ll m = MOD) {
ll r = 1; b %= m;
while (e) { if (e & 1) r = r * b % m; b = b * b % m; e >>= 1; }
return r;
}
ll inv(ll a, ll m = MOD) { return pw(a, m - 2, m); } // m primepw is binary exponentiation; inv uses Fermat and requires a prime modulus.
Factorials and binomials
const int N = 1e6 + 5;
ll fact[N], ifact[N];
void initFact() {
fact[0] = 1;
for (int i = 1; i < N; i++) fact[i] = fact[i-1] * i % MOD;
ifact[N-1] = inv(fact[N-1]);
for (int i = N-1; i > 0; i--) ifact[i-1] = ifact[i] * i % MOD;
}
ll C(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * ifact[r] % MOD * ifact[n-r] % MOD;
}One modular inverse for the whole table — the backward loop derives the rest. See Binomial Coefficients.
DSU
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a; sz[a] += sz[b];
return true;
}
};Path compression plus union by size gives amortised. See DSU.
Fenwick tree
struct BIT {
int n; vector<ll> t;
BIT(int n) : n(n), t(n + 1, 0) {}
void add(int i, ll v) { for (++i; i <= n; i += i & -i) t[i] += v; }
ll sum(int i) { ll s = 0; for (++i; i > 0; i -= i & -i) s += t[i]; return s; }
ll sum(int l, int r) { return sum(r) - (l ? sum(l - 1) : 0); }
};Six lines, , and a far better constant than a segment tree. See Fenwick Tree.
Iterative segment tree
struct SegTree {
int n; vector<ll> t;
SegTree(int n) : n(n), t(2 * n, 0) {}
void set(int i, ll v) { for (t[i += n] = v; i > 1; i >>= 1) t[i>>1] = t[i] + t[i^1]; }
ll query(int l, int r) { // [l, r)
ll res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += t[l++];
if (r & 1) res += t[--r];
}
return res;
}
};Non-recursive, no lazy propagation, and about twice as fast as the recursive form. For range updates use lazy propagation.
Sieve with smallest prime factor
const int MX = 1e6 + 5;
int spf[MX];
void sieve() {
for (int i = 2; i < MX; i++) if (!spf[i])
for (int j = i; j < MX; j += i) if (!spf[j]) spf[j] = i;
}
vector<int> factorize(int x) {
vector<int> f;
while (x > 1) { f.push_back(spf[x]); x /= spf[x]; }
return f;
}Storing the smallest prime factor makes every later factorisation . See Sieve.
Matrix exponentiation
using Mat = array<array<ll,K>,K>;
Mat mul(const Mat& a, const Mat& b) {
Mat c{};
for (int i = 0; i < K; i++)
for (int k = 0; k < K; k++) if (a[i][k])
for (int j = 0; j < K; j++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
return c;
}The if (a[i][k]) guard and the i-k-j loop order are both worth keeping: the order is cache-friendly, the guard skips whole inner loops on sparse matrices. See Matrix Exponentiation.
Geometry point
using T = long long; // exact when coordinates are integral
struct P {
T x, y;
P operator+(P o) const { return {x + o.x, y + o.y}; }
P operator-(P o) const { return {x - o.x, y - o.y}; }
T cross(P o) const { return x * o.y - y * o.x; }
T dot(P o) const { return x * o.x + y * o.y; }
T norm2() const { return x * x + y * y; }
};
int sgn(T v) { return (v > 0) - (v < 0); }
int orient(P a, P b, P c) { return sgn((b - a).cross(c - a)); }Keep coordinates integral wherever possible. Every geometry bug you will not have comes from avoiding floating point; orient is exact with long long. See Geometry Primitives.
String hashing
struct Hash {
static const ll M = (1LL << 61) - 1; // Mersenne prime
vector<ll> h, p;
Hash(const string& s, ll base) : h(s.size() + 1, 0), p(s.size() + 1, 1) {
for (size_t i = 0; i < s.size(); i++) {
h[i+1] = (__int128)h[i] * base % M + s[i]; if (h[i+1] >= M) h[i+1] -= M;
p[i+1] = (__int128)p[i] * base % M;
}
}
ll get(int l, int r) { // [l, r)
ll v = h[r] - (__int128)h[l] * p[r-l] % M;
return v < 0 ? v + M : v;
}
};Use a random base chosen at runtime and the modulus ; a fixed base with a modulus is routinely hacked. See String Hashing.
Coordinate compression
vector<int> vals(a);
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for (int& x : a) x = lower_bound(all(vals), x) - vals.begin();Four lines that turn any values into indices — the prerequisite for most array-indexed structures.
Ordered set (PBDS)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// s.order_of_key(x) -> number of elements < x
// *s.find_by_order(k) -> the k-th smallestGCC-only, but available on Codeforces and AtCoder. See Ordered Set.
Custom hash for unordered_map
struct chash {
static ull splitmix64(ull x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(ull x) const {
static const ull FIXED = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED);
}
};
gp_hash_table<ll, int, chash> mp;The default std::hash<int> is the identity, which makes unordered_map trivially hackable to per operation. This is not paranoia — it is a routine hack on Codeforces.
Verifying these
Every snippet here should be run once against Library Checker or an equivalent problem before a contest, not during one. A structure you have never submitted is not part of your library.
See also: Data Structure Catalog · Contest Template · Named Algorithms