Appendix: CP Quick Reference

Python CP Template

import sys
import os
from collections import defaultdict, Counter, deque
from heapq import heappush, heappop, heapify, nlargest, nsmallest
from bisect import bisect_left, bisect_right, insort
from functools import cache, lru_cache, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from math import gcd, lcm, isqrt, log2, ceil, floor, inf
from typing import Optional

input = sys.stdin.readline
MOD = 10**9 + 7

def solve():
    pass

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()

---

Common Number Theory Snippets

# GCD / LCM
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)

# Modular exponentiation — built-in pow(base, exp, mod)
pow(2, 100, MOD)   # fast; use this instead of ** % MOD

# Sieve of Eratosthenes
def sieve(n: int) -> list[bool]:
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, isqrt(n) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return is_prime

# Modular inverse (when MOD is prime)
def modinv(a: int, mod: int = MOD) -> int:
    return pow(a, mod - 2, mod)

# nCr mod p
def nCr(n: int, r: int, mod: int = MOD) -> int:
    if r > n: return 0
    num = den = 1
    for i in range(r):
        num = num * (n - i) % mod
        den = den * (i + 1) % mod
    return num * pow(den, mod - 2, mod) % mod

---

Complexity Decision Tree

Input size n:
  n ≤ 12          → O(n!) — backtracking / permutations
  n ≤ 25          → O(2^n) — bitmask / meet in the middle
  n ≤ 500         → O(n³) — Floyd-Warshall, cubic DP
  n ≤ 5000        → O(n²) — quadratic DP, nested loops
  n ≤ 10^5–10^6   → O(n log n) — sort, heap, segment tree, BIT
  n ≤ 10^7–10^8   → O(n) — linear scan, prefix sum, hashing
  n ≤ 10^18       → O(log n) — binary search, fast exponentiation

---

End of Python DSA Course Book — August 2026