Theory.tex

\section{Theory}

% Combinatorics {{{
\Section{Combinatorics}

\Topic{Sums}

\begin{tabular}{l l}
    $\sum_{k=0}^n k = n(n+1)/2$		& ${n \choose k} = \frac{n!}{(n-k)!k!}$ \\
    $\sum_{k=a}^b k = (a+b)(b-a+1)/2$   & ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$ \\
    $\sum_{k=0}^n k^2 = n(n+1)(2n+1)/6$ & ${n+1 \choose k} = \frac{n+1}{n-k+1} {n \choose k}$   \\
    $\sum_{k=0}^n k^3 = n^2(n+1)^2/4$   & ${n \choose k+1} = \frac{n-k}{k+1} {n \choose k}$     \\
    $\sum_{k=0}^n k^4 = (6n^5 + 15n^4 + 10n^3 - n)/30$  & ${n \choose k} = \frac{n}{n-k} {n-1 \choose k}$       \\
    $\sum_{k=0}^n k^5 = (2n^6 + 6n^5 + 5n^4 - n^2)/12$  & ${n \choose k} = \frac{n-k+1}{k} {n \choose k-1}$     \\
    $\sum_{k=0}^n x^k = (x^{n+1} - 1)/(x - 1)$  & $12! \approx 2^{28.8}$ \\
    $\sum_{k=0}^n kx^k = (x - (n+1)x^{n+1} + nx^{n+2})/(x-1)^2$	& $20! \approx 2^{61.1}$ \\
    $1 + x + x^2 + \dots = 1 / (1 - x)$
\end{tabular}

%$(x+a)^{-n} = \sum_{k=0}^{\infty} {-n \choose k} x^k a^{-n-k}$ \\
%$(x+y)^z = \sum_{k=0}^{\infty} {z \choose k} x^k y^{z-k}$,\\
%with ${z \choose k} = \frac{z\dots(z-k+1)}{k!}$.

\Topic{Binomial coefficients}

\begin{tabular}{r|rrrrrrrrrrrrr}
    & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$ \\
    \hline
    $0$ & $1$\\
    $1$ & $1$ & $1$\\
    $2$ & $1$ & $2$ & $1$\\
    $3$ & $1$ & $3$ & $3$ & $1$\\
    $4$ & $1$ & $4$ & $6$ & $4$ & $1$\\
    $5$ & $1$ & $5$ & $10$ & $10$ & $5$ & $1$\\
    $6$ & $1$ & $6$ & $15$ & $20$ & $15$ & $6$ & $1$\\
    $7$ & $1$ & $7$ & $21$ & $35$ & $35$ & $21$ & $7$ & $1$\\
    $8$ & $1$ & $8$ & $28$ & $56$ & $70$ & $56$ & $28$ & $8$ & $1$\\
    $9$ & $1$ & $9$ & $36$ & $84$ & $126$ & $126$ & $84$ & $36$ & $9$ & $1$\\
    $10$ & $1$ & $10$ & $45$ & $120$ & $210$ & $252$ & $210$ & $120$ & $45$ & $10$ & $1$\\
    $11$ & $1$ & $11$ & $55$ & $165$ & $330$ & $462$ & $462$ & $330$ & $165$ & $55$ & $11$ & $1$\\
    $12$ & $1$ & $12$ & $66$ & $220$ & $495$ & $792$ & $924$ & $792$ & $495$ & $220$ & $66$ & $12$ & $1$ \\
    \hline
    & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$
\end{tabular}

Number of ways to pick a multiset of size $k$ from $n$ elements: ${n+k-1 \choose k}$ \\
Number of $n$-tuples of non-negative integers with sum $s$:
${{s+n-1} \choose {n-1}}$, at most $s$: ${{s + n} \choose {n}}$ \\
Number of $n$-tuples of positive integers with sum $s$:
${{s-1} \choose {n-1}}$ \\
Number of lattice paths from $(0,0)$ to $(a,b)$, restricted to east and north
steps: ${a+b \choose a}$

\Topic{Multinomial theorem}.
$(a_1+\dots+a_k)^n = \sum {n \choose n_1,\dots,n_k} a_1^{n_1} \dots a_k^{n_k}$,
where $n_i \ge 0$ and $\sum n_i=n$. \\
$${n \choose n_1,\dots,n_k} = M(n_1,\dots,n_k) = \frac{n!}{n_1! \dots n_k!}$$
$$M(a,\dots,b,c,\dots) = M(a+\dots+b,c,\dots) M(a,\dots,b)$$

\Topic{Catalan numbers}.
$C_n = \frac{1}{n+1} {2n \choose n}$.
\quad $C_0=1$, $C_n=\sum_{i=0}^{n-1} C_i C_{n-1-i}$.
\quad $C_{n+1} = C_n \frac{4n+2}{n+2}$. \\
$C_0, C_1, \ldots = 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,
		58786, 208012, 742900, \ldots$ \\
%\quad GF: $\frac{1-\sqrt{1-4x}}{2x}=\sum_{n=0}^{\infty} C_n x^n$. \\
$C_n$ is the number of:
properly nested sequences of $n$ pairs of parentheses;
rooted ordered binary trees with $n+1$ leaves;
triangulations of a convex $(n+2)$-gon.

\Topic{Derangements}.
Number of permutations of $n=0,1,2,\dots$ elements without fixed points is
$1, 0, 1, 2, 9, 44, 265, 1854, 14833, \dots$
Recurrence: $D_n = (n-1)(D_{n-1} + D_{n-2}) = n D_{n-1} + (-1)^n$.
Corollary: number of permutations with exactly $k$ fixed points is ${n \choose k} D_{n-k}$.

\Topic{Stirling numbers of $1^{st}$ kind}.
$s_{n,k}$ is $(-1)^{n-k}$ times the number of permutations of $n$ elements with
exactly $k$ permutation cycles.
$|s_{n,k}| = |s_{n-1,k-1}| + (n-1) |s_{n-1,k}|$. \quad
$\sum_{k=0}^n s_{n,k}\,x^k = x^{\underline n}$

% Number of permutations of $n$ elements with exactly $k$ cycles,
% all of length $\ge r$: \\
% $d_r(n,k) = (n-1) d_r(n-1,k) + (n-1)^{\underline {r-1}}\ d_r(n-r,k-1),
% \quad d_r(n,k)=0 $ for $ n\le kr-1, \quad d_r(n,1)=(n-1)!$.

\Topic{Stirling numbers of $2^{nd}$ kind}.
$S_{n,k}$ is the number of ways to partition a set of $n$ elements into
exactly $k$ non-empty subsets.
$S_{n,k} = S_{n-1,k-1} + k S_{n-1,k}$.
$S_{n,1} = S_{n,n} = 1$.
$x^n = \sum_{k=0}^n S_{n,k}\,x^{\underline k}$

\Topic{Bell numbers}.
$B_n$ is the number of partitions of $n$ elements.
$B_0, \ldots = 1,1,2,5,15,52,203,\ldots$ \\
$B_{n+1} = \sum_{k=0}^n {n \choose k} B_k = \sum_{k=1}^n S_{n,k}$.
Bell triangle: $B_r=a_{r,1}=a_{r-1,r-1}$, $a_{r,c}=a_{r-1,c-1}+a_{r,c-1}$.
%Bell triangle: 1, 1 2, 2 3 5, 5 7 10 15, 15 20 27 37 52, (last) ... (left + left above).

\Topic{Bernoulli numbers}.
%GF: $\frac{x}{e^x - 1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}$. \quad
$\sum_{k=0}^{m-1} k^n =
\frac{1}{n+1} \sum_{k=0}^n {n+1 \choose k} B_k m^{n+1-k}$. \\
$\sum_{j=0}^m {m+1 \choose j} B_j = 0$.
\quad $B_0=1$, $B_1=-\frac{1}{2}$. $B_n=0$, for all odd $n \ne 1$.

%\Topic{Pentagonal theorem}.
%$\prod_{k=1}^{\infty} (1-x^k) = \sum_{n=-\infty}^{\infty} (-1)^n x^{n(3n+1)/2}$.
%$\sum_{n=0}^{\infty}p(n) x^n = \prod_{k=1}^{\infty} \left(\frac{1}{1-x^k}\right) = (\sum x^i)(\sum x^{2i})(\sum x^{3i}) \dots$ \\
%$p(0) = 1$, $p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) - \dots = 0$ ($+,+,-,-$ goes on; same for $s(n)$, but $s(0)\to n$.)

\Topic{Eulerian numbers}.
$E(n,k)$ is the number of permutations with exactly
$k$ descents ($i: \pi_i < \pi_{i+1}$) /
ascents ($\pi_i > \pi_{i+1}$) /
excedances ($\pi_i > i$) /
$k+1$ weak excedances ($\pi_i \ge i$). \\
Formula: $E(n,k)=(k+1)E(n-1,k)+(n-k)E(n-1,k-1)$. \quad
$x^n = \sum_{k=0}^{n-1} E(n,k) {x+k \choose n}$.

\Topic{Burnside's lemma}.
The number of orbits under group $G$'s action on set $X$:\\
$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X_g|$,
where $X_g=\{ x \in X: g(x)=x \}$. (``Average number of fixed points.'') \\
Let $w(x)$ be weight of $x$'s orbit. Sum of all orbits' weights:
$\sum_{o \in X/G} w(o) = \frac{1}{|G|} \sum_{g \in G} \sum_{x \in X_g} w(x)$.

%\Topic{Number of $k$-ary necklaces}.
%$\frac{1}{n}\sum_{d|n} \phi(\frac{n}{d}) k^d$. \\
%\Topic{Number of Lyndon words} (aperiodic necklaces).
%$\frac{1}{n}\sum_{d|n} \mu(\frac{n}{d}) k^d$.

%De Bruijn sequences over alphabet of size $k$, containing all $n$-substrings.
%Length: $n^k$. Number: ${k!}^{k^{n-1}} / k^n$.

% }}}

