Concepts38
Floor Sum Formula
The floor sum computes S(n,m,a,b) = sum_{i=0}^{n-1} floor((a i + b)/m) efficiently in O(log(min(a,m))) time.
Harmonic Lemma
The Harmonic Lemma says that the values of \lfloor n/i \rfloor only change about 2\sqrt{n} times, so you can iterate those value blocks in O(\sqrt{n}) instead of O(n).
Game Theory - Nim
Nim is a two-player impartial game with several piles where a move removes any positive number of stones from exactly one pile.
Game Theory - Calculation Techniques
Sprague–Grundy theory converts any impartial, normal-play game into an equivalent Nim heap using a Grundy number.
Linearity of Expectation Applications
Linearity of expectation says the expected value of a sum equals the sum of expected values, even if the variables are dependent.
Expected Value
Expected value is the long-run average outcome of a random variable if you could repeat the experiment many times.
Bayes' Theorem
Bayes' Theorem tells you how to update the probability of a hypothesis after seeing new evidence.
Partition Function
The partition function p(n) counts the number of ways to write n as a sum of positive integers where order does not matter.
Generating Functions - OGF
An ordinary generating function (OGF) encodes a sequence (a_n) as a formal power series A(x) = \sum_{n \ge 0} a_n x^n.
Stirling Numbers of First Kind
Stirling numbers of the first kind count permutations by their number of cycles and connect power polynomials to rising/falling factorials.
Lucas' Theorem
Lucas' Theorem lets you compute C(n, k) modulo a prime p by working digit-by-digit in base p.
Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle (IEP) corrects overcounting by alternately adding and subtracting sizes of intersections of sets.