codebook.tex

% Compiled and edited by Brian Bi
\documentclass[12pt]{extarticle}
\setlength{\parindent}{0.0in}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage[landscape,a4paper,twoside=false,top=15mm,bottom=10mm,left=8mm,right=8mm]{geometry}
\pagestyle{myheadings}
\markright{}
\usepackage{listings}
\usepackage{color}

\usepackage{titlesec}
\titlespacing{\section}{0pt}{*1}{*1}

\titleformat{\section}[block]
  {\titlerule\addvspace{4pt}\normalfont\Large\bfseries}
  {\thesection\enspace}
  {0pt}
  {}
  []

\titleformat{\subsection}[block]
  {\titlerule\addvspace{4pt}\normalfont\large\bfseries}
  {\thesubsection\enspace}
  {0pt}
  {}
  [\vspace{4pt}\titlerule]
  
% \titleformat{\section}
%   {\normalfont\Large\bfseries}{\thesection}{1em}{}[{\titlerule[0.8pt]}]
% \titleformat{\subsection}
%   {\normalfont\large\bfseries}{\thesubsection}{1em}{}[{\titlerule[0.4pt]}]

% \titlespacing{\subsection}{0pt}{*0}{*0}

\lstset{
	tabsize=2,
	basicstyle=\fontsize{12}{12}\ttfamily,
    %upquote=true,
    aboveskip={0\baselineskip},
    columns=fixed,
    showstringspaces=false,
    extendedchars=true,
    breaklines=true, 
    prebreak = \raisebox{0ex}[0ex][0ex]{\ensuremath{\hookleftarrow}},
    % frame=single,
    \setlength{\columnseprule}{1pt}, 
    rulecolor=\color[rgb]{0.75,0.75,0.75},
    showtabs=false,
    showspaces=false,
    showstringspaces=false,
    keywordstyle=\color[rgb]{0,0,1},
    commentstyle=\color[rgb]{0.133,0.545,0.133},
    stringstyle=\color[rgb]{0.627,0.126,0.941},
}

\pagestyle{fancy}
\fancyhead[L]{RuntimeTerror - IIIT-Delhi}
\fancyhead[R]{\thepage}
\fancyfoot[C]{}

\begin{document}
% Disable balancing of columns on last page, which is ugly
\begin{multicols*}{2}
% Want compact table of contents, but normal spacing between paragraphs later on
\setlength{\parskip}{0.0in}
% \tableofcontents % To remove Contents
\setlength{\parskip}{0.0in}
% New codebook
\section{Flow and matching}

\subsection{Max flow (Dinic)} % Stanford
\lstinputlisting[language=c++]{dinic.cpp}

\subsection{Min-cost max-flow}
\lstinputlisting[language=c++]{MinCostMaxFlow.cpp}

\subsection{Max Bipartite Matching (Hopcroft-Karp)} % Stanford
\lstinputlisting[language=c++]{bipartite.cpp}

\subsection{General Matching} % Stanford
\lstinputlisting[language=c++]{GeneralMatching.cpp}


\section{Geometry}

\subsection{Miscellaneous Geometry} % Stanford
\lstinputlisting[language=c++]{geom-2d.cpp}


\subsection{Convex hull} % Brian Bi
\lstinputlisting[language=c++]{monotone.cpp}

