i. Modular Arithmetic

Work in ${\mathbb{Z}}_m$: $a\equiv b(\mathrm{mod}m)⟺m\mid a-b$. Addition, subtraction and multiplication commute with reduction; division by $b$ means multiplying by $b^{-1}$, which exists iff $\gcd (b,m)=1$. For a prime $p$, ${\mathbb{Z}}_p$ is a field and $b^{-1}=b^{p-2}$. GCD, CRT and linear congruences are in Congruences and CRT; Barrett / Montgomery reduction in Fast Modular Multiplication.

A modint

template <int MOD> struct Mint {                          // MOD prime (inv uses Fermat)
    int v = 0;
    Mint() {}
    Mint(ll x) { v = int(x % MOD); if (v < 0) v += MOD; }
    Mint& operator+=(Mint o) { if ((v += o.v) >= MOD) v -= MOD; return *this; }
    Mint& operator-=(Mint o) { if ((v -= o.v) < 0) v += MOD; return *this; }
    Mint& operator*=(Mint o) { v = int((ll)v * o.v % MOD); return *this; }
    Mint& operator/=(Mint o) { return *this *= o.inv(); }
    Mint pow(ll e) const { Mint r = 1, b = *this; for (; e; e >>= 1, b *= b) if (e & 1) r *= b; return r; }
    Mint inv() const { return pow(MOD - 2); }
    friend Mint operator+(Mint a, Mint b) { return a += b; }
    friend Mint operator-(Mint a, Mint b) { return a -= b; }
    friend Mint operator*(Mint a, Mint b) { return a *= b; }
    friend Mint operator/(Mint a, Mint b) { return a /= b; }
    Mint operator-() const { return Mint() - *this; }
    friend bool operator==(Mint a, Mint b) { return a.v == b.v; }
    friend bool operator!=(Mint a, Mint b) { return a.v != b.v; }
    friend ostream& operator<<(ostream& os, Mint a) { return os << a.v; }
};
using mint = Mint<998244353>;
struct Comb {                                             // factorials up to n, O(1) binomials
    vector<mint> f, fi, iv;
    Comb(int n) : f(n + 1), fi(n + 1), iv(n + 1) {
        f[0] = 1; for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i;
        fi[n] = f[n].inv(); for (int i = n; i > 0; i--) fi[i - 1] = fi[i] * i;
        for (int i = 1; i <= n; i++) iv[i] = fi[i] * f[i - 1];   // 1 / i
    }
    mint C(int n, int k) const { return k < 0 || k > n ? 0 : f[n] * fi[k] * fi[n - k]; }
    mint P(int n, int k) const { return k < 0 || k > n ? 0 : f[n] * fi[n - k]; }
};

Rule	Detail
negative remainders	C++ % keeps the sign of the dividend: use ((a % m) + m) % m
products	(ll)a * b % m for $m<2^{31}$; (__int128)a * b % m up to $2^{63}$
exponents	$a^n\equiv a^{n\mathrm{mod}(p-1)}$ for $p\nmid a$; for composite $m$ see Euler / power towers (Number Theory Miscellany)
comparisons / ordering	meaningless after reduction: compare before reducing, or use exact arithmetic
fractions in answers	”output $P\cdot Q^{-1}\mathrm{mod}p$”: keep everything as mint
equal answers	equality mod $p$ of results is evidence, not proof (random-prime hashing of exact values)

Binary exponentiation, Fermat and Euler

ll power(ll a, ll e, ll m) { ll r = 1 % m; a %= m; if (a < 0) a += m; for (; e; e >>= 1, a = (__int128)a * a % m) if (e & 1) r = (__int128)r * a % m; return r; }
ll mulSlow(ll a, ll b, ll m) { ll r = 0; a %= m; for (; b; b >>= 1, a = (a + a) % m) if (b & 1) r = (r + a) % m; return r; }   // no __int128

The same loop works in any monoid: matrices (linear recurrences), permutations (${\sigma }^k$), affine maps, the “apply $f$ $k$ times” doubling of functional graphs.

Proof: binary exponentiation, Fermat's little theorem, Euler's theorem

Exponentiation: with $e={\sum }_k{b}_k{2}^k$, $a^e={\prod }_{k:b_k=1}{a}^{2^k}$; the loop keeps $a$ equal to the original $a^{2^k}$ at step $k$ and multiplies it in exactly when bit $k$ is set: $O(\log e)$ multiplications, valid in any associative structure.

