CodeBook

\documentclass[twocolumn]{article}

\usepackage[top=2cm,bottom=2cm,left=2cm,right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{xeCJK}
\usepackage{fontspec}
\usepackage{listings}
\usepackage{fancyhdr}
\usepackage{changepage}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}

\setCJKmainfont{NotoSerifTC-Medium.otf}
\XeTeXlinebreaklocale "zh"
\XeTeXlinebreakskip = 0pt plus 1pt

\lstset{
language=C++,
basicstyle=\ttfamily,
numberstyle=\footnotesize,
stepnumber=1,
numbersep=5pt,
backgroundcolor=\color{white},
showspaces=false,
showstringspaces=false,
showtabs=false,
frame=false,
tabsize=2,
captionpos=b,
breaklines=true,
breakatwhitespace=false,
escapeinside={\%*}{*)},
morekeywords={*},
literate={\ \ }{{\ }}1
}

\begin{document}

\setlength\parindent{0pt}

\tableofcontents

\pagestyle{fancy}
\fancyfoot{}
\fancyhead[L]{Gino}
\fancyhead[C]{Codebook}
\fancyhead[R]{\thepage}

\newpage

\section{Reminder}

\subsection{Bug List}
\lstinputlisting{note/BugList.txt}

\subsection{常見手法}
\lstinputlisting{note/UsefulTrick.txt}

\subsection{策略}

\subsubsection{賽前守則}
\lstinputlisting{note/LawBeforeContest.txt}

\subsubsection{賽中策略}
\lstinputlisting{note/Strategy.txt}

\subsubsection{賽中心態調整}
\lstinputlisting{note/CoolDown.txt}

\section{Basic}

\subsection{Default Code}
\lstinputlisting{code/Default.cpp}

\subsection{PBDS}
\lstinputlisting{code/PBDS.cpp}

\subsection{Random}
\lstinputlisting{code/Random.cpp}

\section{Data Structure}

\subsection{BIT}
\lstinputlisting{code/BIT.cpp}

\subsection{Segment Tree - Instruction}
\lstinputlisting{code/SegmentTree-Instruction.cpp}

\subsection{Segment Tree}
\lstinputlisting{code/SegmentTree.cpp}

\subsection{Sparse Table}
\lstinputlisting{code/SparseTable.cpp}

\section{Graph}

\subsection{Dijkstra}
\lstinputlisting{code/Dijkstra.cpp}

\subsection{Floyd-Warshall}
\lstinputlisting{code/FloydWarshall.cpp}

\subsection{SPFA}
\lstinputlisting{code/SPFA.cpp}

\subsection{Bellman-Ford}
\lstinputlisting{code/BellmanFord.cpp}

\subsection{MST - Kruskal}
\lstinputlisting{code/MST-kruskal.cpp}

\subsection{MST - prim}
\lstinputlisting{code/MST-prim.cpp}

\subsection{SCC - Tarjan}
\lstinputlisting{code/SCC-Tarjan.cpp}

\subsection{Eulerian Path - Undir}
\lstinputlisting{code/EulerianPath-Undir.cpp}

\subsection{Eulerian Path - Dir}
\lstinputlisting{code/EulerianPath-Dir.cpp}

\subsection{Hamilton Path}
\lstinputlisting{code/HamiltonPath.cpp}

\section{Tree}

\subsection{LCA}
\lstinputlisting{code/LCA.cpp}

\section{String}

\subsection{Rolling Hash}
\lstinputlisting{code/RollingHash.cpp}

\section{Geometry}

\subsection{Basic Operations}
\lstinputlisting{code/BasicOperator.cpp}

\subsection{Sort by Angle}
\lstinputlisting{code/SortByAngle.cpp}

\subsection{Line Intersection}
\lstinputlisting{code/LineIntersect.cpp}

\subsection{In-polygon Test}
\lstinputlisting{code/InPolygon.cpp}

\subsection{Polygon Area}
\lstinputlisting{code/PolygonArea.cpp}

\subsection{Convex Hull}
\lstinputlisting{code/ConvexHull.cpp}

\subsection{Closest Pair of Point}
\lstinputlisting{code/ClosestPointPair.cpp}

