🐬 Formula

Every formula and identity worth knowing for CP, grouped by topic and numbered for quick reference. No explanations here. Each topic’s notes cover the details.

Sums and Series

1. ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$
2. ${\sum }_{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$
3. ${\sum }_{i=1}^n{i}^3={\left(\frac{n(n+1)}{2}\right)}^2$
4. ${\sum }_{i=1}^n{i}^4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$
5. ${\sum }_{i=1}^n(2i-1)=n^2$
6. ${\sum }_{i=0}^{n-1}{r}^i=\frac{r^n-1}{r-1}$ for $r\ne 1$
7. ${\sum }_{i=0}^{\infty }{r}^i=\frac{1}{1-r}$ for $|r|<1$
8. ${\sum }_{i=0}^{\infty }i{r}^i=\frac{r}{(1-r{)}^2}$ for $|r|<1$
9. ${\sum }_{i=0}^{n}i{2}^i=(n-1)2^{n+1}+2$
10. ${\sum }_{i=1}^{n}i(i+1)=\frac{n(n+1)(n+2)}{3}$
11. ${\sum }_{i=1}^n\frac{1}{i(i+1)}=\frac{n}{n+1}$
12. ${\sum }_{i=1}^n\left(\genfrac{}{}{0ex}{}{i}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$ (sum of falling powers: ${\sum }_i{i}^{\underline{k}}=\frac{(n+1{)}^{\underline{k+1}}}{k+1}$)
13. $H_n={\sum }_{i=1}^n\frac{1}{i}=\ln n+\gamma +O(1/n)$, $\gamma \approx 0.5772$
14. ${\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor ={\sum }_{i=1}^{n}d(i)\approx n\ln n$
15. ${\sum }_{p\le n}\frac{1}{p}=\ln \ln n+O(1)$ (sieve is $O(n\log \log n)$)
16. ${\sum }_{i=1}^{\infty }\frac{1}{i^2}=\frac{{\pi }^2}{6}$
17. Faulhaber: ${\sum }_{i=1}^n{i}^k=\frac{1}{k+1}{\sum }_{j=0}^k\left(\genfrac{}{}{0ex}{}{k+1}{j}\right)B_j{n}^{k+1-j}$ (Bernoulli numbers, $B_1=+\frac{1}{2}$)
18. ${\sum }_{i=1}^n{i}^k$ is a polynomial of degree $k+1$ in $n$ (use Lagrange interpolation on $k+2$ points)
19. Abel summation: ${\sum }_{i=1}^n{a}_i{b}_i=A_n{b}_n-{\sum }_{i=1}^{n-1}{A}_i(b_{i+1}-b_i)$, $A_i={\sum }_{j\le i}{a}_j$
20. Sum of all subarray sums: ${\sum }_{i=1}^n{a}_i\cdot i\cdot (n-i+1)$
21. Sum of all pairwise $|a_i-a_j|$ (sorted): ${\sum }_{i=1}^n{a}_i(2i-n-1)$
22. Sum over all subsets of the subset sums: $2^{n-1}\sum a_i$

Floor, Ceil and Division

23. $\lceil \frac{a}{b}\rceil =\lfloor \frac{a+b-1}{b}\rfloor$ for $a\ge 0,b>0$
24. $\lfloor \frac{\lfloor a/b\rfloor }{c}\rfloor =\lfloor \frac{a}{bc}\rfloor$
25. $\lfloor n/i\rfloor$ takes at most $2\sqrt{n}$ distinct values. For a block starting at $i$, the last index with the same value is $j=\lfloor n/\lfloor n/i\rfloor \rfloor$
26. $a\mathrm{mod}b=a-b\lfloor a/b\rfloor$
27. $\lfloor x\rfloor +\lfloor y\rfloor \le \lfloor x+y\rfloor \le \lfloor x\rfloor +\lfloor y\rfloor +1$
28. Hermite: ${\sum }_{k=0}^{n-1}\lfloor x+\frac{k}{n}\rfloor =\lfloor nx\rfloor$
29. ${\sum }_{i=0}^{n-1}\lfloor \frac{ai+b}{c}\rfloor$ is computed in $O(\log )$ by the floor-sum (Euclid-like) recursion
30. Number of multiples of $k$ in $[l,r]$: $\lfloor r/k\rfloor -\lfloor (l-1)/k\rfloor$
31. $\lfloor \sqrt{n}\rfloor$: start from sqrtl(n), then adjust by $\pm 1$ while the square overshoots or undershoots

GCD and Divisibility

32. $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$, $\gcd (a,0)=a$
33. $\gcd (a,b)\cdot \mathrm{lcm}(a,b)=a\cdot b$
34. Bézout: $\exists x,y:ax+by=\gcd (a,b)$
35. $ax+by=c$ is solvable iff $\gcd (a,b)\mid c$. General solution: $x=x_0+k\frac{b}{g},y=y_0-k\frac{a}{g}$
36. $\gcd (a,b)=\gcd (a-b,b)$, $\gcd (ka,kb)=k\gcd (a,b)$
37. $\gcd (a^m-1,a^n-1)=a^{\gcd (m,n)}-1$
38. $\gcd (F_m,F_n)=F_{\gcd (m,n)}$
39. $\gcd (a,b)=\gcd (a,b+ka)$ $\Rightarrow$ $\gcd$ of an array is preserved under adjacent differences
40. Prefix gcds take at most ${\log }_{2}V+1$ distinct values
41. $\mathrm{lcm}(1,\dots ,n)=e^{n(1+o(1))}$ (grows like $e^n$)
42. Chicken McNugget: the largest number not representable as $ax+by$ ($x,y\ge 0$, $\gcd (a,b)=1$) is $ab-a-b$. Exactly $\frac{(a-1)(b-1)}{2}$ numbers are not representable
43. Euclid’s lemma: $p\mid ab\Rightarrow p\mid a\vee p\mid b$ for prime $p$

Divisor Functions

44. If $n=\prod p_i^{e_i}$: $d(n)=\prod (e_i+1)$
45. $\sigma (n)=\prod \frac{p_i^{e_i+1}-1}{p_i-1}$
46. ${\sigma }_k(n)=\prod \frac{p_i^{k(e_i+1)}-1}{p_i^k-1}$
47. Product of divisors: $n^{d(n)/2}$
48. ${\max }_{n\le 10^9}d(n)=1344$, ${\max }_{n\le 10^{18}}d(n)=103680$
49. ${\sum }_{d\mid n}\phi (d)=n$
50. ${\sum }_{d\mid n}\mu (d)=[n=1]$
51. Number of divisors of $n$ is at most about $2\sqrt{n}$, typically $n^{O(1/\log \log n)}$

Euler’s Totient and Möbius

52. $\phi (n)=n{\prod }_{p\mid n}\left(1-\frac{1}{p}\right)$
53. $\phi (p^k)=p^k-p^{k-1}$, $\phi$ is multiplicative
54. $\phi (mn)=\phi (m)\phi (n)\frac{g}{\phi (g)}$, $g=\gcd (m,n)$
55. ${\sum }_{i=1}^n[\gcd (i,n)=1]i=\frac{n\phi (n)}{2}$ for $n>1$
56. ${\sum }_{i=1}^n\gcd (i,n)={\sum }_{d\mid n}d\phi (n/d)$
57. ${\sum }_{i=1}^n\mathrm{lcm}(i,n)=\frac{n}{2}\left({\sum }_{d\mid n}d\phi (d)+1\right)$
58. $[\gcd (a,b)=1]={\sum }_{d\mid \gcd (a,b)}\mu (d)$
59. ${\sum }_{i=1}^n{\sum }_{j=1}^m[\gcd (i,j)=1]={\sum }_{d\ge 1}\mu (d)\lfloor n/d\rfloor \lfloor m/d\rfloor$
60. ${\sum }_{i=1}^n{\sum }_{j=1}^n\gcd (i,j)={\sum }_{d=1}^n\phi (d)\lfloor n/d{\rfloor }^2$
61. Möbius inversion: $g(n)={\sum }_{d\mid n}f(d)⟺f(n)={\sum }_{d\mid n}\mu (d)g(n/d)$
62. Superset form: $g(d)={\sum }_{d\mid n}f(n)⟺f(d)={\sum }_{d\mid n}\mu (n/d)g(n)$
63. Dirichlet convolution: $(f\ast g)(n)={\sum }_{d\mid n}f(d)g(n/d)$. Identities: $\mu \ast 1=\epsilon$, $\phi \ast 1=\mathrm{id}$, $1\ast 1=d$, $\mathrm{id}\ast 1=\sigma$
64. ${\sum }_{i=1}^n\phi (i)\approx \frac{3n^2}{{\pi }^2}$, probability two random integers are coprime is $\frac{6}{{\pi }^2}$
65. Du’s sieve: $S(n)={\sum }_{i\le n}(f\ast g)(i)-{\sum }_{i=2}^{n}g(i)S(\lfloor n/i\rfloor )$ (with $g(1)=1$), $O(n^{2/3})$

Modular Arithmetic

66. Fermat: $a^{p-1}\equiv 1(\mathrm{mod}p)$ for prime $p\nmid a$ $\Rightarrow$ $a^{-1}\equiv a^{p-2}$
67. Euler: $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$ for $\gcd (a,m)=1$
68. Extended Euler: $a^b\equiv a^{(b\mathrm{mod}\phi (m))+\phi (m)}(\mathrm{mod}m)$ for $b\ge \phi (m)$ (any $a$) — power towers
69. Wilson: $(p-1)!\equiv -1(\mathrm{mod}p)$
70. Inverses $\mathrm{1..}n$ in $O(n)$: $\mathrm{inv}[i]=-\lfloor p/i\rfloor \cdot \mathrm{inv}[p\mathrm{mod}i]\mathrm{mod}p$
71. $(a/b)\mathrm{mod}p=a\cdot b^{p-2}\mathrm{mod}p$
72. CRT: for coprime $m_i$, $x\equiv \sum a_i{M}_i(M_i^{-1}\mathrm{mod}{m}_i)(\mathrm{mod}M)$, $M_i=M/m_i$
73. CRT for non-coprime $m_1,m_2$: solvable iff $a_1\equiv a_2(\mathrm{mod}\gcd (m_1,m_2))$, result is modulo $\mathrm{lcm}$
74. $a\equiv b(\mathrm{mod}m)\Rightarrow a^k\equiv b^k(\mathrm{mod}m)$
75. $ka\equiv kb(\mathrm{mod}m)⟺a\equiv b(\mathrm{mod}m/\gcd (k,m))$
76. $x^2\equiv 1(\mathrm{mod}p)⟺x\equiv \pm 1$
77. Euler criterion: $a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p)$
78. Number of quadratic residues mod odd prime $p$ (excluding 0): $\frac{p-1}{2}$
79. $\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}$, $\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}$
80. Quadratic reciprocity: $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$
81. A primitive root exists modulo $1,2,4,p^k,2p^k$. There are $\phi (\phi (m))$ of them
82. $g$ is a primitive root mod $p$ iff $g^{(p-1)/q}\ne 1$ for every prime $q\mid p-1$
83. ${\mathrm{ord}}_m(a)\mid \phi (m)$
84. $x^k\equiv a(\mathrm{mod}p)$ has $\gcd (k,p-1)$ solutions if $a^{(p-1)/\gcd (k,p-1)}\equiv 1$, else 0
85. $-a\mathrm{mod}m=(m-a\mathrm{mod}m)\mathrm{mod}m$, safe mod: ((a % m) + m) % m
86. NTT-friendly primes: $998244353=119\cdot 2^{23}+1$ (root 3), $469762049=7\cdot 2^{26}+1$ (root 3), $167772161=5\cdot 2^{25}+1$ (root 3)
87. Common hashing primes: $10^9+7$, $10^9+9$, $2^{61}-1$ (Mersenne)

