math-and-combinatoricslisted

# 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 | Trigger Signals | Technique | Typical Complexity | |---|---|---| | "answer modulo 10^9+7", large product/sum | Modular Arithmetic | O(1) per operation | | "count primes up to N", "smallest factor" | Sieve of Eratosthenes | O(N log log N) | | "greatest common divisor", "least common multiple" | GCD / LCM | O(log min(a,b)) | | "how many ways to choose", "combinations mod p" | Binomial Coefficients | O(N) precompute, O(1) query | | "compute a^b mod m", "matrix recurrence" | Fast Exponentiation | O(log b) | | "count arrangements", "distribute items into groups" | Counting Techniques | Varies | | "count elements satisfying at least one", "derangements" | Inclusion-Exclusion | O(2^k) for k constraints | | "two players, optimal play", "who wins" | Game Theory (Sprague-Grundy) | Varies by state space | --- ## 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 in