Putting It All Together
All Pillars — "Every problem is still the same game: Fix, Set, Shape, Chain. The math just gives you more tools to execute each move."
The Setup
You've spent 11 chapters building a toolkit: primes, GCD, modular arithmetic, combinatorics, inclusion-exclusion, probability, game theory, Mobius, matrices, polynomials, CRT, Burnside. That's a lot of tools. The hard part was never understanding each tool in isolation — it was knowing which one to grab.
This lesson is the index. Given a problem statement, how do you read the signals and reach for the right technique? The answer lives in the four pillars.
The Recognition Guide
Every competitive math problem broadcasts signals about which pillar applies. Here's how to read them.
Signal: "Find \(x\) such that..." — Pillar: Fix
You're solving for an unknown. Something is held fixed (a modulus, a constraint, a structure), and you need to determine what value satisfies the conditions.
| Problem shape | Technique | Chapter |
|---|---|---|
| \(ax \equiv b \pmod{m}\) | Modular inverse via Extended Euclidean | Ch3-4 |
| System of congruences \(x \equiv r_i \pmod{m_i}\) | CRT / Garner's algorithm | Ch12 |
| \(a^x \equiv b \pmod{p}\) | Baby-step giant-step (discrete log) | Ch4 |
| Bezout: \(ax + by = \gcd(a,b)\) | Extended Euclidean | Ch3 |
The Fix pillar is about constraint satisfaction. You fix the structure and solve for the unknown.
Signal: "Count / How many..." — Pillar: Set + IE
You're measuring the size of a set. The question is which set, and whether inclusion-exclusion or a direct formula is faster.
| Problem shape | Technique | Chapter |
|---|---|---|
| Choose \(k\) from \(n\) | Binomial coefficients, Lucas | Ch5 |
| Count with forbidden positions | Inclusion-exclusion | Ch6 |
| Count coprime pairs in range | Mobius function / Euler totient | Ch4, Ch9 |
| Count divisors / sum of divisors | Multiplicative function sieve | Ch9 |
| Count up to symmetry | Burnside's lemma | Ch12 |
| Multiset counting | Stars and bars | Ch5 |
The Set pillar is about what you're counting and what algebra governs the collection.
Signal: "There exists... / Prove that..." — Pillar: Shape
Existence arguments and extremal results. These rarely ask you to compute a value — they ask whether something is possible, or what the minimum/maximum is.
| Problem shape | Technique | Chapter |
|---|---|---|
| \(n+1\) objects in \(n\) boxes | Pigeonhole principle | Ch1 |
| Convex/monotone structure in answer | Binary search on answer + check | Ch1 |
| Harmonic-sum bounds on sieve | \(O(n \log \log n)\) analysis | Ch2 |
| Floor function staircase | \(O(\sqrt{n})\) distinct values of \(\lfloor n/k \rfloor\) | Ch9 |
Shape is about structural properties — monotonicity, convexity, bounded distinct values — that let you bypass brute force.
Signal: "After \(n\) steps / transitions..." — Pillar: Chain
Sequential processes. Something evolves step by step, and you need the state after many steps.
| Problem shape | Technique | Chapter |
|---|---|---|
| Linear recurrence, large \(n\) | Matrix exponentiation | Ch10 |
| Game with positions and moves | Sprague-Grundy / nimbers | Ch8 |
| Expected value over random process | Linearity of expectation, EV recurrences | Ch7 |
| Polynomial multiplication | NTT / FFT | Ch11 |
| Generating function identity | Formal power series | Ch11 |
Chain is about transitions and dependencies — what depends on what, and how to skip ahead.
Signal: "Up to rotation / symmetry..." — Pillar: Fix (Burnside)
A special case of Fix. You fix a symmetry and count what survives. The averaging over all symmetries is Burnside.
| Problem shape | Technique | Chapter |
|---|---|---|
| Distinct necklaces / bracelets | Burnside + cyclic/dihedral group | Ch12 |
| Distinct grid colorings | Burnside + \(D_4\) | Ch12 |
| Weighted counting under symmetry | Polya enumeration (rare) | Beyond course |
The Decision Tree
When you read a problem, run through these questions in order.
Step 1: What is the problem asking for?
- An explicit value \(x\) satisfying constraints → Fix
- A count → Set (proceed to Step 2)
- An expected value → Chain (EV recurrence or linearity of expectation)
- A game-theoretic outcome (win/lose) → Chain (Sprague-Grundy)
- A yes/no existence → Shape (pigeonhole, extremal argument)
Step 2 (if counting): What kind of count?
- Count modulo a prime → probably needs modular inverse for division (Ch4)
- Count with "at least one of" / "none of" → inclusion-exclusion (Ch6)
- Count with coprimality constraint → Mobius inversion or totient sieve (Ch9)
- Count up to symmetry → Burnside (Ch12)
- Count sequences/multisets → combinatorics + stars-and-bars (Ch5)
- Count with a recurrence → matrix exponentiation if \(n\) is large (Ch10)
Step 3: What's the modulus structure?
- Modulus is prime → Fermat inverse, NTT-friendly if \(m = a \cdot 2^k + 1\)
- Modulus is composite → CRT to split into prime power components
- No modulus (exact answer) → might need multi-mod CRT + Garner's
- Modulus is \(2\) → XOR / nimber arithmetic (Ch8)
Step 4: What's the size constraint?
- \(n \leq 10^6\) → sieve-based approaches work
- \(n \leq 10^{18}\) → need \(O(\sqrt{n})\) or \(O(\log n)\) algorithms
- \(k\) (number of elements to combine) is small → matrix exponentiation, iterative CRT
- Answer could exceed \(10^{18}\) → Garner's algorithm,
__int128, or multi-mod
Technique Quick Reference
Here's the full map from technique to its chapter, complexity, and when to use it.
| Technique | Chapter | Time | Use when... |
|---|---|---|---|
| Trial division | Ch2 | \(O(\sqrt{n})\) | Factoring a single value |
| Sieve of Eratosthenes | Ch2 | \(O(n \log \log n)\) | Need all primes up to \(n\) |
| Smallest prime factor sieve | Ch2 | \(O(n \log \log n)\) | Need to factor many values quickly |
| Extended Euclidean | Ch3 | \(O(\log \min(a,b))\) | Modular inverse, Bezout coefficients |
| Binary exponentiation | Ch4 | \(O(\log e)\) | \(a^e \bmod m\) |
| Modular inverse | Ch4 | \(O(\log m)\) | Division mod prime |
| Euler totient | Ch4 | \(O(\sqrt{n})\) single, \(O(n \log \log n)\) sieve | Exponent reduction, coprime counting |
| Binomial coefficients | Ch5 | \(O(n)\) precompute | \(\binom{n}{k} \bmod p\) |
| Lucas' theorem | Ch5 | \(O(p + \log_p n)\) | \(\binom{n}{k} \bmod p\) where \(p\) is small prime |
| Inclusion-exclusion | Ch6 | \(O(2^k)\) for \(k\) sets | Count with forbidden patterns |
| Linearity of expectation | Ch7 | Varies | EV without full probability distribution |
| Sprague-Grundy | Ch8 | \(O(\text{positions} \times \text{moves})\) | Impartial games |
| Mobius inversion | Ch9 | \(O(n \log n)\) or \(O(n \log \log n)\) | Sum over divisors / coprime pairs |
| Mobius sieve | Ch9 | \(O(n \log \log n)\) | Bulk multiplicative function computation |
| Matrix exponentiation | Ch10 | \(O(d^3 \log n)\) | Linear recurrences with large \(n\) |
| NTT | Ch11 | \(O(n \log n)\) | Polynomial multiplication mod prime |
| CRT (iterative) | Ch12 | \(O(k \log M)\) | Combine congruences from different moduli |
| Garner's algorithm | Ch12 | \(O(k^2 \log M)\) | CRT without overflow; answer mod output prime |
| Burnside's lemma | Ch12 | \(O(\|G\| \cdot f)\) | Counting up to symmetry |
What This Course Deliberately Defers
Some topics are deeply intertwined with math but belong in other courses because they're primarily algorithmic patterns, not mathematical structures.
Deferred to the DP course:
- Digit DP. Counting integers in a range with digit-based constraints. The math is just modular arithmetic — the hard part is the DP state design.
- Knapsack and subset sum. The structure is combinatorial, but the technique is pure DP.
- Monoid transitions in DP. Matrix exponentiation (Ch10) teaches the math. The DP course teaches when and how to set up the transition matrix for specific problems.
- Generating functions for DP. Ch11 introduces formal power series. The DP course shows how to encode recurrences as generating functions and extract coefficients.
Deferred to the Graph course:
- Tropical semiring and Floyd-Warshall. The algebraic structure (min-plus semiring) is powerful, but the primary application is shortest paths — a graph topic.
- Flow and matching. The theory uses Hall's theorem (combinatorics) and LP duality (linear algebra), but the algorithms are graph algorithms.
- Euler tours and circuits. The math is light — the challenge is implementation.
Deferred to the Greedy course:
- Matroids. The mathematical foundation for when greedy works. The theory is algebraic (independence systems, rank functions), but the application is greedy algorithm design.
This course gave you the mathematical infrastructure. Those courses build algorithms on top of it.
Cross-References to Upcoming Courses
Here's how the math you've learned feeds into future topics.
DP Course
- Matrix exponentiation (Ch10) is the engine behind fast linear recurrence DP. The DP course will show you how to design the state vector and transition matrix for problems like "count paths of length \(n\)" or "number of tilings of a \(2 \times n\) grid."
- NTT (Ch11) enables polynomial multiplication, which the DP course uses for convolution-based subset sum and partition counting.
- Generating functions (Ch11) turn DP recurrences into algebraic equations that you can solve in closed form or compute via formal power series.
Graph Course
- Modular arithmetic (Ch4) appears in problems involving cycle detection and periodicity in graphs.
- The tropical semiring (min, +) replaces the standard (0, 1, +, ×) ring. Floyd-Warshall is "matrix exponentiation" in this semiring — the same \(O(n^3 \log k)\) trick from Ch10 computes shortest paths with at most \(k\) edges.
- GCD structure (Ch3) appears in problems about cycles in functional graphs: iterating \(f(x) = ax + b \bmod m\) has period dividing \(\text{ord}(a, m)\).
Greedy Course
- Matroid theory uses the concept of an independence system — a set family closed under taking subsets. The rank function of a matroid is submodular, which connects to the convexity ideas from the Shape pillar.
- Exchange arguments in greedy proofs often use the same logic as the Fix pillar: fix one choice and show the rest is forced.
What to Study Next
Your next steps depend on your goal.
Goal: FAANG / Top Tech Interviews
You're done with math. Chapters 1-8 cover everything you'll see. Focus on:
- DP course — the most common interview topic after arrays/strings.
- Graph course — BFS, DFS, shortest paths, topological sort.
- Practice — LeetCode medium/hard with a timer.
The advanced chapters (9-12) are overkill for interviews. Mobius inversion and Burnside's lemma don't appear in FAANG rounds.
Goal: Codeforces Rating 1800-2200
You need Chapters 1-10 solidly, with some Ch11-12 exposure. Focus on:
- Combinatorics (Ch5-6) — appears in almost every Div 2 D/E.
- Number theory (Ch2-4, Ch9) — GCD tricks, modular arithmetic, Mobius are recurring themes.
- Matrix exponentiation (Ch10) — standard technique for Div 2 E.
- DP course — the other half of competitive programming.
Goal: Codeforces 2400+ / ICPC
You need everything. All 12 chapters, deeply. Additionally:
- NTT mastery (Ch11) — implement from scratch, understand the prime constraints.
- Generating functions (Ch11) — convert DP to GF, extract \([x^n]\) efficiently.
- Burnside + Polya (Ch12) — rare but devastating when it appears.
- Multi-technique problems — the real challenge at this level is combining 2-3 techniques in a single problem. The practice set below targets this.
Mixed Practice: Multi-Technique Problems
These problems require combining techniques from different chapters. They're the real test of whether you can recognize which tools to deploy.
| Problem | Link | Techniques | Difficulty |
|---|---|---|---|
| CF 1264D — Beautiful Bracket Sequence | codeforces.com/contest/1264/problem/D | Combinatorics (Ch5) + Modular inverse (Ch4) | Hard |
| CF 1156E — Special Segments | codeforces.com/contest/1156/problem/E | Inclusion-exclusion (Ch6) + GCD structure (Ch3) | Hard |
| CF 1553F — Pairwise Modulo | codeforces.com/contest/1553/problem/F | Mobius / divisor sieve (Ch9) + prefix sums | Hard |
| CF 1117D — Magic Gems | codeforces.com/contest/1117/problem/D | Matrix exponentiation (Ch10) + recurrence | Medium |
| CF 632E — Thief in a Shop | codeforces.com/contest/632/problem/E | NTT (Ch11) + generating functions | Hard |
| CF 449D — Jzzhu and Numbers | codeforces.com/contest/449/problem/D | Inclusion-exclusion (Ch6) + bitmask (Set pillar) | Hard |
| CSES — Counting Necklaces | cses.fi/problemset/task/2209 | Burnside (Ch12) + totient (Ch4) | Medium |
| CF 687B — Remainders Game | codeforces.com/contest/687/problem/B | CRT theory (Ch12) + prime factorization (Ch2) | Medium |
The Four Pillars, One Last Time
| Pillar | Core Question | You Reach For... |
|---|---|---|
| Fix | "If I hold X still, what must Y be?" | Modular inverse, CRT, Burnside's "fix a symmetry" |
| Set | "What am I collecting? What operations combine them?" | Factorization as multiset, IE, sieve, GCD = intersection |
| Shape | "Is there structure I can exploit?" | Floor staircase, harmonic sums, binary search on answer |
| Chain | "What depends on what?" | Recurrences, matrix exp, Sprague-Grundy, EV transitions |
Every problem you'll face is some combination of these four moves. The chapters gave you the vocabulary. The pillars give you the grammar. Now go solve problems.
Quick Recap
- Fix signals: "find \(x\)", "solve for", congruences, constraints. Techniques: inverse, CRT, Burnside.
- Set signals: "count", "how many", "enumerate". Techniques: combinatorics, IE, Mobius, sieve.
- Shape signals: "exists", "minimum", "prove", monotonicity. Techniques: pigeonhole, binary search, floor tricks.
- Chain signals: "after \(n\) steps", "game", "expected value", "recurrence". Techniques: matrix exp, Grundy, EV DP.
- Use the decision tree: what is asked → what kind of count → what modulus → what size.
- This course defers Digit DP, Knapsack, Flow, and Matroids to their respective courses.
- Your next steps depend on your goal: interviews need Ch1-8, competitive programming needs everything.
This concludes the Mathematics for Problem Solving course. You now have 12 chapters of tools and four pillars to organize them. The rest is practice.