Primes

88. $\pi (n)\sim \frac{n}{\ln n}$. $\pi (10^6)=78498$, $\pi (10^7)=664579$, $\pi (10^9)=50847534$
89. Prime gaps below $10^9$ are at most 282, below $10^{18}$ at most 1442
90. Deterministic Miller–Rabin for 64-bit: bases $\{2,325,9375,28178,450775,9780504,1795265022\}$, or the first 12 primes
91. Bertrand: there is a prime in $(n,2n]$ for $n\ge 1$
92. Goldbach (verified far beyond $10^{18}$): every even $n>2$ is a sum of two primes
93. Every prime $p>3$ is $6k\pm 1$
94. Legendre: exponent of $p$ in $n!$ is ${\nu }_p(n!)={\sum }_{k\ge 1}\lfloor n/p^k\rfloor =\frac{n-s_p(n)}{p-1}$
95. Kummer: ${\nu }_p\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ = number of carries when adding $m$ and $n$ in base $p$
96. Lifting the exponent: for odd $p\mid a-b$, $p\nmid ab$: ${\nu }_p(a^n-b^n)={\nu }_p(a-b)+{\nu }_p(n)$
97. Trailing zeros of $n!$: ${\sum }_{k\ge 1}\lfloor n/5^k\rfloor$
98. Fermat’s two squares: $n$ is a sum of two squares iff every prime $p\equiv 3(\mathrm{mod}4)$ appears with an even exponent
99. Four squares (Lagrange): every $n\ge 0$ is a sum of four squares. Three squares works unless $n=4^a(8b+7)$

