Math And Combinatorics

Math and Combinatorics Patterns

Mathematical and combinatorial problems appear frequently in competitive programming and algorithm design. They often hide behind constraints that look like brute-force problems but require algebraic shortcuts to meet time limits. This reference covers eight core pattern families with recognition signals, templates, and pitfalls.

Pattern Recognition Table

Constraint-to-Technique Mapping

• N up to 10^7 and asks about primes: Sieve of Eratosthenes.
• N up to 10^6 and asks "how many ways": Precomputed factorials + modular inverse for nCr.
• "modulo 10^9+7" anywhere in the problem: Modular arithmetic throughout; use modular inverse for division.
• Two players, finite game, no randomness: Sprague-Grundy theorem or direct DP on game states.
• "count subsets satisfying property" with small constraint count (k <= 20): Inclusion-exclusion over 2^k subsets.
• Linear recurrence with large N (10^18): Matrix exponentiation to compute nth term in O(k^3 log N).
• "distribute N items into K groups": Stars and bars, possibly combined with inclusion-exclusion for bounded constraints.

Individual Patterns

Modular Arithmetic

Recognition Signals

• Problem says "answer modulo 10^9+7" or any large prime
• Intermediate values overflow 64-bit integers
• Division is required under a modular context
• Counting problem with astronomically large answers

Core Idea

All arithmetic operations (add, subtract, multiply) distribute over modulo. Division under a prime modulus uses modular inverse: a / b mod p = a * b^(p-2) mod p via Fermat's little theorem. Always reduce intermediate results to prevent overflow.

Python Template

MOD = 10**9 + 7

def mod_add(a: int, b: int) -> int:
    return (a + b) % MOD

def mod_mul(a: int, b: int) -> int:
    return (a * b) % MOD

def mod_pow(base: int, exp: int, mod: int = MOD) -> int:
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        exp >>= 1
        base = base * base % mod
    return result

def mod_inv(a: int, mod: int = MOD) -> int:
    """Modular inverse via Fermat's little theorem. Requires mod is prime."""
    return mod_pow(a, mod - 2, mod)

def mod_div(a: int, b: int) -> int:
    return mod_mul(a, mod_inv(b))

Key Edge Cases

• Subtraction can go negative: use (a - b + MOD) % MOD
• Zero divisor: mod_inv(0) is undefined; guard against it
• Non-prime modulus: Fermat's theorem does not apply; use extended GCD instead
• Chained multiplications: reduce after every multiply, not just at the end

Common Mistakes

• Forgetting to take mod after subtraction, producing negative values
• Using Fermat's inverse with a composite modulus
• Applying mod to intermediate index calculations where exact values are needed

Sieve of Eratosthenes

Recognition Signals

• "Find all primes up to N" with N up to 10^7
• "Smallest prime factor of every number"
• Need to factorize many numbers efficiently
• "Count of prime factors" across a range

Core Idea

The classic sieve marks composites by iterating through multiples of each prime. The smallest-prime-factor (SPF) variant stores the smallest divisor at each index, enabling O(log N) factorization of any number after an O(N log log N) precompute. For ranges beyond memory, use a segmented sieve.

Python Template

def sieve_primes(n: int) -> list[bool]:
    """Standard boolean sieve. is_prime[i] is True if i is prime."""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return is_prime