% Number Theory {{{
\Section{Number Theory}

\Topic{Linear diophantine equation}. $ax+by=c$.
Let $d=\gcd(a,b)$. A solution exists iff $d|c$.
If $(x_0,y_0)$ is any solution, then all solutions are given by
$(x,y) = (x_0 + \frac{b}{d}t, y_0 - \frac{a}{d}t)$, $t \in {\mathbb Z}$.
To find some solution $(x_0, y_0)$, use extended GCD to solve
$ax_0 + by_0 = d = \gcd(a, b)$, and multiply its solutions by $\frac{c}{d}$.

Linear diophantine equation in $n$ variables:
$a_1 x_1 + \dots + a_n x_n = c$ has solutions iff $\gcd(a_1, \dots, a_n) | c$.
To find some solution, let $b=\gcd(a_2, \dots, a_n)$,
solve $a_1 x_1 + by = c$, and iterate with $a_2 x_2 + \dots = y$.

\Topic{Extended GCD}
\begin{verbatim}
// Finds g = gcd(a,b) and x, y such that ax+by=g.
// Bounds: |x|<=b+1, |y|<=a+1.
void gcdext(int &g, int &x, int &y, int a, int b)
{ if (b == 0) { g = a; x = 1; y = 0; }
  else        { gcdext(g, y, x, b, a % b); y = y - (a / b) * x; } }
\end{verbatim}

Multiplicative inverse of $a$ modulo $m$:
$x$ in $ax + my = 1$, or $a^{\phi(m)-1} \pmod{m}$.

\Topic{Chinese Remainder Theorem}.
System $x \equiv a_i \pmod{m_i}$ for $i=1,\dots,n$, with
pairwise relatively-prime $m_i$ has a unique solution modulo $M = m_1 m_2 \dots m_n$:
$x = a_1 b_1 \frac{M}{m_1} + \dots + a_n b_n \frac{M}{m_n} \pmod{M}$,
where $b_i$ is modular inverse of $\frac{M}{m_i}$ modulo $m_i$.

%\Topic{Generalized CRT}.
System $x \equiv a \pmod{m}$, $x \equiv b \pmod{n}$ has solutions
iff $a \equiv b \pmod{g}$, where $g=\gcd(m,n)$.
The solution is unique modulo $L=\frac{mn}{g}$, and equals:
$x \equiv a + T(b-a) m/g \equiv b + S(a-b) n/g \pmod{L}$,
where $S$ and $T$ are integer solutions of $mT + nS = \gcd(m,n)$.

\Topic{Prime-counting function}. $\pi(n) = |\{p \le n : p \hbox{ is prime}\}|$.
$n/\ln(n) < \pi(n) < 1.3 n/\ln(n)$.
$\pi(1000) = 168$, $\pi(10^6) = 78498$, $\pi(10^9) = 50\ 847\ 534$.
\quad $n$-th prime $\approx n \ln n$.

\Topic{Miller-Rabin's primality test}.
Given $n = 2^r s + 1$ with odd $s$, and a random integer $1 < a < n$. \\
If $a^s \equiv 1 {\pmod n}$ or $a^{2^j s} \equiv -1 {\pmod n}$ for some
$0 \le j \le r-1$, then $n$ is a probable prime.
With bases 2, 7 and 61, the test indentifies all composites below $2^{32}$.
Probability of failure for a random $a$ is at most 1/4.

\Topic{Pollard-$\rho$}.
Choose random $x_1$, and let $x_{i+1} = x_i^2 - 1 \pmod{n}$.
Test $\gcd(n, x_{2^k+i} - x_{2^k})$ as possible $n$'s factors for $k=0,1,\ldots$
Expected time to find a factor: $O(\sqrt{m})$, where $m$ is smallest
prime power in $n$'s factorization.
That's $O(n^{1/4})$ if you check $n = p^k$ as a special case before factorization.

\Topic{Fermat primes}.  A Fermat prime is a prime of form $2^{2^n}+1$.
The only known Fermat primes are 3, 5, 17, 257, 65537.
A number of form $2^n+1$ is prime only if it is a Fermat prime.

%\Topic{Mersenne primes}.  A Mersenne prime is a prime of form $2^n-1$.
%Known Mersenne primes correspond to (necessarily prime) indexes
%2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,
%2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
%21701, 23209, 44497, 86243, 110503, 132049, 216091,
%756839, 859433, 1257787, 1398269, 2976221, 3021377,
%6972593, 13466917.

\Topic{Perfect numbers}.  $n>1$ is called perfect if it equals
sum of its proper divisors and $1$.  Even $n$ is perfect iff $n = 2^{p-1} (2^p - 1)$
and $2^p - 1$ is prime (Mersenne's). No odd perfect numbers are yet found.

\Topic{Carmichael numbers}.
A positive composite $n$ is a Carmichael number
($a^{n-1} \equiv 1 \pmod{n}$ for all $a$: $\gcd(a,n)=1$),
iff $n$ is square-free, and for all prime divisors $p$ of $n$, $p-1$ divides $n-1$.

\Topic{Number/sum of divisors}.
$\tau(p_1^{a_1} \dots p_k^{a_k}) = \prod_{j=1}^k (a_j+1)$. \quad
$\sigma(p_1^{a_1} \dots p_k^{a_k}) = \prod_{j=1}^k \frac{p_j^{a_j+1}-1}{p_j-1}$.

\Topic{Euler's phi function}.
$\phi(n)=|\{m \in {\mathbb N}, m \le n, \gcd(m, n) = 1 \}|$. \\
$\phi(mn) = \frac{\phi(m) \phi(n) \gcd(m,n)}{\phi(\gcd(m,n))}$. \quad
$\phi(p^a) = p^{a-1} (p-1)$. \quad
$\sum_{d|n} \phi(d) = \sum_{d|n} \phi(\frac{n}{d}) = n$.

%\Topic{Fermat's theorem}.  $a^p \equiv a \pmod{p}$ if $p$ is prime. \\
%For any polynomial $f(x)$ with integer coefficients and prime $p$,
%$f(x)^{p^n} \equiv f(x^{p^n}) \pmod{p}$
\Topic{Euler's theorem}. $a^{\phi(n)} \equiv 1\pmod{n}$, if $\gcd(a,n)=1$. \\
\Topic{Wilson's theorem}. $p$ is prime iff $(p - 1)! \equiv -1 \pmod p$.

\Topic{Mobius function}.
$\mu(1) = 1$. $\mu(n) = 0$, if $n$ is not squarefree.
$\mu(n) = (-1)^s$, if $n$ is the product of $s$ distinct primes.
Let $f$, $F$ be functions on positive integers.
If for all $n \in N$, $F(n)=\sum_{d|n} f(d)$, then $f(n) = \sum_{d|n} \mu(d) F(\frac{n}{d})$,
and vice versa. \quad
$\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}$.
\quad $\sum_{d|n} \mu(d) = 1$. \\
If $f$ is multiplicative, then $\sum_{d|n} \mu(d) f(d) = \prod_{p|n}(1-f(p))$,
$\sum_{d|n} \mu(d)^2 f(d) = \prod_{p|n} (1+f(p))$.

\Topic{Legendre symbol}. If $p$ is an odd prime, $a \in {\mathbb Z}$, then
$\left(\frac{a}{p}\right)$ equals $0$, if $p | a$; $1$ if $a$ is a quadratic
residue modulo $p$; and $-1$ otherwise.
Euler's criterion:
$\left(\frac{a}{p}\right)=a^{\left(\frac{p-1}{2}\right)} \pmod p$. \\
%$\left(\frac{a}{p}\right) \left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)$
%Law of Quadratic Reciprocity: for any distinct odd primes $p$ and $q$,
%$\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$
\Topic{Jacobi symbol}.  %Generalization of Legendre's symbol to any odd modulus. \\
If $n=p_1^{a_1} \cdots p_k^{a_k}$ is odd, then
$\left(\frac{a}{n}\right) = \prod_{i=1}^k \left(\frac{a}{p_i}\right)^{k_i}$.

%\Topic{Kronecker symbol}.
%Let $a$ be a positive integer, which is not a perfect square and
%$a \equiv 0$ or $1 {\pmod 4}$. \\
%$\left(\frac{a}{2}\right) = \{ 1$, if $a \equiv 1 {\pmod 8}$;
%$-1$, if $a \equiv 5 {\pmod 8} \}$. \\
%$\left(\frac{a}{n}\right) = \prod_{j=1}^k p_j^{k_j}$,
%if gcd$(a,n) \ne 1$ and $n=\prod p_i^{k_i}$.
%$\left(\frac{a}{n}\right)$ equals Jacobi symbol otherwise.

\Topic{Primitive roots}.  If the order of $g$ modulo $m$ (min $n>0$:
$g^n \equiv 1 \pmod{m}$) is $\phi(m)$, then $g$ is called a primitive root.
If $Z_m$ has a primitive root, then it has $\phi(\phi(m))$ distinct primitive
roots. $Z_m$ has a primitive root iff $m$ is one of $2$, $4$,
$p^k$, $2p^k$, where $p$ is an odd prime.
If $Z_m$ has a primitive root $g$, then for all $a$ coprime to $m$,
there exists unique integer $i=\text{ind}_g(a)$ modulo $\phi(m)$,
such that $g^i \equiv a \pmod{m}$.
$\text{ind}_g(a)$ has logarithm-like properties:
$\text{ind}(1) = 0$, $\text{ind}(ab) = \text{ind}(a) + \text{ind}(b)$.

If $p$ is prime and $a$ is not divisible by $p$, then congruence
$x^n \equiv a \pmod{p}$ has $\gcd(n, p-1)$ solutions if
$a^{(p-1)/\gcd(n,p-1)} \equiv 1 \pmod{p}$, and no solutions otherwise.
(Proof sketch: let $g$ be a primitive root, and
$g^i \equiv a \pmod{p}$, $g^u \equiv x \pmod{p}$.
$x^n \equiv a \pmod{p}$ iff $g^{nu} \equiv g^i \pmod{p}$ iff $nu \equiv i \pmod{p}$.)

\Topic{Discrete logarithm problem}.  Find $x$ from $a^x \equiv b \pmod{m}$.
Can be solved in $O(\sqrt{m})$ time and space with a meet-in-the-middle trick.
Let $n = \lceil \sqrt{m} \rceil$, and $x = ny - z$.
Equation becomes $a^{ny} \equiv b a^z \pmod{m}$.  Precompute all values that
the RHS can take for $z = 0, 1, \dots, n-1$, and brute force $y$ on the LHS,
each time checking whether there's a corresponding value for RHS.

\Topic{Pythagorean triples}.  Integer solutions of $x^2 + y^2 = z^2$
All relatively prime triples are given by:
$x=2mn, y=m^2-n^2, z=m^2+n^2$ where $m>n, \gcd(m,n)=1$ and $m \not\equiv n \pmod{2}$.
All other triples are multiples of these.
Equation $x^2 + y^2 = 2z^2$ is equivalent to $(\frac{x+y}{2})^2 + (\frac{x-y}{2})^2 = z^2$.

\Topic{Postage stamps/McNuggets problem}.  Let $a$, $b$ be relatively-prime integers.
There are exactly $\frac{1}{2}(a-1)(b-1)$ numbers \emph{not} of form $ax+by$ ($x,y \ge 0$),
and the largest is $(a-1)(b-1)-1 = ab - a - b$.

\Topic{Fermat's two-squares theorem}.  Odd prime $p$ can be represented
as a sum of two squares iff $p \equiv 1 {\pmod 4}$.
A product of two sums of two squares is a sum of two squares.
Thus, $n$ is a sum of two squares iff every prime of
form $p=4k+3$ occurs an even number of times in $n$'s factorization.

\Topic{RSA}. Let $p$ and $q$ be random distinct large primes, $n = pq$.
Choose a small odd integer $e$, relatively prime to $\phi(n) = (p-1)(q-1)$,
and let $d = e^{-1} \pmod{\phi(n)}$. Pairs $(e,n)$ and $(d,n)$ are
the public and secret keys, respectively.
Encryption is done by raising a message $M \in Z_n$ to the power $e$ or $d$,
modulo $n$.

% }}}

% String Algorithms {{{

\Section{String Algorithms}

\Topic{Burrows-Wheeler inverse transform}.
Let $B[1..n]$ be the input (last column of sorted matrix of string's rotations.)
Get the first column, $A[1..n]$, by sorting $B$.
For each $k$-th occurence of a character $c$ at index $i$ in $A$,
let $next[i]$ be the index of corresponding $k$-th occurence of $c$ in $B$.
The $r$-th fow of the matrix is $A[r]$, $A[next[r]]$, $A[next[next[r]]]$, ...

\Topic{Huffman's algorithm}.  Start with a forest, consisting of isolated
vertices.  Repeatedly merge two trees with the lowest weights.
% }}}

% Graph Theory {{{
\Section{Graph Theory}

\Topic{Euler's theorem}. For any planar graph, $V - E + F = 1 + C$,
where $V$ is the number of graph's vertices, $E$ is the number of edges,
$F$ is the number of faces in graph's planar drawing, and $C$ is the number
of connected components.  Corollary: $V - E + F = 2$ for a 3D polyhedron.

%\Topic{Schlafli's}. A convex polyhedron in $R^n$, which has $N_0$ vertices, $N_1$ edges,
%$N_i$ $i$-dimensional faces, satisfies: $N_0-N_1+N_2-\dots=1-(-1)^n$.

\Topic{Vertex covers and independent sets}.
Let $M$, $C$, $I$ be a max matching, a min vertex cover, and a max independent set.
Then $|M| \le |C| = N - |I|$, with equality for bipartite graphs.
Complement of an MVC is always a MIS, and vice versa.
Given a bipartite graph with partitions $(A, B)$, build a network:
connect source to $A$, and $B$ to sink with edges of capacities, equal to
the corresponding nodes' weights, or $1$ in the unweighted case.
Set capacities of the original graph's edges to the infinity.
Let $(S,T)$ be a minimum $s$-$t$ cut.
Then a maximum(-weighted) independent set is $I = (A \cap S) \cup (B \cap T)$,
and a minimum(-weighted) vertex cover is $C = (A \cap T) \cup (B \cap S)$.

\Topic{Matrix-tree theorem}.
Let matrix $T = [t_{ij}]$, where $t_{ij}$ is the number of multiedges
between $i$ and $j$, for $i \ne j$, and $t_{ii} = -\mbox{deg}_i$.
Number of spanning trees of a graph is equal to the determinant of
a matrix obtained by deleting any $k$-th row and $k$-th column from $T$.
%If $G$ is a multigraph and $e$ is an edge of $G$, then the number $\tau(G)$ of
%spanning trees of $G$ satisfies recurrence $\tau(G) = \tau(G-e) + \tau(G/e)$,
%when $G-e$ is the multigraph obtained by deleting $e$, and $G/e$ is
%the contraction of $G$ by $e$ (multiple edges arising from the contraction
%are preserved.)

\Topic{Euler tours}.
Euler tour in an undirected graph exists iff the graph is connected and each
vertex has an even degree.  Euler tour in a directed graph exists iff in-degree
of each vertex equals its out-degree, and underlying undirected graph is connected.
%Open Euler path exists if it's possible to make the graph Eulerian by adding a single edge.
Construction:
\vspace{-5mm}
\begin{verbatim}
    doit(u):
      for each edge e = (u, v) in E, do: erase e, doit(v)
      prepend u to the list of vertices in the tour
\end{verbatim}
\vspace{-2mm}

\Topic{Stable marriages problem}.
While there is a free man $m$: let $w$ be the most-preferred woman to whom he
has not yet proposed, and propose $m$ to $w$. If $w$ is free, or is engaged to someone whom
she prefers less than $m$, match $m$ with $w$, else deny proposal.

\Topic{Stoer-Wagner's min-cut algorithm}.
Start from a set $A$ containing an arbitrary vertex.
While $A \ne V$, add to $A$ the most tightly connected vertex
($z \notin A$ such that $\sum_{x \in A} w(x, z)$ is maximized.)
Store cut-of-the-phase (the cut between the last added vertex and rest of
the graph), and merge the two vertices added last.  Repeat until the graph
is contracted to a single vertex.  Minimum cut is one of the cuts-of-the-phase.

\Topic{Tarjan's offline LCA algorithm}. (Based on DFS and union-find structure.)
\begin{verbatim}
    DFS(x):
      ancestor[Find(x)] = x
      for all children y of x:
         DFS(y); Union(x, y); ancestor[Find(x)] = x
      seen[x] = true
      for all queries {x, y}:
        if seen[y] then output "LCA(x, y) is ancestor[Find(y)]"
\end{verbatim}

\Topic{Strongly-connected components}. Kosaraju's algorithm. \\
1. Let $G^T$ be a transpose $G$ (graph with reversed edges.) \\
1. Call DFS($G^T$) to compute finishing times $f[u]$ for each vertex $u$. \\
3. For each vertex $u$, in the order of decreasing $f[u]$, perform DFS($G$, $u$). \\
4. Each tree in the 3rd step's DFS forest is a separate SCC.

\Topic{2-SAT}. Build an implication graph with 2 vertices for each
variable -- for the variable and its inverse; for each clause $x \lor y$
add edges $({\overline x}, y)$ and $({\overline y}, x)$.
The formula is satisfiable iff $x$ and ${\overline x}$ are in distinct SCCs,
for all $x$. To find a satisfiable assignment, consider the graph's SCCs
in topological order from sinks to sources (i.e. Kosaraju's last step), assigning `true' to
all variables of the current SCC (if it hasn't been previously
assigned `false'), and `false' to all inverses.

\Topic{Randomized algorithm for non-bipartite matching}.
Let $G$ be a simple undirected graph with even $|V(G)|$.
Build a matrix $A$, which for each edge $(u,v) \in E(G)$ has
$A_{i,j}=x_{i,j}$, $A_{j,i}=-x_{i,j}$, and is zero elsewhere.
Tutte's theorem: $G$ has a perfect matching iff $\det G$ (a multivariate
polynomial) is identically zero.
Testing the latter can be done by computing the determinant for
a few random values of $x_{i,j}$'s over some field.
(e.g. $Z_p$ for a sufficiently large prime $p$)

\Topic{Prufer code of a tree}.
Label vertices with integers $1$ to $n$.
Repeatedly remove the leaf with the smallest label, and output its only
neighbor's label, until only one edge remains. The sequence has
length $n-2$.  Two isomorphic trees have the same sequence, and every sequence
of integers from $1$ and $n$ corresponds to a tree.
Corollary: the number of labelled trees with $n$ vertices is $n^{n-2}$.  % Cayley's theorem

\Topic{Erdos-Gallai theorem}.
A sequence of integers $\{ d_1, d_2, \dots, d_n \}$,
with $n-1 \ge d_1 \ge d_2 \ge \dots \ge d_n \ge 0$ is a degree sequence
of some undirected simple graph iff $\sum d_i$ is even and
$d_1 + \dots + d_k \le k(k-1) + \sum_{i=k+1}^n \min(k, d_{i})$
for all $k=1,2,\dots,n-1$.

% }}}

% Games {{{

\Section{Games}

\Topic{Grundy numbers}.
For a two-player, normal-play (last to move wins) game on a graph $(V,E)$:
$G(x) = \mbox{mex}(\{ G(y) : (x, y) \in E \})$,
where $\mbox{mex}(S) = \min \{ n \ge 0: n \not\in S \}$.
$x$ is losing iff $G(x) = 0$.

\Topic{Sums of games}.

\vspace{-4mm}
\begin{itemize}
  \item
    \emph{Player chooses a game and makes a move in it}.
    Grundy number of a position is xor of grundy numbers of positions in summed games.
  \item
    \emph{Player chooses a non-empty subset of games (possibly, all) and makes moves in all of them}.
    A position is losing iff each game is in a losing position.
  \item
    \emph{Player chooses a proper subset of games (not empty and not all),
        and makes moves in all chosen ones.}
    A position is losing iff grundy numbers of all games are equal.
  \item
    \emph{Player must move in all games, and loses if can't move in some game}.
    A position is losing if any of the games is in a losing position.
\end{itemize}
% http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames

\vspace{-3mm}

\Topic{Mis\`{e}re Nim}.
A position with pile sizes $a_1, a_2, \dots, a_n \ge 1$,
not all equal to $1$, is losing iff $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$
(like in normal nim.)
A position with $n$ piles of size $1$ is losing iff $n$ is \emph{odd}.

% }}}

% Bit Tricks {{{

\Section{Bit tricks}
Clearing the lowest 1 bit: \verb$x & (x - 1)$, all trailing 1's: \verb$x & (x + 1)$ \\
Setting the lowest 0 bit: \verb$x | (x + 1)$ \\
Enumerating subsets of a bitmask $m$: \\
\verb|x=0; do { ...; x=(x+1+~m)&m; } while (x!=0);| \\
\verb$__builtin_ctz/__builtin_clz$ returns the number of trailing/leading zero bits. \\
\verb$__builtin_popcount(unsigned x)$ counts 1-bits (slower than table lookups). \\
For 64-bit unsigned integer type, use the suffix `\verb$ll$', i.e. \verb$__builtin_popcountll$.

% }}}

% Math {{{
\Section{Math}

\Topic{Stirling's approximation}
$z! = \Gamma(z+1) = \sqrt{2 \pi}\ z^{z+1/2}\ e^{-z}
(1 + \frac{1}{12z} + \frac{1}{288 z^2} - \frac{139}{51840 z^3} + \dots)$
%$\ln \Gamma(z) = \frac{1}{2} \ln(2 \pi) + (z - \frac{1}{2}) \ln z - z + \sum_{n=1}^{\infty} \frac{B_{2n}}{2n(2n-1)} z^{-(2n-1)}$.
%$\sum = \frac{1}{12 z} - \frac{1}{360 z^3} + \frac{1}{1260 z^5} - \dots$

\Topic{Taylor series}.
$f(x) = f(a) + \frac{x-a}{1!} f'(a) + \frac{(x-a)^2}{2!} f^{(2)}(a) + \dots + \frac{(x-a)^n}{n!} f^{(n)}(a) + \dots$. \\
$\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!} + \dots$ \\
$\ln x = 2(a+\frac{a^3}{3}+\frac{a^5}{5}+\dots)$, where $a=\frac{x-1}{x+1}$. $\ln x^2 = 2 \ln x$. \\
$\arctan x = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + \dots$,
$\arctan x = \arctan c + \arctan \frac{x-c}{1+xc}$ (e.g c=.2) \\
$\pi = 4 \arctan 1$, $\pi = 6 \arcsin \frac{1}{2}$

% }}}