Binomial Coefficients

100. $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$, $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$
101. Pascal: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$
102. $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n}{k}\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$, $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$
103. ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$, ${\sum }_k(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=[n=0]$
104. ${\sum }_{k\text{ even}}\left(\genfrac{}{}{0ex}{}{n}{k}\right)={\sum }_{k\text{ odd}}\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^{n-1}$ for $n\ge 1$
105. ${\sum }_{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n-1}$, ${\sum }_k{k}^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n(n+1)2^{n-2}$
106. Hockey stick: ${\sum }_{i=r}^n\left(\genfrac{}{}{0ex}{}{i}{r}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{r+1}\right)$
107. Vandermonde: ${\sum }_k\left(\genfrac{}{}{0ex}{}{m}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{r-k}\right)=\left(\genfrac{}{}{0ex}{}{m+n}{r}\right)$
108. ${\sum }_k{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$
109. ${\sum }_{k=0}^m\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+m+1}{m}\right)$
110. ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)=F_{n+1}$ (shallow diagonals of Pascal’s triangle)
111. $\left(\genfrac{}{}{0ex}{}{n}{m}\right)\left(\genfrac{}{}{0ex}{}{m}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n-k}{m-k}\right)$
112. ${\sum }_{k=0}^m(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=(-1{)}^m\left(\genfrac{}{}{0ex}{}{n-1}{m}\right)$
113. $\left(\genfrac{}{}{0ex}{}{-n}{k}\right)=(-1{)}^k(\genfrac{}{}{0ex}{}{n+k-1}{k})$
114. Lucas: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\equiv \prod \left(\genfrac{}{}{0ex}{}{n_i}{k_i}\right)(\mathrm{mod}p)$ (base-$p$ digits)
115. $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is odd iff $k\&n=k$ (i.e. $k\subseteq n$ as bitmasks)
116. Binomial theorem: $(x+y{)}^n={\sum }_k(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$
117. Multinomial: $\left(\genfrac{}{}{0ex}{}{n}{k_1,\dots ,k_m}\right)=\frac{n!}{k_1!\cdots k_m!}$
118. $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le {\left(\frac{en}{k}\right)}^k$, $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim \frac{4^n}{\sqrt{\pi n}}$
119. Central binomial: $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)={\sum }_k{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2$

Counting

120. Stars and bars: nonnegative solutions of $x_1+\cdots +x_k=n$: $\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$. Positive: $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$
121. With upper bounds $x_i\le c$: ${\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j}\left)\right(\genfrac{}{}{0ex}{}{n-j(c+1)+k-1}{k-1})$
122. Multisets of size $k$ from $n$ types: $\left(\genfrac{}{}{0ex}{}{n+k-1}{k}\right)$
123. Lattice paths $(0,0)\to (a,b)$: $\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$
124. Paths not crossing $y=x$ (reflection): $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)$. Paths to $(a,b)$ that touch $y=x+c$: reflect the start point across it
125. Ballot problem: sequences with $a$ up-steps, $b$ down-steps ($a>b$) staying positive: $\frac{a-b}{a+b}\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$
126. Permutations of a multiset: $\frac{n!}{\prod c_i!}$
127. $k$-permutations: $n^{\underline{k}}=\frac{n!}{(n-k)!}$
128. Circular arrangements: $(n-1)!$, necklaces up to reflection too: $\frac{(n-1)!}{2}$
129. Derangements: $D_n=(n-1)(D_{n-1}+D_{n-2})$, $D_n=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}\approx \frac{n!}{e}$
130. Inclusion–exclusion: $\left|\bigcup A_i\right|={\sum }_{\varnothing \ne S}(-1{)}^{|S|+1}\left|{\bigcap }_{i\in S}{A}_i\right|$
131. Surjections $[n]\to [k]$: ${\sum }_{j=0}^k(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})(k-j{)}^n=k!S(n,k)$
132. Functions $[n]\to [k]$: $k^n$. Injections: $k^{\underline{n}}$
133. Subsets of size $k$ with no two adjacent from $[n]$: $\left(\genfrac{}{}{0ex}{}{n-k+1}{k}\right)$
134. Burnside: number of orbits $=\frac{1}{|G|}{\sum }_{g\in G}|X^g|$
135. Necklaces of length $n$ with $k$ colors (rotation): $\frac{1}{n}{\sum }_{d\mid n}\phi (d)k^{n/d}$
136. Bracelets (rotation + reflection): $\frac{N}{2}+\frac{k^{\lceil n/2\rceil }+k^{\lfloor n/2\rfloor +1}}{4}$ for even $n$ (with $N$ = necklaces), $\frac{N}{2}+\frac{k^{(n+1)/2}}{2}$ for odd $n$
137. Pólya: $|X/G|=\frac{1}{|G|}{\sum }_g{k}^{c(g)}$, $c(g)$ = number of cycles of $g$
138. Labeled graphs on $n$ vertices: $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$
139. Cayley: labeled trees on $n$ vertices: $n^{n-2}$. Rooted labeled forests with $k$ given roots: $k{n}^{n-k-1}$
140. Spanning trees of $K_{m,n}$: $m^{n-1}{n}^{m-1}$
141. Kirchhoff: number of spanning trees = any cofactor of the Laplacian $L=D-A$
142. LGV lemma: non-intersecting path systems $=\det \left[e(a_i,b_j)\right]$
143. Number of perfect matchings of $K_{2n}$: $(2n-1)!!=\frac{(2n)!}{2^{n}n!}$
144. Involutions: $I_n=I_{n-1}+(n-1)I_{n-2}$
145. Permutations with $k$ inversions: $I(n,k)={\sum }_{j=0}^{\min (k,n-1)}I(n-1,k-j)$. Total inversions over all permutations: $n!\frac{n(n-1)}{4}$
146. Expected number of fixed points of a random permutation: $1$. Expected cycles: $H_n$

