Chapter 7: Mathematics

Overview

Math is the secret weapon that turns many "impossible" problems into three lines of code. This chapter covers everything from the bread-and-butter (modular arithmetic, primes, combinatorics) through probability and game theory, up to the heavy artillery (FFT/NTT, Gaussian elimination, XOR basis). You don't need all of it at once — number theory and combinatorics alone cover most math-tagged problems on Codeforces — but when a problem does need FFT or Sprague-Grundy, nothing else will work.

Navigation

Coming from: Chapter 6 — Advanced Graph Algorithms — advanced graph decompositions, flows, and tree techniques
Going to: Chapter 8 — Geometry — computational geometry primitives and convex hull algorithms

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	Math Fundamentals	Beginner	GCD, fast exponentiation, "mod 10⁹+7"
02	Number Theory	Intermediate	"Primes," "divisors," "factorization," "sieve"
03	Extended Euclidean & CRT	Intermediate	"Modular inverse" or "solve system of congruences"
04	Combinatorics Basics	Intermediate	"Count arrangements" or "C(n, k) mod p"
05	Catalan Numbers	Intermediate	"Balanced parentheses," "binary trees," "non-crossing partitions"
06	Inclusion-Exclusion	Intermediate	"Count elements in A∪B∪C" or "at least one forbidden"
07	Game Theory — Nim & Sprague-Grundy	Intermediate	"Two players, both play optimally, who wins?"
08	Probability and Expected Value	Intermediate	"Expected number of steps" or "probability of event"
09	Matrix Exponentiation	Intermediate	"Linear recurrence" + huge n (10⁹+)
10	Gaussian Elimination	Advanced	"Solve linear system" or "XOR equations"
11	Linear Basis (XOR Basis)	Advanced	"Maximum XOR subset" or "XOR span"
12	FFT & NTT	Advanced	"Polynomial multiplication" or "count pairs with sum = k"

Grouped by skill

The same topics, regrouped so it is clear what kind of reasoning each one trains:

• Modular arithmetic and inverses — Math Fundamentals (01), Extended Euclidean & CRT (03).
• Counting — Combinatorics Basics (04), Catalan Numbers (05), Inclusion-Exclusion (06).
• Number-theoretic structure — Number Theory (02).
• Recurrences and transforms — Matrix Exponentiation (09), FFT & NTT (12).
• Linear algebra — Gaussian Elimination (10), Linear Basis / XOR (11).
• Games and probability — Game Theory & Nim (07), Probability and Expected Value (08).

If You Only Read 3 Files

Prerequisite, not optional: Math Fundamentals is assumed throughout. Do not skip it — modular arithmetic, fast exponentiation, and GCD show up in every other file in this chapter.

1. Number Theory — because primes, sieves, and divisor functions appear in a huge fraction of math problems. The Sieve of Eratosthenes alone solves dozens of problem types.
2. Combinatorics Basics — because "count the ways" is one of the most common problem types on Codeforces, and you need to compute C(n, k) mod p fluently. Stars and Bars, PIE, and binomial coefficients are essential.
3. Game Theory — Nim & Sprague-Grundy — because game theory problems look terrifying until you learn Sprague-Grundy theory, and then they become formulaic. XOR of Grundy values determines the winner.

Cross-Chapter Connections

• Math Fundamentals provides the modular arithmetic used everywhere, especially in Modular Arithmetic Basics from Chapter 0
• Combinatorics Basics powers many DP transitions in Chapter 4
• Matrix Exponentiation solves linear recurrences that appear in DP — 1D Introduction
• FFT & NTT is often combined with DP — Convex Hull Trick for advanced optimizations
• Game Theory uses Bit Manipulation (XOR operations) from Chapter 0
• Inclusion-Exclusion connects to SOS DP — both count over subsets

---

File Listing

File	Topic	Level
math-fundamentals	Math Fundamentals	⭐
number-theory	Number Theory	⭐⭐
combinatorics-basics	Combinatorics Basics	⭐⭐
catalan-numbers	Catalan Numbers	⭐⭐
inclusion-exclusion	Inclusion-Exclusion Principle	⭐⭐
extended-euclid-crt	Extended Euclidean & CRT	⭐⭐
matrix-exponentiation	Matrix Exponentiation	⭐⭐
game-theory-nim	Game Theory — Nim & Sprague-Grundy	⭐⭐
probability	Probability and Expected Value	⭐⭐
fft-ntt	FFT & NTT	⭐⭐⭐
gaussian-elimination	Gaussian Elimination	⭐⭐⭐
linear-basis-xor	Linear Basis (XOR Basis)	⭐⭐⭐

Suggested Reading Order

1. math-fundamentals — modular arithmetic, GCD/LCM, fast exponentiation
2. number-theory — primes, sieves, divisors, multiplicative functions
3. combinatorics-basics — binomial coefficients, counting principles
4. catalan-numbers — the ubiquitous counting sequence
5. inclusion-exclusion — count unions of overlapping sets
6. extended-euclid-crt — modular inverses and Chinese Remainder Theorem
7. probability — linearity of expectation and expected value DP
8. game-theory-nim — Sprague-Grundy theory for combinatorial games
9. matrix-exponentiation — compute linear recurrences for huge n
10. fft-ntt — O(n log n) polynomial multiplication
11. gaussian-elimination — solve linear systems over reals and GF(2)
12. linear-basis-xor — XOR subset queries via basis vectors