Euler: let $R$ be the $\phi (m)$ residues coprime to $m$. If $\gcd (a,m)=1$, multiplication by $a$ permutes $R$ (it maps $R$ into $R$, and is injective because $a$ is invertible). Hence ${\prod }_{r\in R}r\equiv {\prod }_{r\in R}ar=a^{\phi (m)}{\prod }_{r\in R}r$, and cancelling the invertible product gives $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$. Fermat is the case $m=p$ prime, $\phi (p)=p-1$, so $a^{-1}\equiv a^{p-2}$ and exponents reduce modulo $p-1$.

Inverses in bulk

vector<ll> inversesUpTo(int n, ll p) {                    // inv[i] for 1 <= i <= n < p, O(n)
    vector<ll> inv(n + 1, 1);
    for (int i = 2; i <= n; i++) inv[i] = (p - (p / i) * inv[p % i] % p) % p;
    return inv;
}
vector<mint> batchInverse(const vector<mint>& a) {        // all a[i]^{-1} with one exponentiation (a[i] != 0)
    int n = sz(a); vector<mint> pre(n + 1, 1), res(n);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] * a[i];
    mint suf = pre[n].inv();                              // = (a_0 ... a_{n-1})^{-1}
    for (int i = n - 1; i >= 0; i--) res[i] = suf * pre[i], suf *= a[i];
    return res;
}

Proof: the two inverse tricks, and inverse factorials

Linear inverses: $p=\lfloor p/i\rfloor i+(p\mathrm{mod}i)$, so $\lfloor p/i\rfloor i+(p\mathrm{mod}i)\equiv 0$; multiplying by $i^{-1}(p\mathrm{mod}i{)}^{-1}$ gives $i^{-1}\equiv -\lfloor p/i\rfloor (p\mathrm{mod}i{)}^{-1}$, and $p\mathrm{mod}i<i$ was computed earlier ($p\mathrm{mod}i\ne 0$ since $i<p$). Batch: before processing index $i$, suf $=(a_0\cdots a_i{)}^{-1}$, so suf * pre[i] $=a_i^{-1}$; multiplying by $a_i$ moves to $(a_0\cdots a_{i-1}{)}^{-1}$. Factorials: $\frac{1}{(i-1)!}=\frac{i}{i!}$ fills the inverse factorials downward from one inversion, and $\frac{1}{i}=\frac{(i-1)!}{i!}$.

Integer pitfalls

ll floorDiv(ll a, ll b) { return a / b - ((a % b != 0) && ((a < 0) != (b < 0))); }   // any signs, b != 0
ll ceilDiv(ll a, ll b) { return a / b + ((a % b != 0) && ((a < 0) == (b < 0))); }
bool mulOverflows(ll a, ll b) { ll c; return __builtin_mul_overflow(a, b, &c); }

C++ division truncates toward zero, so floor and ceiling differ from / exactly when the remainder is nonzero and the signs differ (floor) or agree (ceiling). Check products against a bound with __builtin_mul_overflow or a > lim / b instead of multiplying first.

Signed/unsigned comparison

Comparing int against unsigned (or size_t) silently converts the signed value to unsigned first — a negative int becomes a huge positive number, so -1 < sz(v) can be false. Cast explicitly, or keep indices signed throughout (the sz() macro exists for exactly this).

Unusual number representations

Negative base $-b$: every integer has a unique representation with digits $\mathrm{0..}b-1$ and no sign. Balanced ternary: digits $-1,0,1$ with weights $3^k$ (weighing with weights on both pans). A Trygub number stores a huge binary integer as a sparse map of signed base-$2^{30}$ digits, supporting “add $\pm x\cdot 2^e$” in amortized $O(\log )$ and reading any bit or the sign.