Special Numbers

147. Catalan: $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)$, $C_{n+1}={\sum }_{i=0}^n{C}_i{C}_{n-i}$, $C_{n+1}=\frac{2(2n+1)}{n+2}{C}_n$
148. Catalan counts: balanced parentheses, binary trees with $n$ nodes, full binary trees with $n+1$ leaves, triangulations of an $(n+2)$-gon, Dyck paths, non-crossing partitions, monotone lattice paths under the diagonal, 231-avoiding permutations
149. $C_n$: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796
150. Super Catalan / Schröder: $S_n=S_{n-1}+{\sum }_{k=0}^{n-1}{S}_k{S}_{n-1-k}$ (1, 2, 6, 22, 90)
151. Motzkin: $M_{n+1}=M_n+{\sum }_{k=0}^{n-1}{M}_k{M}_{n-1-k}$ (1, 1, 2, 4, 9, 21, 51)
152. Stirling 1st kind (unsigned, permutations with $k$ cycles): $c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$, ${\sum }_{k}c(n,k)=n!$
153. $x^{\overline{n}}={\sum }_{k}c(n,k)x^k$
154. Stirling 2nd kind (partitions into $k$ nonempty sets): $S(n,k)=S(n-1,k-1)+kS(n-1,k)$
155. $S(n,k)=\frac{1}{k!}{\sum }_{j=0}^k(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})(k-j{)}^n$, $x^n={\sum }_{k}S(n,k)x^{\underline{k}}$
156. Bell: $B_n={\sum }_{k}S(n,k)$, $B_{n+1}={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)B_k$ (1, 1, 2, 5, 15, 52, 203, 877)
157. Partitions of $n$: $p(n)={\sum }_{k\ge 1}(-1{)}^{k+1}\left[p(n-k(3k-1)/2)+p(n-k(3k+1)/2)\right]$ (pentagonal theorem). $p(100)=190569292$
158. Partitions into distinct parts = partitions into odd parts
159. Partitions of $n$ into at most $k$ parts = partitions of $n$ into parts of size at most $k$: $p_k(n)=p_{k-1}(n)+p_k(n-k)$
160. Eulerian numbers (permutations with $k$ ascents): $A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1)$
161. Narayana: $N(n,k)=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$ (Dyck paths with $k$ peaks)
162. Fibonacci: $F_n=F_{n-1}+F_{n-2}$, $F_n=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}}$, $\phi =\frac{1+\sqrt{5}}{2}$
163. $\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n$
164. Doubling: $F_{2n}=F_n(2F_{n+1}-F_n)$, $F_{2n+1}=F_{n+1}^2+F_n^2$
165. Cassini: $F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$
166. $F_{m+n}=F_m{F}_{n+1}+F_{m-1}{F}_n$, ${\sum }_{i=1}^n{F}_i=F_{n+2}-1$, $\sum F_i^2=F_n{F}_{n+1}$
167. Pisano period for $10^k$ ($k\ge 3$): $15\cdot 10^{k-1}$. $\pi (p)\mid p-1$ if $p\equiv \pm 1(\mathrm{mod}5)$, $\pi (p)\mid 2(p+1)$ if $p\equiv \pm 2(\mathrm{mod}5)$
168. Zeckendorf: every positive integer is a unique sum of non-consecutive Fibonacci numbers
169. Bernoulli: ${\sum }_{j=0}^m\left(\genfrac{}{}{0ex}{}{m+1}{j}\right)B_j=0$ for $m\ge 1$, $B_0=1$
170. Harmonic: $H_n$; Wolstenholme: $H_{p-1}\equiv 0(\mathrm{mod}{p}^2)$ for $p\ge 5$

Generating Functions

171. $\frac{1}{1-x}=\sum x^n$, $\frac{1}{(1-x{)}^k}=\sum \left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)x^n$
172. $\frac{1}{1-ax}=\sum a^n{x}^n$, $e^x=\sum \frac{x^n}{n!}$, $-\ln (1-x)={\sum }_{n\ge 1}\frac{x^n}{n}$
173. Catalan: $C(x)=\frac{1-\sqrt{1-4x}}{2x}$, $C=1+x{C}^2$
174. Fibonacci: $\frac{x}{1-x-x^2}$
175. Partitions: ${\prod }_{k\ge 1}\frac{1}{1-x^k}$. Distinct parts: $\prod (1+x^k)$
176. EGF of set partitions: $e^{e^x-1}$. Derangements: $\frac{e^{-x}}{1-x}$. Involutions: $e^{x+x^2/2}$
177. Exponential formula: connected structures $C(x)$ $\Rightarrow$ all structures $e^{C(x)}$
178. Product of OGFs = convolution. Product of EGFs = binomial convolution
179. Linear recurrence of order $d$ $\iff$ rational GF $P(x)/Q(x)$, $\mathrm{deg}P<d$, $Q(x)=1-c_{1}x-\cdots -c_d{x}^d$. The $n$-th term is $[x^n]\frac{P}{Q}$ (Bostan–Mori, $O(d\log d\log n)$)
180. Multiplying by $x\frac{d}{dx}$ maps $a_n\to n{a}_n$. Multiplying by $\frac{1}{1-x}$ takes prefix sums