def smallest_prime_factor(n: int) -> list[int]:
    """SPF sieve for fast factorization."""
    spf = list(range(n + 1))
    for i in range(2, int(n**0.5) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i * i, n + 1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

def factorize(x: int, spf: list[int]) -> list[int]:
    """Factorize x using precomputed SPF table."""
    factors: list[int] = []
    while x > 1:
        factors.append(spf[x])
        x //= spf[x]
    return factors

Key Edge Cases

• N = 0 or 1: no primes exist; handle boundary
• Memory limit: standard sieve needs O(N) space; switch to segmented sieve above ~10^8
• SPF of 1: not defined; skip or handle separately
• Even numbers: can optimize by treating 2 specially and only sieving odds

Common Mistakes

• Starting inner loop at 2*i instead of i*i (correct but slower)
• Off-by-one on sieve size (allocate n+1 slots)
• Forgetting that sieve[0] and sieve[1] are not prime

GCD / LCM

Recognition Signals

• Problem explicitly mentions GCD or LCM
• "Find the largest number that divides all elements"
• "Smallest number divisible by all elements"
• Equations involving linear combinations of two integers (Bezout's identity)

Core Idea

Euclidean algorithm computes GCD in O(log min(a,b)). LCM derives from GCD: lcm(a,b) = a * b // gcd(a,b). Extended Euclidean finds coefficients x, y such that a*x + b*y = gcd(a,b), which is essential for modular inverse when the modulus is not prime.

Python Template

from math import gcd
from functools import reduce

def lcm(a: int, b: int) -> int:
    return a * b // gcd(a, b)

def lcm_array(arr: list[int]) -> int:
    return reduce(lcm, arr)

def gcd_array(arr: list[int]) -> int:
    return reduce(gcd, arr)

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Returns (g, x, y) such that a*x + b*y = g = gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def mod_inv_ext(a: int, m: int) -> int:
    """Modular inverse via extended GCD. Works for any coprime a, m."""
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f"Inverse does not exist: gcd({a}, {m}) = {g}")
    return x % m

Key Edge Cases

• gcd(0, x) = x and gcd(0, 0) = 0 by convention
• LCM overflow: compute a // gcd(a,b) * b instead of a * b // gcd(a,b)
• Negative inputs: take absolute values before computing
• Extended GCD with b = 0: base case returns (a, 1, 0)

Common Mistakes

• LCM overflow from multiplying before dividing by GCD
• Assuming modular inverse exists when gcd(a, m) != 1
• Recursion depth for very large inputs (Python's default limit); use iterative version if needed

Binomial Coefficients

Recognition Signals

• "How many ways to choose k items from n"
• "nCr mod p" with large n
• Pascal's triangle or binomial theorem mentioned
• Lattice path counting (grid movement problems)

Core Idea

For small n (up to ~10^6), precompute factorials and inverse factorials modulo a prime, then answer nCr queries in O(1). Pascal's triangle DP works for smaller n without modular arithmetic. Lucas' theorem handles nCr mod p when n is very large but p is small.

Python Template

MOD = 10**9 + 7

def precompute_factorials(n: int) -> tuple[list[int], list[int]]:
    """Precompute factorial and inverse factorial arrays mod MOD."""
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    return fact, inv_fact

def nCr(n: int, r: int, fact: list[int], inv_fact: list[int]) -> int:
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD

def lucas(n: int, r: int, p: int) -> int:
    """nCr mod p for small prime p, using Lucas' theorem."""
    if r == 0:
        return 1
    return lucas(n // p, r // p, p) * nCr_small(n % p, r % p, p) % p

def nCr_small(n: int, r: int, p: int) -> int:
    """Direct nCr mod p for n < p."""
    if r < 0 or r > n:
        return 0
    num = den = 1
    for i in range(r):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    return num * pow(den, p - 2, p) % p

Key Edge Cases

• nCr(n, 0) = 1 and nCr(n, n) = 1 for all valid n
• r > n returns 0
• Negative r or n: return 0
• Lucas' theorem only works when p is prime

Common Mistakes

• Off-by-one in precompute size (need n+1 slots)
• Using Lucas' theorem with composite modulus
• Forgetting the r > n guard, causing index-out-of-bounds

Fast Exponentiation

Recognition Signals

• "Compute a^b mod m" with b up to 10^18
• Linear recurrence (Fibonacci-like) with very large n
• "Matrix power" or "transform applied k times"
• State transition repeated billions of times

Core Idea

Binary exponentiation computes a^b mod m in O(log b) by squaring the base and halving the exponent at each step. Matrix exponentiation extends this: represent a linear recurrence as a matrix multiplication, then raise the transition matrix to the nth power. This turns O(n) recurrence evaluation into O(k^3 log n) where k is the matrix dimension.

Python Template

def power(base: int, exp: int, mod: int) -> int:
    """Binary exponentiation: base^exp mod mod."""
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        exp >>= 1
        base = base * base % mod
    return result

Matrix = list[list[int]]

def mat_mul(a: Matrix, b: Matrix, mod: int) -> Matrix:
    """Multiply two square matrices mod mod."""
    n = len(a)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if a[i][k] == 0:
                continue
            for j in range(n):
                result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % mod
    return result

def mat_pow(mat: Matrix, exp: int, mod: int) -> Matrix:
    """Raise a square matrix to exp-th power mod mod."""
    n = len(mat)
    result = [[int(i == j) for j in range(n)] for i in range(n)]
    while exp > 0:
        if exp & 1:
            result = mat_mul(result, mat, mod)
        exp >>= 1
        mat = mat_mul(mat, mat, mod)
    return result

Key Edge Cases

• exp = 0: result is 1 (scalar) or identity matrix
• base = 0 with exp = 0: conventionally 1, but problem-dependent
• Overflow in matrix multiplication: reduce mod at every addition
• Recurrence with more than 2 terms: increase matrix dimension accordingly

Common Mistakes

• Forgetting to handle exp = 0 as a special case
• Not reducing base modulo m before starting (causes unnecessary large intermediate values)
• Using the wrong matrix dimension for the recurrence

Counting Techniques

Recognition Signals

• "How many ways to arrange/distribute/partition"
• "Count sequences satisfying constraints"
• "Stars and bars" or "multiset coefficient"
• Catalan-number patterns: balanced parentheses, binary trees, non-crossing partitions

Core Idea

Permutations count ordered arrangements; combinations count unordered selections. Stars and bars counts ways to distribute n identical items into k distinct bins: C(n+k-1, k-1). Catalan numbers count structures with recursive nesting (nth Catalan = C(2n, n) / (n+1)). Recognize which formula applies by identifying whether order matters and whether items are identical or distinct.

Python Template

MOD = 10**9 + 7

def permutations_mod(n: int, r: int, fact: list[int], inv_fact: list[int]) -> int:
    """P(n, r) = n! / (n-r)! mod MOD."""
    if r < 0 or r > n:
        return 0
    return fact[n] * inv_fact[n - r] % MOD

def stars_and_bars(n: int, k: int, fact: list[int], inv_fact: list[int]) -> int:
    """Distribute n identical items into k distinct bins (each >= 0)."""
    return nCr(n + k - 1, k - 1, fact, inv_fact)

def catalan(n: int, fact: list[int], inv_fact: list[int]) -> int:
    """Nth Catalan number mod MOD."""
    return nCr(2 * n, n, fact, inv_fact) * pow(n + 1, MOD - 2, MOD) % MOD

def multiset_coeff(n: int, k: int, fact: list[int], inv_fact: list[int]) -> int:
    """Choose k items from n types with repetition allowed. Uses nCr from above."""
    return nCr(n + k - 1, k, fact, inv_fact)

Key Edge Cases

• Stars and bars with lower bounds: shift variables (replace x_i with y_i = x_i - lower_i)
• Catalan(0) = 1 by convention
• Empty arrangements: 0 items chosen from n gives 1 way (the empty selection)
• Upper-bounded distributions: combine stars and bars with inclusion-exclusion

Common Mistakes

• Confusing "with repetition" vs "without repetition" in the problem statement
• Applying stars and bars when items are distinct (use multinomial instead)
• Forgetting the n+1 denominator in the Catalan formula

Inclusion-Exclusion

Recognition Signals

• "Count elements satisfying at least one of k properties"
• "Count permutations with no fixed points" (derangements)
• "Count integers in range divisible by at least one of given primes"
• Constraints that are easier to count by complementing

Core Idea

Inclusion-exclusion alternates between adding and subtracting intersection sizes: |A1 union A2 union ... Ak| = sum|Ai| - sum|Ai intersect Aj| + .... This is powerful when direct counting is hard but counting elements with specific properties (or their complements) is easy. Derangements are a classic application: D(n) = n! * sum_{i=0}^{n} (-1)^i / i!.

Python Template

MOD = 10**9 + 7

def inclusion_exclusion(sets_sizes: list[int], intersect_fn) -> int:
    """Generic IE over k sets. intersect_fn(mask) returns |intersection of sets in mask|."""
    k = len(sets_sizes)
    total = 0
    for mask in range(1, 1 << k):
        bits = bin(mask).count("1")
        size = intersect_fn(mask)
        if bits % 2 == 1:
            total = (total + size) % MOD
        else:
            total = (total - size + MOD) % MOD
    return total

def derangements(n: int) -> int:
    """Count permutations with no fixed points, mod MOD."""
    if n == 0:
        return 1
    if n == 1:
        return 0
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 0
    for i in range(2, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD
    return dp[n]

def euler_totient(n: int) -> int:
    """Euler's totient: count integers in [1, n] coprime to n."""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result

Key Edge Cases

• D(0) = 1 (the empty permutation is a derangement)
• Inclusion-exclusion with k > 20 is usually too slow (2^k subsets); look for algebraic shortcuts
• Totient of 1 is 1
• Overlapping constraints that are not independent require careful intersection counting

Common Mistakes

• Sign error: forgetting to alternate between addition and subtraction
• Double-counting when constraints are not mutually independent
• Not handling the complementary counting step (total minus IE result)

Game Theory (Sprague-Grundy)

Recognition Signals

• "Two players take turns, optimal play, who wins"
• Game with positions that can be decomposed into independent sub-games
• Nim-like games with pile manipulation
• "First player wins or second player wins"

Core Idea

The Sprague-Grundy theorem states that every impartial game position has a Grundy number (nimber). A position with Grundy number 0 is a losing position for the player to move. For composite games (independent sub-games), the overall Grundy number is the XOR of individual Grundy numbers. Standard Nim: XOR all pile sizes; if nonzero, first player wins.

Python Template

def compute_grundy(max_state: int, moves_fn) -> list[int]:
    """Compute Grundy numbers for states 0..max_state.

    moves_fn(state) returns an iterable of reachable states.
    """
    grundy = [0] * (max_state + 1)
    for state in range(max_state + 1):
        reachable: set[int] = set()
        for next_state in moves_fn(state):
            reachable.add(grundy[next_state])
        mex = 0
        while mex in reachable:
            mex += 1
        grundy[state] = mex
    return grundy

def game_winner(values: list[int]) -> str:
    """Winner via XOR. Works for Nim piles or composite Grundy values."""
    xor_sum = 0
    for v in values:
        xor_sum ^= v
    return "First" if xor_sum != 0 else "Second"

Key Edge Cases

• Terminal position (no moves available): Grundy number is 0 (losing for player to move)
• Single pile Nim: first player wins unless pile is 0
• Game with cycles: Sprague-Grundy applies only to acyclic (impartial) games
• Misere Nim: different endgame rule inverts the strategy for the last move

Common Mistakes

• Applying Sprague-Grundy to partisan games (different move sets per player)
• Forgetting that XOR-based composition requires sub-games to be independent
• Computing mex incorrectly by not collecting all reachable Grundy values first