string toNegativeBase(ll x, int b) {                       // base -b, b >= 2
    if (x == 0) return "0";
    string s; while (x != 0) { ll r = ((x % b) + b) % b; s.push_back(char('0' + r)); x = (x - r) / -b; }
    reverse(all(s)); return s;
}
ll fromNegativeBase(const string& s, int b) { ll r = 0; for (char c : s) r = r * -b + (c - '0'); return r; }
string toBalancedTernary(ll x) {                           // digits '-', '0', '+'
    if (x == 0) return "0";
    string s;
    while (x != 0) { int r = int(((x % 3) + 3) % 3); if (r == 2) s += '-', x = (x + 1) / 3; else s += r ? '+' : '0', x = (x - r) / 3; }
    reverse(all(s)); return s;
}
ll fromBalancedTernary(const string& s) { ll x = 0; for (char c : s) x = x * 3 + (c == '+') - (c == '-'); return x; }
struct TrygubNumber {                                      // value = sum digits[k] * 2^(30k), digits in (-2^30, 2^30)
    static constexpr int K = 30; static constexpr ll BASE = 1LL << K;
    map<int, ll> d;
    void add(ll x, int e) {                                // += x * 2^e, |x| < 2^31, e >= 0
        x *= 1LL << (e % K);
        for (int blk = e / K; x != 0; blk++) { ll& v = d[blk]; v += x; x = v / BASE; v -= x * BASE; if (v == 0) d.erase(blk); }
    }
    int sign() const { return d.empty() ? 0 : d.rbegin()->second > 0 ? 1 : -1; }
    int bit(int k) const {                                 // k-th bit of a non-negative value
        int blk = k / K; auto it = d.lower_bound(blk);
        ll v = it != d.end() && it->first == blk ? it->second : 0;
        if (it != d.begin() && prev(it)->second < 0) v--;  // borrow from the lower blocks
        v = ((v % BASE) + BASE) % BASE; return int(v >> (k % K) & 1);
    }
};

Proof: negative base, balanced ternary, and Trygub numbers

Negative base: at each step $r\equiv x(\mathrm{mod}b)$ is forced (the last digit), and $(x-r)/(-b)$ is an integer; the absolute value shrinks for $|x|>1$ ($|x-r|\le |x|+b-1$, divided by $b$), and from $|x|\le 1$ the next steps end in 0, so the loop terminates; uniqueness follows because the last digit is forced at every step. Balanced ternary: the same argument with digits $\{-1,0,1\}$ representing the residues $\{2,0,1\}$. Trygub: after each carry step the digit lies in $(-\text{BASE},\text{BASE})$; the value of a block’s bits equals its digit minus one if the nearest lower nonzero digit is negative (that negative tail borrows exactly one unit from this block, since a nonzero tail of digits with magnitude $<\text{BASE}$ has absolute value below one block unit), and the sign of the whole number is the sign of its highest nonzero digit for the same reason. Cost: after the first two blocks every carry has magnitude at most 2, so a chain only continues through a block whose digit was within 2 of $\pm \text{BASE}$, and it leaves that digit with magnitude at most 2. With the potential “number of blocks whose digit is within 2 of $\pm \text{BASE}$”, each step of a long chain lowers the potential and each add raises it by $O(1)$, so carries are amortized $O(1)$ per add, each costing a map operation.

Sums worth knowing

Sum	Value
${\sum }_{i=1}^{n}i$, $\sum i^2$, $\sum i^3$	$\frac{n(n+1)}{2}$, $\frac{n(n+1)(2n+1)}{6}$, $(\frac{n(n+1)}{2}{)}^2$
${\sum }_{i=0}^n{r}^i$	$\frac{r^{n+1}-1}{r-1}$ ($r\ne 1$); mod $p$ when $r\equiv 1$ the sum is $n+1$
${\sum }_{i=1}^n\lfloor n/i\rfloor$	$\le n{H}_n=n\ln n+O(n)$: “loop over multiples” is $O(n\log n)$
$H_n$	$\ln n+\gamma +O(1/n)$, $\gamma \approx 0.5772$
${\sum }_{p\le n}1/p$	$\ln \ln n+O(1)$: the sieve of Eratosthenes is $O(n\log \log n)$
$n!$, $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$	$\sim \sqrt{2\pi n}(n/e{)}^n$, $\sim 4^n/\sqrt{\pi n}$
$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$	$\le (en/k{)}^k$
general ${\sum }_i{i}^k$	Faulhaber / Bernoulli or Lagrange interpolation

Proof: the elementary sums and bounds

The power sums follow by induction (or telescoping $(i+1{)}^{k+1}-i^{k+1}$); the geometric sum by $(r-1)\sum r^i=r^{n+1}-1$. Harmonic: ${\int }_i^{i+1}\frac{dx}{x}\le \frac{1}{i}\le {\int }_{i-1}^i\frac{dx}{x}$, so $\ln (n+1)\le H_n\le 1+\ln n$, hence $\sum \lfloor n/i\rfloor \le n{H}_n=O(n\log n)$; the constant $\gamma$ is the limit of the decreasing, bounded sequence $H_n-\ln n$. Binomial bound: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le \frac{n^k}{k!}$ and $k!\ge (k/e{)}^k$ since $e^k={\sum }_j{k}^j/j!\ge k^k/k!$. The prime-reciprocal and Stirling asymptotics are classical analytic estimates (Mertens, Stirling); only their orders of growth are used in complexity arguments.