Probability and Expectation

181. Linearity: $E[X+Y]=E[X]+E[Y]$ always. $E[XY]=E[X]E[Y]$ if independent
182. $E[X]={\sum }_{k\ge 1}P(X\ge k)$ for $X\in {\mathbb{Z}}_{\ge 0}$
183. $\mathrm{Var}(X)=E[X^2]-E[X{]}^2$, $\mathrm{Var}(aX+b)=a^2\mathrm{Var}(X)$
184. Geometric (success prob. $p$): $E=\frac{1}{p}$, $\mathrm{Var}=\frac{1-p}{p^2}$
185. Binomial$(n,p)$: $E=np$, $\mathrm{Var}=np(1-p)$
186. Coupon collector: $E=n{H}_n$
187. Birthday: collision expected after $\approx \sqrt{\pi n/2}$ draws. $P(\text{collision})\approx 1-e^{-k^2/(2n)}$
188. Bayes: $P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}$
189. Total probability: $P(B)={\sum }_{i}P(B\mid A_i)P(A_i)$
190. Indicator trick: $E[\#\text{events}]=\sum P({\text{event}}_i)$
191. Expected maximum of $n$ i.i.d. $U[0,1]$: $\frac{n}{n+1}$. Expected $k$-th smallest: $\frac{k}{n+1}$
192. Gambler’s ruin (fair): probability of reaching $N$ from $i$ is $\frac{i}{N}$. Biased with $r=q/p$: $\frac{1-r^i}{1-r^N}$
193. Random walk on a line: expected time to hit $\pm n$ from 0 is $n^2$
194. Markov: $P(X\ge a)\le \frac{E[X]}{a}$. Chebyshev: $P(|X-\mu |\ge k\sigma )\le \frac{1}{k^2}$
195. Expected value mod $p$: $\frac{a}{b}\to a\cdot b^{-1}\mathrm{mod}p$
196. Expected steps in a Markov chain: $E_i=1+{\sum }_j{P}_{ij}{E}_j$ (solve the linear system, or DP on a DAG)
197. Probability that a random permutation has a given $k$-cycle structure: $\prod \frac{1}{k_i^{m_i}{m}_i!}$

Linear Algebra and Matrices

198. $\det (AB)=\det A\det B$, $\det (A^T)=\det A$, $\det (A^{-1})=\frac{1}{\det A}$
199. Swapping rows flips the sign, adding a multiple of a row keeps it, scaling a row by $c$ multiplies it by $c$
200. $(AB{)}^{-1}=B^{-1}{A}^{-1}$, $(AB{)}^T=B^T{A}^T$
201. $2\times 2$ inverse: ${\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)}^{-1}=\frac{1}{ad-bc}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$
202. Rank–nullity: $\mathrm{rank}(A)+\mathrm{nullity}(A)=n$ (columns)
203. Number of solutions of $Ax=b$ over ${\mathbb{F}}_p$ (if consistent): $p^{n-\mathrm{rank}}$
204. Linear recurrence $\Rightarrow$ companion matrix power: $O(d^3\log n)$, or Kitamasa $O(d^2\log n)$
205. Number of walks of length $k$ from $i$ to $j$: $(A^k{)}_{ij}$
206. Shortest walk with exactly $k$ edges: min-plus matrix power
207. Cayley–Hamilton: $p_A(A)=0$
208. Vandermonde determinant: ${\prod }_{i<j}(x_j-x_i)$
209. XOR basis: size $\le \log V$. A span of $r$ basis vectors has $2^r$ elements. Every value in the span is produced by $2^{n-r}$ subsets

Bit Manipulation

210. $a+b=(a\oplus b)+2(a\&b)$
211. $a+b=(a|b)+(a\&b)$
212. $a\oplus b=(a|b)-(a\&b)$
213. $|a-b|\le a\oplus b\le a+b$ and $a\oplus b\equiv a+b(\mathrm{mod}2)$
214. $x\&(x-1)$ clears the lowest set bit. $x\&(-x)$ isolates it
215. $x|(x+1)$ sets the lowest zero bit. $x\&(x+1)$ clears trailing ones
216. $x$ is a power of 2 iff $x>0$ and $x\&(x-1)=0$
217. ${⨁}_{i=0}^{n}i=n,1,n+1,0$ for $n\mathrm{mod}4=0,1,2,3$
218. ${⨁}_{i=l}^{r}i=X(r)\oplus X(l-1)$, with $X$ from formula 217
219. ${\max }_{l\le a\le b\le r}(a\oplus b)=2^{\lfloor {\log }_2(l\oplus r)\rfloor +1}-1$ (or 0 if $l=r$)
220. Submask enumeration: for (s = m; s; s = (s - 1) & m). Over all masks this is $3^n$ in total
221. Gosper’s hack (next mask with the same popcount): c = x & -x, r = x + c, x = (((r ^ x) >> 2) / c) | r
222. Gray code: $g(n)=n\oplus (n\gg 1)$. Inverse: prefix XOR of the bits from the top
223. $\mathrm{popcount}(a\oplus b)\equiv \mathrm{popcount}(a)+\mathrm{popcount}(b)(\mathrm{mod}2)$
224. Bits are independent: ${\sum }_i{\sum }_j(a_i\oplus a_j)={\sum }_b{2}^b\cdot c_b(n-c_b)$, $c_b$ = count with bit $b$ set
225. Sum of $\mathrm{AND}$ over all subarrays: per bit, count maximal runs of 1s. A run of length $L$ in bit $b$ contributes $\frac{L(L+1)}{2}\cdot 2^b$
226. SOS DP: $F[m]={\sum }_{s\subseteq m}f[s]$ in $O(n{2}^n)$. Inverse (Möbius) with alternating signs
227. Subset convolution: $O(n^2{2}^n)$ with ranked zeta transforms
228. XOR convolution via FWHT: $H={\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)}^{\otimes n}$, inverse divides by $2^n$
229. __builtin_popcountll, __builtin_clzll (undefined for 0), __builtin_ctzll, __lg(x) $=\lfloor {\log }_{2}x\rfloor$, std::bit_width

