Glossary

Every concept in this sheet, plus the smaller terms it uses. Select a concept to open its card.

Binary exponentiation: Computing a^e in O(log e) multiplications by squaring the base and multiplying it in whenever the current bit of e is set.
Binomial coefficients mod p: Precompute factorials and inverse factorials up to the largest n once, then each n choose r is three multiplications.

Compiler flags and sanitizers: Compile with warnings on for normal runs, and with sanitizers and the debug STL while hunting a bug, so out-of-range indexes and overflow stop the program with a message.
Complexity vs n table: A rule of thumb that maps the input limit n to the slowest complexity that fits a typical one or two second time limit, assuming a judge runs very roughly 10^8 simple operations per second.
Contest template: The short file you start every problem from: one header that pulls in the whole standard library, a long long alias, fast input and output, and a loop over test cases.

Fast input and output: Two lines that stop cin and cout synchronising with C input and output and flushing each other, plus printing a newline character instead of endl, which flushes on every line.

GCD and LCM: The greatest common divisor is the largest number dividing both values, found by Euclid's algorithm in O(log n).

Integer overflow and long long: An int holds values up to about 2.1 * 10^9, and a long long up to about 9.2 * 10^18.

Modular arithmetic: Working with remainders after division by a fixed number, usually 10^9 + 7 or 998244353.
Modular inverse: The number b^-1 such that b * b^-1 leaves remainder 1.

Parity and invariants: An invariant is a quantity an allowed operation never changes, such as the parity of a sum or the gcd of an array.
priority_queue: A heap that always gives the largest element in O(1) and inserts or removes in O(log n).

set, map and multiset: Sorted containers built on a balanced binary search tree, with O(log n) insert, erase and search, and lower_bound to find the first element not below a value.
Sieve of Eratosthenes: Marks every multiple of each prime as composite, finding all primes up to n in O(n log log n).
Sorting with a comparator: Passing a function to sort that returns true when the first element must come before the second, usually written as a lambda.
STL algorithms toolkit: Ready-made functions in the standard library for sorting, removing duplicates, summing, finding extremes and walking through permutations.

Trial division and divisors: Divide x by every candidate p while p * p <= x.

vector, pair and tuple: A vector is a resizable array with O(1) index access and amortised O(1) push_back.