\subsection{Pick's Theorem (Text)} % Wesley May
For a polygon with all vertices on lattice points, $A = i + b/2 - 1$, where $A$
is the area, $i$ is the number of lattice points strictly within the polygon,
and $b$ is the number of lattice points on the boundary of the polygon.

\section{Math Algorithms}

\subsection{Sieve} % Jimmy Mårdell (Yarin)
\lstinputlisting[language=c++]{yarin.cpp}

\subsection{Modular arithmetic and linear Diophantine solver} % Stanford
\lstinputlisting[language=c++]{modular.cpp}

\subsection{Gaussian elimination} % Stanford
\lstinputlisting[language=c++]{RREF.cpp}

% \subsection{Solving linear systems (Text)} % Brian Bi
% To solve a general system of linear equations, put it into matrix form and
% compute the reduced row echelon form. For example,
% \begin{align*}2x + y &= 5 \\ 3x + 2y &= 6\end{align*}
% corresponds to the matrix
% \[ \left[ \begin{array}{cc|c} 2 & 1 & 5 \\ 3 & 2 & 6 \end{array} \right] \]
% with RREF
% \[ \left[ \begin{array}{cc|c} 1 & 0 & 4 \\ 0 & 1 & -3 \end{array} \right] \]
% After row reduction, if any row has a 1 in the rightmost column and 0
% everywhere else, then the system is inconsistent and has no solution.
% Otherwise, to find a solution, set the variable corresponding to the leftmost 1
% in each column equal to the corresponding value in the rightmost column, and
% set all other variables to 0. Ignore rows consisting entirely of 0. The
% solution is unique iff the rank of the matrix equals the number of variables.

\subsection{Fast Fourier transform (FFT)} % Stanford
\lstinputlisting[language=c++]{fft.cpp}

\subsection{Pollard rho and (Rabin-Miller)} % Qiyu Zhu
\lstinputlisting[language=c++]{pollard-rho.cpp}

\subsection{Euler's Totient} % Andre Hahn Pereira
\lstinputlisting[language=c++]{totient.cpp}

\section{Graphs}

\subsection{Strongly connected components} % Stanford (modified by Brian Bi)
\lstinputlisting[language=c++]{scc.cpp}

\subsection{Bridges} % Andre Hahn Pereira
\lstinputlisting[language=c++]{bridges.cpp}

\subsection{Bellman Ford}
\lstinputlisting[language=c++]{BellmanFord.cpp}

% \subsection{Dijkstra}
% \lstinputlisting[language=c++]{dijkstra.cpp}

% \subsection{Floyd Warshall}
% \lstinputlisting[language=c++]{FloydWarshall.cpp}

% \subsection{Kruskal(MST)}
% \lstinputlisting[language=c++]{KruskalMST.cpp}

\subsection{Centroid Decompostion}
\lstinputlisting[language=c++]{centroid_decomposition.cpp}

\subsection{Lowest Common Ancestor} 
\lstinputlisting[language=c++]{LCA.cpp}

\subsection{Heavy Light Decomposition(HLD)} 
\lstinputlisting[language=c++]{HLD.cpp}

\section{Strings}

% \subsection{Suffix arrays} % Stanford
% \lstinputlisting[language=c++]{suffix-array.cpp}

\subsection{Palindromic Tree} % Stanford
\lstinputlisting[language=c++]{palindromictree.cpp}

\subsection{Trie} % Brian Bi
\lstinputlisting[language=c++]{Trie.cpp}

% \subsection{Longest palindromic substring(Manacher)} % Brian Bi
% \lstinputlisting[language=c++]{manacher.cpp}

\subsection{Z \& Prefix Function, Knuth Morris Pratt (KMP)} % Brian Bi
\lstinputlisting[language=c++]{Z&PF.cpp}

\section{Data Structures}

\subsection{Implicit Treap} % Brian Bi
\lstinputlisting[language=c++]{Treap.cpp}

\subsection{Binary Indexed Tree (BIT)} % Brian Bi
\lstinputlisting[language=c++]{BIT.cpp}

\subsection{Binary Indexed Tree (2D BIT)} % Brian Bi
\lstinputlisting[language=c++]{2dBIT.cpp}

\subsection{Segment Tree with Lazy Propagation} % Brian Bi
\lstinputlisting[language=c++]{segtree.cpp}

\subsection{Sparse Table RMQ} % Brian Bi
\lstinputlisting[language=c++]{sparsetablermq.cpp}

\section{Miscellaneous}

% \subsection{Stable Marriage} % Brian Bi
% \lstinputlisting[language=c++]{stablemp.cpp}

\subsection{Berlekamp Massey} % Brian Bi
\lstinputlisting[language=c++]{BerlekampMassey.cpp}

\subsection{Convex Hull Trick} % Brian Bi
\lstinputlisting[language=c++]{CHT.cpp}

\subsection{2-SAT} % Brian Bi
\lstinputlisting[language=c++]{2sat.cpp}

\subsection{LCS} % Brian Bi
\lstinputlisting[language=c++]{LCS.cpp}

\subsection{LIS} % Brian Bi
\lstinputlisting[language=c++]{lis.cpp}

\subsection{Ternary Search} % Brian Bi
\lstinputlisting[language=c++]{TernarySearch.cpp}

\subsection{C ++ Template} % Brian Bi
\lstinputlisting[language=c++]{template.cpp}

\subsection{C ++ Build System} % Brian Bi
\lstinputlisting[language=c++]{C++build_system.cpp}

% \subsection{Java BigInt} % Brian Bi
% \lstinputlisting[language=Java]{BigIntJava.java}

\subsection{Java Template} % Brian Bi
\lstinputlisting[language=Java]{javatemplate.java}

\subsection{Python Fast I/O} % Brian Bi
\lstinputlisting[language=Python]{FastIOPython.py}

\subsection{Mobius Function} % Brian Bi
\lstinputlisting[language=c++]{MobiusFunction.cpp}

\subsection{K-Bit Subsets} % Brian Bi
\lstinputlisting[language=c++]{KBitSubsets.cpp}

% Bit Tricks {{{

\subsection{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|for (submask = mask; ; submask = (submask - 1) & mask)| \\
\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$.

% }}}


% Combinatorics {{{
\section{Combinatorics}

\subsection{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)$ \\
    $(x+a)^{-n} = \sum_{k=0}^{\infty} {-n \choose k} x^k a^{-n-k}$ \\
\end{tabular}

%$(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!}$.

\subsection{Binomial coefficients}

\iffalse
\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}
\fi

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}$


\subsection{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)$$


\subsection{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.

\subsection{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}$.

\subsection{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)!$.

\subsection{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}$

% \subsection{eulernumbers}
% $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).

% \subsection{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$.

% \subsection{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$.)

\subsection{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}$.

% \subsection{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)$.

% \subsection{Number of $k$-ary necklaces}
% $\frac{1}{n}\sum_{d|n} \phi(\frac{n}{d}) k^d$. \\
% \subsection{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}


\subsection{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$.

\subsection{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.

% \subsection{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.

\subsection{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.

\subsection{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$.

\subsection{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}$.
Maximum number of divisors: 4, 12, 32, 64, 128, 240, 448, 768, 1344, 2304, 4032, 6720, 10752, 17280, 26880, 41472, 64512, 103680

\subsection{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$.

\subsection{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}$
\subsection{Euler's theorem} $a^{\phi(n)} \equiv 1\pmod{n}$, if $\gcd(a,n)=1$. \\
\subsection{Wilson's theorem} $p$ is prime iff $(p - 1)! \equiv -1 \pmod p$.

\subsection{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))$.

% \subsection{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}}$

% \subsection{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}$.

% \subsection{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.

% \subsection{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}$.)


\subsection{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.


% \subsection{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$.

\subsection{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$.

\subsection{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.


% \subsection{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}

% \subsection{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]]]$, ...

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


% Graph Theory {{{
\section{Graph Theory}

\subsection{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.

% \subsection{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$.

\subsection{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.
$(|M|$ is number of edges in maximum matching$)$.
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)$.

\subsection{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.)

% \subsection{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}


% \subsection{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.



\subsection{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.



% \subsection{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$)

\subsection{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

\subsection{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$.

% }}}
W
% Games {{{

\section{Games}

\subsection{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$.

% \subsection{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}

\subsection{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}

% }}}


% Math {{{
\section{Math}

% \subsection{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$

% \subsection{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}$

% }}}

\subsection{List of Primes}

\begin{tabular}{l l l l l l l l l l l l}
    1e5 & 3 & 19 & 43 & 49 & 57 & 69 & 103 & 109 & 129 & 151 & 153 \\
    1e6 & 33 & 37 & 39 & 81 & 99 & 117 & 121 & 133 & 171 & 183 \\
    1e7 & 19 & 79 & 103 & 121 & 139 & 141 & 169 & 189 & 223 & 229 \\
    1e8 & 7 & 39 & 49 & 73 & 81 & 123 & 127 & 183 & 213 \\
\end{tabular}

\end{multicols*}
\end{document}