Graph Theory

230. Handshake: $\sum \mathrm{deg}(v)=2|E|$, so the number of odd-degree vertices is even
231. A tree has $n-1$ edges. A forest with $c$ components has $n-c$ edges
232. Euler path exists iff connected (ignoring isolated vertices) and 0 or 2 odd vertices. Directed: $\mathrm{in}=\mathrm{out}$ everywhere, except at most one vertex with $+1$ and one with $-1$
233. Euler’s formula (planar, connected): $V-E+F=2$. Simple planar: $E\le 3V-6$, bipartite planar: $E\le 2V-4$
234. Kőnig (bipartite): max matching $=$ min vertex cover. Max independent set $=V-$ max matching
235. Hall: a matching saturating $L$ exists iff $|N(S)|\ge |S|$ for all $S\subseteq L$
236. Gallai: in any graph without isolated vertices, $\alpha (G)+\tau (G)=n$ and $\nu (G)+\rho (G)=n$ (max matching + min edge cover)
237. Dilworth: in a poset, min chain cover $=$ max antichain. Min path cover in a DAG $=n-$ max matching of the split graph
238. Mirsky: min antichain cover $=$ longest chain (LIS length duality)
239. Max-flow $=$ min-cut
240. Erdős–Gallai: $d_1\ge \cdots \ge d_n$ is graphic iff the sum is even and ${\sum }_{i\le k}{d}_i\le k(k-1)+{\sum }_{i>k}\min (d_i,k)$ for all $k$
241. Turán: a $K_{r+1}$-free graph has at most $\left(1-\frac{1}{r}\right)\frac{n^2}{2}$ edges
242. Bipartite iff there is no odd cycle
243. Number of edges in a DAG’s transitive closure: compute with bitsets in $O(\frac{nm}{w})$
244. Tree diameter: BFS from any vertex to the farthest $u$, then BFS from $u$
245. Centers: 1 or 2. Centroids: 1 or 2. The centroid’s largest remaining component has $\le n/2$ vertices
246. Prüfer sequence: length $n-2$, vertex $v$ appears $\mathrm{deg}(v)-1$ times $\Rightarrow$ trees with given degrees: $\frac{(n-2)!}{\prod (d_i-1)!}$
247. Number of distinct paths in a tree: $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Sum of all pairwise distances: ${\sum }_e{s}_e(n-s_e)$
248. Brooks: $\chi (G)\le \Delta (G)$ unless $G$ is complete or an odd cycle. Vizing: ${\chi }^{\prime }(G)\in \{\Delta ,\Delta +1\}$
249. Chromatic polynomial of a tree: $k(k-1{)}^{n-1}$. Cycle: $(k-1{)}^n+(-1{)}^n(k-1)$
250. Ramsey: $R(3,3)=6$, $R(4,4)=18$
251. Small-to-large merging: every element moves $O(\log n)$ times
252. HLD: any root-to-leaf path crosses $O(\log n)$ light edges

Game Theory

253. Nim: the first player wins iff $a_1\oplus a_2\oplus \cdots \oplus a_n\ne 0$
254. Sprague–Grundy: $g(v)=\mathrm{mex}\{g(u):v\to u\}$. Sum of games: XOR of Grundy values
255. Misère Nim: if all piles $\le 1$, the first player wins iff the number of piles is even. Otherwise as normal Nim
256. Staircase Nim: equivalent to Nim on the odd-indexed steps
257. Bash game (take $\mathrm{1..}k$): lose iff $n\equiv 0(\mathrm{mod}k+1)$
258. Wythoff: losing positions are $(\lfloor k\phi \rfloor ,\lfloor k{\phi }^2\rfloor )$
259. Moore’s Nim${}_k$ (take from up to $k$ piles): lose iff every bit’s count is $\equiv 0(\mathrm{mod}k+1)$
260. Subtraction game with set $S$: Grundy values are eventually periodic
261. Green Hackenbush on trees: $g(v)={⨁}_c(g(c)+1)$ (colon principle)
262. Chomp, Hex: the first player wins (strategy stealing)

Geometry

263. Cross product: $a\times b=a_x{b}_y-a_y{b}_x$ (positive $\Rightarrow$ $b$ is counter-clockwise from $a$)
264. Dot product: $a\cdot b=|a||b|\cos \theta$
265. Shoelace: $A=\frac{1}{2}\left|{\sum }_i(x_i{y}_{i+1}-x_{i+1}{y}_i)\right|$
266. Pick: $A=I+\frac{B}{2}-1$. Boundary points on a segment: $\gcd (|\Delta x|,|\Delta y|)+1$
267. Triangle: $A=\frac{1}{2}ab\sin C=\sqrt{s(s-a)(s-b)(s-c)}$ (Heron), $s=\frac{a+b+c}{2}$
268. Circumradius $R=\frac{abc}{4A}$, inradius $r=\frac{A}{s}$
269. Law of sines: $\frac{a}{\sin A}=2R$. Law of cosines: $c^2=a^2+b^2-2ab\cos C$
270. Distance from point $P$ to line $AB$: $\frac{|(B-A)\times (P-A)|}{|B-A|}$
271. Line $ax+by+c=0$: distance from $(x_0,y_0)$ is $\frac{|a{x}_0+b{y}_0+c|}{\sqrt{a^2+b^2}}$
272. Rotation by $\theta$: $(x\cos \theta -y\sin \theta ,x\sin \theta +y\cos \theta )$
273. Line intersection: $P=A+(B-A)\frac{(C-A)\times (D-C)}{(B-A)\times (D-C)}$
274. Polygon centroid: $C_x=\frac{1}{6A}\sum (x_i+x_{i+1})(x_i{y}_{i+1}-x_{i+1}{y}_i)$
275. Circle: area $\pi r^2$, sector $\frac{\theta r^2}{2}$, segment $\frac{r^2}{2}(\theta -\sin \theta )$, chord $2r\sin \frac{\theta }{2}$
276. Sphere: $V=\frac{4}{3}\pi r^3$, $S=4\pi r^2$. Cap of height $h$: $V=\frac{\pi h^2(3r-h)}{3}$
277. Cone: $V=\frac{1}{3}\pi r^{2}h$. Cylinder: $V=\pi r^{2}h$
278. Great-circle distance: $d=r\arccos (\sin {\phi }_1\sin {\phi }_2+\cos {\phi }_1\cos {\phi }_2\cos \Delta \lambda )$
279. Manhattan $\leftrightarrow$ Chebyshev: $(x,y)\to (x+y,x-y)$ turns $L_1$ into $L_{\infty }$
280. Convex hull of $n$ random points in a square has $O(\log n)$ vertices. Lattice points of a convex polygon inside $[0,C{]}^2$: $O(C^{2/3})$ hull vertices
281. Number of regions formed by $n$ lines in general position: $\frac{n(n+1)}{2}+1$. Circle with $n$ points, all chords: $\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$
282. 3D: $a\times b=(a_y{b}_z-a_z{b}_y,a_z{b}_x-a_x{b}_z,a_x{b}_y-a_y{b}_x)$, volume of tetrahedron $=\frac{|(b-a)\cdot ((c-a)\times (d-a))|}{6}$