\subsection{Pick's Theorem}

Consider a polygon which vertices are all lattice points.

Let $i$ = number of points inside the polygon.

Let $b$ = number of points on the boundary of the polygon.

Then we have the following formula:

$$
Area = i + \frac{b}{2} - 1
$$

\section{Number Theory}

\subsection{Fast Power}
Note: $a^n \equiv a^{(n \ mod \ p-1)} (mod \ p)$
\lstinputlisting{code/FastPow.cpp}

\subsection{Matrix Fast Power}
\lstinputlisting{code/MatrixFastPow.cpp}

\subsection{Extend GCD}
\lstinputlisting{code/ExtGCD.cpp}

\subsection{Prime Seive + Defactor}
\lstinputlisting{code/PrimeSeive+Defactor.cpp}

\subsection{Other Formulas}
\begin{itemize}
    \item Inversion:\\ $aa^{-1} \equiv 1 \pmod{m}$. $a^{-1}$ exists iff $\gcd(a,m)=1$.

    \item Linear inversion:\\ $a^{-1} \equiv (m - \lfloor\frac{m}{a}\rfloor) \times (m \bmod a)^{-1} \pmod{m}$

    \item Fermat's little theorem:\\ $a^p \equiv a \pmod{p}$ if $p$ is prime.

    \item Euler function:\\ $\phi(n)=n \prod_{p|n} \frac{p-1}{p}$

    \item Euler theorem:\\ $a^{\phi(n)} \equiv 1 \pmod{n}$ if $\gcd(a,n) = 1$.

    \item Extended Euclidean algorithm:\\
    $ax+by=\gcd(a,b)=\gcd(b, a \bmod b)=\gcd(b, a-\lfloor\frac{a}{b}\rfloor b)=bx_1+(a-\lfloor\frac{a}{b}\rfloor b)y_1=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1)$

    \item Divisor function:\\ $\sigma_x(n) = \sum_{d|n}d^x$. $n=\prod_{i=1}^r p_i^{a_i}$.\\ $\sigma_x(n)=\prod_{i=1}^r \frac{p_i^{(a_i+1)x}-1}{p_i^x-1}$ if $x \neq 0$. $\sigma_0(n)=\prod_{i=1}^r (a_i+1)$.

    \item Chinese remainder theorem:\\ $x \equiv a_i \pmod{m_i}$.\\
        $M=\prod m_i$. $M_i=M/m_i$. $t_i=M_i^{-1}$.\\
        $x = kM + \sum a_i t_i M_i$, $k \in \mathbb{Z}$.
\end{itemize}

\section{Combinatorics}

\subsection{Basic Formulas}

\begin{itemize}
    \item $P^n_k=\frac{n!}{(n-k)!}$
    \item $C^n_k=\frac{n!}{(n-k)!k!}$
    \item $H^n_k=C^{n+k-1}_k=\frac{(n+k-1)!}{k!(n-1)!}$
\end{itemize}

\subsection{Catalan Number}

$$
C_0=1, C_n=\sum_{i=0}^{n-1} C_i C_{n-1-i}
$$
$$
C_n=C_n^{2n}-C_{n-1}^{2n}
$$
\begin{center}
    \begin{tabular}{r|lllll}
        0 & 1 & 1 & 2 & 5 \\
        4 & 14 & 42 & 132 & 429 \\
        8 & 1430 & 4862 & 16796 & 58786 \\
        12 & 208012 & 742900 & 2674440 & 9694845
    \end{tabular}
\end{center}

\subsection{Burnside's Lemma}

Let $X$ be the original set.

Let $G$ be the group of operations acting on $X$.

Let $X^g$ be the set of $x$ not affected by $g$.

Let $X/G$ be the set of orbits.

Then the following equation holds:

$$
|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|
$$



\section{Special Numbers}

\subsection{Fibonacci Series}

$$f(n)=f(n-1)+f(n-2)$$

\begin{equation*}
    \begin{bmatrix}
        f(n) \\
        f(n - 1)
    \end{bmatrix}
    =
    \begin{bmatrix}
        1 & 1 \\
        1 & 0
    \end{bmatrix}
    \begin{bmatrix}
        1 \\
        0
    \end{bmatrix}
\end{equation*}

\begin{center}
    \begin{tabular}{r|lllll}
        1 & 1 & 1 & 2 & 3 \\
        5 & 5 & 8 & 13 & 21 \\
        9 & 34 & 55 & 89 & 144 \\
        13 & 233 & 377 & 610 & 987 \\
        17 & 1597 & 2584 & 4181 & 6765 \\
        21 & 10946 & 17711 & 28657 & 46368 \\
        25 & 75025 & 121393 & 196418 & 317811 \\
        29 & 514229 & 832040 & 1346269 & 2178309 \\
        33 & 3524578 & 5702887 & 9227465 & 14930352
    \end{tabular}
\end{center}

$f(45) \approx 10^9$\\
$f(88) \approx 10^{18}$


\subsection{Prime Numbers}

First 50 prime numbers:\\
\begin{center}
    \begin{tabular}{r|llllllllll}
        1 & 2 & 3 & 5 & 7 & 11 \\
        6 & 13 & 17 & 19 & 23 & 29 \\
        11 & 31 & 37 & 41 & 43 & 47 \\
        16 & 53 & 59 & 61 & 67 & 71 \\
        21 & 73 & 79 & 83 & 89 & 97 \\
        26 & 101 & 103 & 107 & 109 & 113 \\
        31 & 127 & 131 & 137 & 139 & 149 \\
        36 & 151 & 157 & 163 & 167 & 173 \\
        41 & 179 & 181 & 191 & 193 & 197 \\
        46 & 199 & 211 & 223 & 227 & 229
    \end{tabular}
\end{center}

Very large prime numbers:\\
\begin{tabular}{ccc}
    1000001333 & 1000500889 & 2500001909 \\
    2000000659 & 900004151 & 850001359
\end{tabular}



\end{document}