Strings

283. $p$ is a period of $s$ iff $s$ has a border of length $|s|-p$. The smallest period is $n-\pi [n-1]$
284. $s$ is a power of a block iff $p=n-\pi [n-1]$ divides $n$
285. Fine–Wilf: periods $p,q$ with $p+q-\gcd (p,q)\le n$ $\Rightarrow$ $\gcd (p,q)$ is a period
286. Number of distinct substrings $=\sum (n-s{a}_i)-\sum lc{p}_i={\sum }_{v\ne root}(\mathrm{len}(v)-\mathrm{len}(\mathrm{link}(v)))$ in a suffix automaton
287. A string has at most $n$ distinct palindromic substrings (eertree has $\le n+2$ nodes)
288. Polynomial hash collision probability for two fixed strings: $\le \frac{n}{p}$. Among $k$ strings: about $\frac{k^{2}n}{2p}$
289. Number of runs in a string $<n$ (runs theorem)
290. Lyndon factorization is unique (Chen–Fox–Lyndon). Duval finds it in $O(n)$
291. Necklace (minimal rotation) via Booth or Duval on $s+s$

Complexity Limits

292. Roughly $10^8$ simple operations per second
293. $n\le 10$: $O(n!)$ · $n\le 20$: $O(2^{n}n)$ · $n\le 40$: meet in the middle $O(2^{n/2})$ · $n\le 500$: $O(n^3)$ · $n\le 5000$: $O(n^2)$ · $n\le 10^5$: $O(n\sqrt{n})$ · $n\le 10^6$: $O(n\log n)$ · $n\le 10^8$: $O(n)$ · larger: $O(\log n)$ or $O(1)$
294. int $\approx 2.1\cdot 10^9$, long long $\approx 9.2\cdot 10^{18}$, __int128 $\approx 1.7\cdot 10^{38}$
295. double has a 53-bit mantissa (~15–16 digits), long double 64-bit (~18–19 digits)
296. $2^{10}\approx 10^3$, $2^{20}\approx 10^6$, $2^{30}\approx 10^9$, $2^{60}\approx 10^{18}$
297. $10!=3628800$, $12!\approx 4.8\cdot 10^8$, $13!>2^{32}$, $20!\approx 2.4\cdot 10^{18}$ (the largest fitting in long long)
298. $\left(\genfrac{}{}{0ex}{}{30}{15}\right)\approx 1.55\cdot 10^8$, $\left(\genfrac{}{}{0ex}{}{60}{30}\right)\approx 1.18\cdot 10^{17}$
299. Memory: $10^6$ int $\approx 4$ MB, a vector<int> of size $256\cdot 10^6/4$ is 256 MB

Small Tricks

300. Swap without temp: a ^= b, b ^= a, a ^= b
301. Average without overflow: l + (r - l) / 2
302. Round-up division for nonnegative values: (a + b - 1) / b. Floor division for negative numerators: a / b - ((a % b != 0) && ((a < 0) != (b < 0)))
303. Overflow-safe a * b % m for 64-bit: (__int128)a * b % m
304. Compare fractions $\frac{a}{b}<\frac{c}{d}$ (for $b,d>0$) with a * d < c * b
305. Compare $\sqrt{a}+\sqrt{b}$ vs $\sqrt{c}$ by squaring twice, never with floating point near equality
306. Count pairs with sum divisible by $k$: bucket by $a_i\mathrm{mod}k$, pair $r$ with $k-r$
307. Number of subarrays with sum $k$: prefix sums + hashmap of counts
308. Subarrays with XOR $k$: prefix XOR + hashmap
309. For “minimize the maximum”, binary search the answer. For “maximize the minimum”, likewise
310. Contribution technique: count how many times each element is the min/max with monotonic stacks: $(i-L_i)(R_i-i)$
311. ${\sum }_{i<j}{a}_i{a}_j=\frac{(\sum a_i{)}^2-\sum a_i^2}{2}$
312. $\max (a,b)=\frac{a+b+|a-b|}{2}$, $\min (a,b)=\frac{a+b-|a-b|}{2}$
313. $|x_1-x_2|+|y_1-y_2|=\max (|u_1-u_2|,|v_1-v_2|)$ with $u=x+y$, $v=x-y$
314. Median minimizes $\sum |x-a_i|$. Mean minimizes $\sum (x-a_i{)}^2$
315. Sorting by $a_i+b_i$ or by $\frac{a}{b}$ comparators (exchange argument): put $i$ before $j$ iff $f(i,j)<f(j,i)$
316. Coordinates on a grid: $id=r\cdot m+c$, 4-neighbours via dr = {-1,0,1,0}, dc = {0,1,0,-1}
317. Random seed: mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
318. Anti-hash for unordered_map: splitmix64 with a random offset
319. Iterating over all pairs $(i,j)$ with $i\mid j$ up to $n$ costs $O(n\log n)$
320. Two sorted arrays: the $k$-th smallest of their union in $O(\log )$ by binary searching how many come from the first

Inequalities and Approximations

321. AM–GM–HM: $\frac{n}{\sum 1/a_i}\le \sqrt[n]{\prod a_i}\le \frac{\sum a_i}{n}$ for $a_i>0$, equality iff all $a_i$ equal
322. Cauchy–Schwarz: ${\left(\sum a_i{b}_i\right)}^2\le \left(\sum a_i^2\right)\left(\sum b_i^2\right)$
323. Jensen: for convex $f$, $f\left(\frac{\sum a_i}{n}\right)\le \frac{\sum f(a_i)}{n}$ (reverse for concave $f$)
324. Bernoulli’s inequality: $(1+x{)}^r\ge 1+rx$ for $x>-1$ and $r\ge 1$ (or $r\le 0$); reversed for $0\le r\le 1$
325. Triangle inequality: $|a+b|\le |a|+|b|$; $||a|-|b||\le |a-b|$
326. Stirling’s approximation: $n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$, i.e. $\ln n!=n\ln n-n+\frac{1}{2}\ln (2\pi n)+O(1/n)$
327. Power-mean inequality: for $p>q$, ${\left(\frac{\sum a_i^p}{n}\right)}^{1/p}\ge {\left(\frac{\sum a_i^q}{n}\right)}^{1/q}$ (generalises AM–GM, taking $p\to 0$ as the geometric mean)
328. Quadratic formula: $a{x}^2+bx+c=0\Rightarrow x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$; integer roots require $b^2-4ac$ a perfect square

Polynomials, Roots and Symmetric Functions

329. Vieta’s formulas: for ${\prod }_i(x-r_i)=x^n-e_1{x}^{n-1}+e_2{x}^{n-2}-\cdots \pm e_n$, the elementary symmetric function $e_k={\sum }_{|S|=k}{\prod }_{i\in S}{r}_i$ (sum of roots $=e_1$, product $=\pm e_n$)
330. Newton’s identities: power sums $p_k={\sum }_i{r}_i^k$ relate to elementary symmetric $e_k$ by $p_k={\sum }_{i=1}^{k-1}(-1{)}^{i-1}{e}_i{p}_{k-i}+(-1{)}^{k-1}k{e}_k$ — converts between a polynomial’s coefficients and its roots’ power sums without finding the roots
331. Cramer’s rule: for $Ax=b$ with $\det A\ne 0$, $x_i=\det (A_i)/\det (A)$ where $A_i$ replaces column $i$ of $A$ with $b$
332. Trace and eigenvalues: $\mathrm{tr}(A)={\sum }_i{\lambda }_i$, $\det (A)={\prod }_i{\lambda }_i$, both summed/multiplied with multiplicity
333. Discriminant of $a{x}^2+bx+c$ is $b^2-4ac$; of a general polynomial, $\mathrm{disc}(p)=\pm \mathrm{Res}(p,p^{\prime })/a_n$ (resultant with its derivative), zero iff $p$ has a repeated root

More Probability

334. Variance of a sum: $\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)+2\mathrm{Cov}(X,Y)$, $\mathrm{Cov}(X,Y)=E[XY]-E[X]E[Y]$ (reduces to the independent-sum case when $\mathrm{Cov}=0$)
335. Hypergeometric (draw $k$ without replacement from $n$ with $K$ successes): $E=k\frac{K}{n}$, $\mathrm{Var}=k\frac{K}{n}\frac{n-K}{n}\frac{n-k}{n-1}$
336. Poisson($\lambda$): $P(X=k)=\frac{{\lambda }^k{e}^{-\lambda }}{k!}$, $E=\mathrm{Var}=\lambda$; sum of independent Poissons is Poisson with summed rates
337. Union bound: $P\left({\bigcup }_i{A}_i\right)\le {\sum }_{i}P(A_i)$ (no independence needed, slack when events overlap a lot)

More Number Theory

338. Pell’s equation $x^2-d{y}^2=1$ ($d$ not a perfect square): the fundamental solution $(x_1,y_1)$ comes from the continued fraction of $\sqrt{d}$; all solutions are $(x_n,y_n)$ with $x_n+y_n\sqrt{d}=(x_1+y_1\sqrt{d}{)}^n$, i.e. $x_{n+1}=x_1{x}_n+d{y}_1{y}_n,y_{n+1}=x_1{y}_n+y_1{x}_n$
339. Continued fraction convergents $p_k/q_k$ of $[a_0;a_1,a_2,\dots ]$: $p_k=a_k{p}_{k-1}+p_{k-2}$, $q_k=a_k{q}_{k-1}+q_{k-2}$ ($p_{-1}=1,p_{-2}=0,q_{-1}=0,q_{-2}=1$); $p_k{q}_{k-1}-p_{k-1}{q}_k=(-1{)}^{k-1}$, and $p_k/q_k$ is the best rational approximation to the continued fraction’s value among fractions with denominator $\le q_k$
340. $q$-binomial coefficient (Gaussian binomial): ${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q={\prod }_{i=0}^{k-1}\frac{1-q^{n-i}}{1-q^{i+1}}$, counts $k$-dimensional subspaces of ${\mathbb{F}}_q^n$; reduces to $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ as $q\to 1$
341. Möbius function closed form: $\mu (1)=1$; $\mu (n)=(-1{)}^k$ if $n$ is a product of $k$ distinct primes; $\mu (n)=0$ if any prime divides $n$ more than once (not squarefree)

More Graph Theory

342. BEST theorem: the number of Eulerian circuits of a connected directed graph with every ${\mathrm{deg}}^{+}(v)={\mathrm{deg}}^{-}(v)$ is $t_w(G){\prod }_v({\mathrm{deg}}^{+}(v)-1)!$, where $t_w(G)$ is the number of arborescences oriented into any fixed vertex $w$ (same for every choice of $w$) — see Matrix-Tree for $t_w$ and Euler Tours for the full count
343. Erdős–Gallai / handshake extension: the number of edges in any simple graph is at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$; a graph is self-complementary only if $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ is even