main.tex

\documentclass[a4paper,10pt,twocolumn,oneside]{article}
\setlength{\columnsep}{10pt}  %兩欄模式的間距
\setlength{\columnseprule}{0pt}  %兩欄模式間格線粗細
\setlength{\headsep}{6pt}
\usepackage{amsthm}  %定義，例題
\usepackage{amssymb}
\usepackage[
    left=1cm,
    right=1cm,
    top=1.3cm,
    bottom=1cm,
]{geometry}
\usepackage{fontspec}  %設定字體
\usepackage{color}
\usepackage[x11names]{xcolor}
\usepackage{listings}  %顯示code用的
%\usepackage[Glenn]{fncychap}  %排版，頁面模板
\usepackage{fancyhdr}  %設定頁首頁尾
\usepackage{graphicx}  %Graphic
\usepackage{enumitem}
\usepackage{titlesec}
\usepackage{amsmath}
\usepackage{tikz}  % 格子紙
\usepackage[CheckSingle, CJKmath]{xeCJK}
% \usepackage{CJKulem}
%\usepackage[T1]{fontenc}
\titlespacing{\section}{0pt}{13pt}{5pt}
\titlespacing{\subsection}{0pt}{8pt}{1pt}
\usepackage{amsmath, courier, listings, fancyhdr, graphicx}
\usepackage{hyperref}
\hypersetup{
    colorlinks,
    citecolor=black,
    filecolor=black,
    linkcolor=black,
    urlcolor=black
}



%\renewcommand\listfigurename{圖目錄}
%\renewcommand\listtablename{表目錄} 

% ================================================ %

%\setmainfont[
%    Path=./fonts/,
%    UprightFont=AnthropicSerif-Text-Regular-Static.otf,
%    BoldFont=AnthropicSerif-Text-SemiBold-Static.otf,
%    ItalicFont=AnthropicSerif-Text-RegularItalic-Static.otf,
%    BoldItalicFont=AnthropicSerif-Text-SemiBoldItalic-Static.otf
%]{AnthropicSerif-Text-Regular-Static.otf}

\setmainfont[
    Path=./fonts/,
    UprightFont=CodeNewRomanNerdFontPropo-Regular.otf,
    BoldFont=CodeNewRomanNerdFontPropo-Bold.otf,
    ItalicFont=CodeNewRomanNerdFontPropo-Italic.otf
]{CodeNewRomanNerdFontPropo-Regular.otf}

\setmonofont[
    Path=./fonts/,
    UprightFont=CodeNewRomanNerdFontPropo-Regular.otf,
    BoldFont=CodeNewRomanNerdFontPropo-Bold.otf,
    ItalicFont=CodeNewRomanNerdFontPropo-Italic.otf
]{CodeNewRomanNerdFontPropo-Regular.otf}

\setCJKmainfont[
    Path=./fonts/
]{NotoSerifTC-Medium.otf}




\XeTeXlinebreaklocale "zh" %中文自動換行
\XeTeXlinebreakskip = 0pt plus 1pt %設定段落之間的距離
\setcounter{secnumdepth}{3} %目錄顯示第三層

% ================================================ %
\makeatletter
\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
\@empty\z@\@empty
\makeatother
\lstset{
language=C++,
basicstyle=\footnotesize\ttfamily,
numberstyle=\tiny\color{gray},
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={*},
keywordstyle=\bfseries\color{Blue1},
commentstyle=\itshape\color{Red4},
stringstyle=\itshape\color{Green4},
numbers=left
}


% ================================================ %

\begin{document}
\renewcommand{\headrulewidth}{0.4pt}
%\renewcommand{\contentsname}{Contents} 
\makeatletter
\renewcommand{\tableofcontents}{%
  \@starttoc{toc}%
}
\makeatother

\pagestyle{fancy}
\fancyfoot{}
\fancyhead[L]{NYCU\_LLLemonade\_Jam}
\fancyhead[C]{National Yang Ming Chiao Tung University}
\fancyhead[R]{\thepage}

% ================================================ %

{\scriptsize \tableofcontents}



\section{Reminder}

\subsection{Observations and Tricks}
\begin{itemize}[nolistsep]
    \item Contribution Technique
    \item 二分圖/Spanning Tree/DFS Tree
    \item 行、列操作互相獨立
    \item 奇偶性
    \item 當 $s, t$ 遞增並且 $t = f(s)$，對 $s$ 二分搜不好做，可以改成對 $t$ 二分搜，再算 $f(t)$
    \item 啟發式合併
    \item Permutation Normalization （做一些平移對齊兩個 permutation）
    \item 枚舉 $a_1 \sim a_n$ 再枚舉 $a_n \sim a_1$ 可以包在一個迴圈
    \item 兩個凸型函數相加還是凸型函數，相減不一定
    \item 一個區間的 mex $= k$，表示這個區間包含 $0 \sim k - 1$ 所有數字，並且「$U -$ 區間」的最小值 $= k$。
\end{itemize}

\subsection{Bug List}
\begin{itemize}[nolistsep]
\item 沒開 long long
\item 陣列戳出界／陣列開不夠大
\item 寫好的函式忘記呼叫
\item 0-base / 1-base
\item 忘記初始化
\item == 打成 =
\item <= 打成 <+
\item dp[i] 從 dp[i-1] 轉移時忘記特判 i > 0
\item std::sort 比較運算子寫成 < 或是讓 = 的情況為 true
\item 漏 case
\item 線段樹改值懶標初始值不能設為 0
\item DFS 的時候不小心覆寫到全域變數
\item 浮點數誤差
\item unsigned int128
\item 多筆測資不能沒讀完直接 return
\item 記得刪 cerr
\item vector 超級肥， 小 vector 請用 array， 例如矩陣快速冪
\end{itemize}

\begin{tikzpicture}[remember picture, overlay]
  % 在頁面底部右下方開始畫格線區域
  \begin{scope}[shift={(0,0)}, x=0.5cm, y=0.5cm]
    % 垂直線 (x 固定)
    \foreach \x in {0,...,18}
      \draw[gray!50, very thin] (\x,0) -- (\x,-19);
    % 水平線 (y 下降)
    \foreach \y in {0,...,19}
      \draw[gray!50, very thin] (0,-\y) -- (18,-\y);
  \end{scope}
\end{tikzpicture}

\newpage

% \subsection{常見手法}
% \begin{itemize}[nolistsep]
% \item 對 OOO 排序
% \item 對值域做事
% \item 數值丟到數線上
% \item 數對 (a, b) $\Rightarrow$ 二維平面
% \item 區間問題：離線、雙指針、單調性
% \item 對答案的變動因素太多，可嘗試固定一種因素，並對它枚舉
% \item 把條件列出來分 case (ex. 三維偏序)
% \end{itemize}


%\subsection{OwO}
%\begin{itemize}[nolistsep]
% \item 注意變數範圍，誰特別大／特別小，作法 80\% 跟它有關。
% \item 題目「保證」某種性質作法 99\% 跟它有關。
% \item 寫下範測，釐清題目。
% \item 可以構造複雜點的測資幫助思考。
% \item Enjoy The Game!
%\end{itemize}




\section{Init (Linux)}

開場流程：
\lstinputlisting[language=sh]{code/basic/開場流程 (Linux).sh}

\subsection{vimrc}
\lstinputlisting[language=sh]{code/basic/vimrc}

% \subsection{template.cpp}
% \lstinputlisting{code/basic/template.cpp}

\subsection{run.sh}
\lstinputlisting[language=sh]{code/basic/run.sh}

%\section{Init (Windows)}

%開場流程：
%\lstinputlisting[language=sh]{code/basic/開場流程 (Windows).sh}


\section{Basic}

% \subsection{template (optional)}
% \lstinputlisting{code/basic/template\_optional.cpp}

% \subsection{Stress}
% \lstinputlisting[language=sh]{code/basic/stress.sh}

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

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

\section{Python}
\subsection{I/O}
\lstinputlisting[language=Python]{code/python/PythonIO.py}

\subsection{Decimal}
\lstinputlisting[language=Python]{code/python/PythonDecimal.py}



\section{Data Structure}

\subsection{CDQ}
\lstinputlisting{code/data-structure/CDQ.cpp}

\subsection{Mo's Algorithm}
\lstinputlisting{code/data-structure/Mo-algorithm.cpp}

% \subsection{Segment Tree}
% \lstinputlisting{code/data-structure/SegmentTree.cpp}

%\subsection{Heavy Light Decomposition (Benson)}
%\lstinputlisting{code/data-structure/HLD-Benson.cpp}

\subsection{Heavy Light Decomposition}
\lstinputlisting{code/data-structure/HLD-Ian.cpp}

%\subsection{Heavy Light Decomposition (Gino)}
%\lstinputlisting{code/data-structure/HLD-Gino.cpp}

% \subsection{Skew Heap}
% \lstinputlisting{code/data-structure/skew-heap.cpp}

\subsection{Leftist Heap}
\lstinputlisting{code/data-structure/leftist-heap.cpp}

\subsection{Persistent Treap}
\lstinputlisting{code/data-structure/persistent-treap.cpp}

\subsection{Li Chao Tree}
\lstinputlisting{code/data-structure/li-chao-tree.cpp}

\subsection{Time Segment Tree}
\lstinputlisting{code/data-structure/time-segtree.cpp}




\section{DP}

\begin{itemize}[nolistsep]
    \item 區間 DP  
        \begin{itemize}[nolistsep]
            \item 狀態：$dp[l][r]$ = 區間 $[l,r]$ 的最佳值/方案數  
            \item 轉移：枚舉劃分點 $k$  
            \item 思考：是否滿足四邊形不等式、Knuth 優化可加速  
        \end{itemize}
    \item 背包 DP  
        \begin{itemize}[nolistsep]
            \item 狀態：$dp[i][w]$ = 前 $i$ 個物品容量 $w$ 的最佳值  
            \item 判斷是 0/1、多重、分組 $\rightarrow$ 決定轉移方式  
            \item 若容量大 $\rightarrow$ bitset / 數學變形 / meet-in-the-middle  
        \end{itemize}
    \item 樹形 DP  
        \begin{itemize}[nolistsep]
            \item 狀態：$dp[u][\text{flag}]$ = 子樹 $u$ 的最佳值  
            \item 合併子樹資訊 $\rightarrow$ 小到大合併 / 捲積式轉移  
            \item 注意 reroot 技巧（dp on tree + dp2 上傳）  
        \end{itemize}
    \item 數位 DP  
        \begin{itemize}[nolistsep]
            \item 狀態：$(pos, tight, property)$  
            \item tight 控制是否貼上界  
            \item property 常為「餘數、數字和、相鄰限制」  
        \end{itemize}
    \item 狀壓 DP  
        \begin{itemize}[nolistsep]
            \item 狀態：$dp[mask][last]$  
            \item 常見於 TSP / Hamiltonian path / 覆蓋問題  
            \item $n \le 20$ 可做，否則要容斥 / FFT  
        \end{itemize}
    \item 期望 / 機率 DP  
        \begin{itemize}[nolistsep]
            \item 狀態 $E[s]$ = 從狀態 $s$ 到終點的期望  
            \item 式子：$E[s] = c + \sum P(s \to s') E[s']$  
            \item 線性期望：能拆就拆，少算分布  
            \item 輸出 mod $\rightarrow$ 分數化 $\rightarrow$  模逆元  
        \end{itemize}
    \item 計數 DP / 組合數  
        \begin{itemize}[nolistsep]
            \item 狀態表示方案數，常搭配「模數取餘」  
            \item 若轉移是捲積型 $\rightarrow$ FFT/NTT 加速  
            \item 若能公式化（Catalan / Ballot / Stirling） $\rightarrow$ 直接套公式  
        \end{itemize}
    \item 優化 DP  
        \begin{itemize}[nolistsep]
            \item 判斷轉移方程 $dp[i] = \min_j (dp[j] + C(j,i))$ 的性質  
            \item 單調性 $\rightarrow$ 分治優化  
            \item 凸性 $\rightarrow$ Convex Hull Trick / 斜率優化  
            \item 四邊形不等式 $\rightarrow$ Knuth 優化  
        \end{itemize}
\end{itemize}

\subsection{Aliens}
\lstinputlisting{code/dp/Aliens.cpp}

\subsection{SOS DP}
\lstinputlisting{code/dp/SOS\_DP.cpp}

\subsection{期望 DP (Expected Value DP)}

\begin{itemize}[nolistsep]
    \item 狀態設計：$E[s]$ = 從狀態 $s$ 出發到終點的期望值
    \item 列式子：
    \[
        E[s] = \text{(當前代價)} + \sum_{s'} P(s \to s') \cdot E[s']
    \]
    \item 若存在自環，把 $E[s]$ 移到左邊，整理成
    \[
        (1 - P(s \to s)) E[s] = c + \sum_{s' \neq s} P(s \to s') \cdot E[s']
    \]
    \item 線性期望技巧：能拆就拆，避免處理整個分布
    \item 輸出 mod 時，分母要用模逆元：$q^{-1} \equiv q^{M-2} \pmod{M}$ (質數模數)
\end{itemize}

\paragraph{常見題型}
\begin{itemize}[nolistsep]
    \item 擲骰子遊戲（到達終點的期望步數）
    \item 隨機遊走 hitting time
    \item 重複試驗直到成功
    \item 博弈遊戲的期望值
    \item 機率 DP：計算到某步時在某狀態的機率
\end{itemize}

\paragraph{範例：擲骰子到 $n$ 格}
\[
    E[i] = 1 + \tfrac{1}{6}\sum_{d=1}^6 E[i+d], \quad (i<n), 
    \quad E[n] = 0
\]

\lstinputlisting{code/dp/dice\_expectation.cpp}

\subsection{數位 DP (Digit DP)}

\begin{itemize}[nolistsep]
    \item 狀態：$(pos, tight, property)$
    \begin{itemize}[nolistsep]
        \item pos = 當前處理到第幾位
        \item tight = 是否受限於上界 $N$
        \item property = 額外屬性（如數位和、餘數、相鄰限制…）
    \end{itemize}
    \item 遞迴：枚舉當前位數字，遞迴下一位
    \item 終止條件：$pos == \text{長度}$ $\to$ 回傳屬性是否滿足
    \item 記憶化：$dp[pos][tight][property]$
\end{itemize}

\paragraph{常見題型}
\begin{itemize}[nolistsep]
    \item 計算 $[0,N]$ 中數位和可被 $k$ 整除的數字個數
    \item 不含連續相同數字的數字個數
    \item 含特定數字次數的數字個數
    \item 位數和 / 餘數 / mod pattern
\end{itemize}

\paragraph{範例：計算 $[0,N]$ 中數位和 $\bmod k = 0$ 的數字個數}

\[
    dp[pos][tight][\text{sum mod } k]
\]

\lstinputlisting{code/dp/digit\_dp\_sum\_mod.cpp}


\section{Graph}

\subsection{Blossom}
\lstinputlisting{code/graph/Blossom.cpp}

\subsection{Weighted Blossom}
\lstinputlisting{code/graph/WeightedBlossom.cpp}

\subsection{Max Clique}
\lstinputlisting{code/graph/MaxClique.cpp}

% \subsection{Tree Centroid}
% \lstinputlisting{code/graph/tree\_centroid.cpp}

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

\subsection{BCC - AP}
\lstinputlisting{code/graph/BCC-AP.cpp}

\subsection{BCC - Bridge}
\lstinputlisting{code/graph/BCC-Bridge.cpp}

\subsection{SCC - Tarjan with 2-SAT}
\lstinputlisting{code/graph/2SAT-SCC.cpp}

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

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

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

\subsection{Kth Shortest Path}
\lstinputlisting{code/graph/KSP.cpp}

\subsection{System of Difference Constraints}
\lstinputlisting{code/graph/DiffConstraints.cpp}
\begin{itemize}
	\item $x_u - x_v \le c \Rightarrow$ \texttt{add(v, u, c)}
	\item $x_u - x_v \ge c \Rightarrow$ \texttt{add(u, v, -c)}
	\item $x_u - x_v = c \Rightarrow$ \texttt{add(v, u, c), add(u, v -c)}
	\item $x_u \ge c \Rightarrow$ add super vertex $x_0 = 0$, then $x_u - x_0 \ge c$ $\Rightarrow$ \texttt{add(u, 0, -c)}
	\item Don't for get non-negative constraints for every variable if specified implicitly.
	\item Interval sum $\Rightarrow$ Use prefix sum to transform into differential constraints.  Don't for get $S_{i+1} - S_{i} \ge 0$ if $x_i$ needs to be non-negative.
	\item $\frac{x_u}{x_v} \le c \Rightarrow$ $\log{x_u} - \log{x_v} \le \log{c}$
\end{itemize}





\section{String}

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

\subsection{Trie}
\lstinputlisting{code/string/Trie.cpp}

\subsection{KMP}
\lstinputlisting{code/string/KMP.cpp}

\subsection{Z Value}
\lstinputlisting{code/string/Zval.cpp}

\subsection{Manacher}
\lstinputlisting{code/string/Manacher.txt}

% \subsection{Suffix Array - Instruction}
% \lstinputlisting{code/string/SuffixArray-Instruction.cpp}

\subsection{Suffix Array}
\lstinputlisting{code/string/SA-Optimized.cpp}

\subsection{Suffix Automaton}
\lstinputlisting{code/string/SAM.cpp}

\subsection{SA-IS}
\lstinputlisting{code/string/SA-IS.cpp}

\subsection{Minimum Rotation}
\lstinputlisting{code/string/MinRotation.cpp}

\subsection{Aho Corasick}
\lstinputlisting{code/string/ACAutomaton.txt}






\section{Geometry}

\subsection{Template}
\lstinputlisting{code/geometry/GeometryDefault.cpp}

\subsection{Basic Operations}
\lstinputlisting{code/geometry/InPoly.cpp}
\lstinputlisting{code/geometry/SortByAngle.cpp}
\lstinputlisting{code/geometry/LineIntersectCheck.cpp}
\lstinputlisting{code/geometry/LineIntersection.cpp}
\lstinputlisting{code/geometry/ConvexHull.cpp}
\lstinputlisting{code/geometry/PolygonArea.cpp}

\subsection{Lower Concave Hull}
\lstinputlisting{code/geometry/LowerConcaveHull.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
$$

\subsection{Minimum Enclosing Circle}
\lstinputlisting{code/geometry/MinEnclosingCircle.cpp}

% \subsection{Closest Pair of Points}
% \lstinputlisting{code/geometry/ClosestPointPair.cpp}

\subsection{PolyUnion}
\lstinputlisting{code/geometry/PolyUnion.cpp}

% \subsection{Convex Hull Trick}
% \lstinputlisting{code/geometry/ConvexHullTrick.cpp}

\subsection{Minkowski Sum}
\lstinputlisting{code/geometry/MinkowskiSum.cpp}






\section{Number Theory}

%\subsection{Basic}
%\lstinputlisting{code/number-theory/Basic.cpp}

\subsection{Prime Sieve and Defactor}
\lstinputlisting{code/number-theory/PrimeSeive+Defactor.cpp}

\subsection{Harmonic Series}
\lstinputlisting{code/number-theory/Harmonic\_Series.cpp}

\subsection{Count Number of Divisors}
\lstinputlisting{code/number-theory/Number\_of\_Divisors.cpp}

\subsection{數論分塊}
\lstinputlisting{code/number-theory/數論分塊.cpp}


\subsection{Pollard's rho}
\lstinputlisting{code/number-theory/PollardRho.cpp}
\lstinputlisting{code/number-theory/PollardRho.py}

\subsection{Miller Rabin}
\lstinputlisting{code/number-theory/MillerRabin.cpp}

\subsection{Discrete Log}
\lstinputlisting{code/number-theory/DiscreteLog.cpp}
%\lstinputlisting{code/new-number-theory/exbsgs.cpp}

\subsection{Discrete Sqrt}
\lstinputlisting{code/number-theory/DiscreteSqrt.cpp}
%\lstinputlisting{code/new-number-theory/sqrt\_mod\_p.cpp}

\subsection{Fast Power}
{ \normalsize
Note: $a^n \equiv a^{(n \ mod \ (p-1))} (mod \ p)$
}

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

\subsection{Mu + Phi}
\lstinputlisting{code/number-theory/Mu + Phi.cpp}


\subsection{Other Formulas}
{\normalsize \begin{itemize}
    \item Pisano Period: 任何線性遞迴（比如費氏數列）模任何一個數字 $M$ 都會循環，找循環節 $\pi(M)$ 先質因數分解 $M = \Pi p_i^{e_i}$，然後 $\pi(M) = lcm(\pi(p_i^{e_i}))$，

    \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$.  If a, n are not coprime: 質因數分解 $n = \Pi p_i^{e_i}$，對每個 $p_i^{e^i}$ 分開看他們跟 $a$ 是否互質（互質：Fermat／不互質：夠大的指數會直接削成 $0$），最後用 CRT 合併。
    
    \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 (Coprime Moduli):\\ $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}$.
        
    \item Chinese remainder theorem:\\
    $x \equiv a_1 \pmod{m_1}, x \equiv a_2 \pmod{m_2} \Rightarrow x = m_1 p + a_1 = m_2 q + a_2 \Rightarrow m_1 p - m_2 q = a_2 - a_1$\\
    Solve for $(p, q)$ using ExtGCD.\\
    $x \equiv m_1 p + a_1 \equiv m_2 q + a_2 \pmod{lcm(m_1, m_2)}$
    
    \item Avoiding Overflow:
    $ca \mod cb = c(a \mod b)$
    
    \item Dirichlet Convolution: $(f * g)(n) = \sum_{d|n} f(n)g(n/d)$
    
    \item Important Multiplicative Functions + Proterties:
    \begin{enumerate}[nolistsep]
        \item $\epsilon(n) = [n = 1]$
        \item $1(n) = 1$
        \item $id(n) = n$
        \item $\mu(n) = 0$ if $n$ has squared prime factor
        \item $\mu(n) = (-1)^k$ if $n = p_1 p_2 \cdots p_k$
        \item $\epsilon = \mu * 1$
        \item $\phi = \mu * id$
        \item $[n=1] = \sum_{d|n} \mu(d)$
        \item $[gcd=1] = \sum_{d|gcd} \mu(d)$
    \end{enumerate}
    
    \item Möbius inversion:
    $f = g * 1 \Leftrightarrow g = f * \mu$
\end{itemize}}

\subsection{Polynomial}
\lstinputlisting{code/number-theory/Polynomial.cpp}

\subsection{Counting Primes}
\lstinputlisting{code/new-number-theory/counting\_primes.cpp}

\subsection{Linear Sieve for Other Number Theoretic Functions}
\lstinputlisting{code/new-number-theory/linear\_sieve.cpp}

% \subsection{GCD Convolution}
% \lstinputlisting{code/new-number-theory/gcd\_convolution.cpp}


\section{Linear Algebra}

\subsection{Gaussian-Jordan Elimination}
\lstinputlisting{code/linear-algebra/GaussElimination.cpp}

\subsection{Determinant}
{\normalsize
\noindent
\begin{enumerate}
\item Use GJ Elimination, if there's any row consists of only 0, then det = 0, otherwise det = product of diagonal elements.
\item Properties of det:
\begin{itemize}
    \item Transpose: Unchanged
    \item Row Operation 1 - Swap 2 rows: $-det$
    \item Row Operation 2 - $k \overrightarrow{r_i}$: $k \times det$
    \item Row Operation 3 - $k \overrightarrow{r_i}$ add to  $\overrightarrow{r_j}$: Unchaged
\end{itemize}
\end{enumerate}
}

\section{Flow / Matching}

\subsection{Flow Methods}
\lstinputlisting{code/flow/FlowMethod.txt}

\subsection{Dinic}
\lstinputlisting{code/flow/Dinic.cpp}

\subsection{ISAP}
\lstinputlisting{code/flow/ISAP.cpp}

\subsection{Bounded Max Flow}
\lstinputlisting{code/flow/BoundedMaxFlow.cpp}

\subsection{MCMF}
\lstinputlisting{code/flow/MCMF.cpp}

\subsection{Hopcroft-Karp}
\lstinputlisting{code/flow/HopcroftKarp.cpp}

\subsection{Cover / Independent Set}
\lstinputlisting{code/flow/CoverIndepend.txt}

\subsection{Kuhn Munkres}
\lstinputlisting{code/flow/KM2.cpp}

\section{Combinatorics}

\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{Bertrand's Ballot Theorem}

\begin{itemize}
    \item $A$ always $> B$: $C(p+q, p) - 2 C(p+q-1, p)$
    \item $A$ always $\geq$ $B$: $C(p+q, p) \times \frac{p + 1 - q}{p + 1}$
\end{itemize}


\subsection{Burnside's Lemma}
{\normalsize
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}

{\normalsize
\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}
\noindent
$f(45) \approx 10^9, f(88) \approx 10^{18}$
}


\subsection{Prime Numbers}
{\normalsize
\begin{itemize}

%\item 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}


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

\item $\pi(n) \equiv$ Number of primes $\leq n \approx n/((\ln n) - 1)$ \\
$\pi(100) = 25, \pi(200) = 46$ \\
$\pi(500) = 95, \pi(1000) = 168$ \\
$\pi(2000) = 303, \pi(4000) = 550$ \\
$\pi(10^4) = 1229, \pi(10^5) = 9592$ \\
$\pi(10^6) = 78498, \pi(10^7) = 664579$ \\
 
\end{itemize}
}



\newpage

\begin{tikzpicture}[remember picture, overlay]
  % 在頁面底部右下方開始畫格線區域
  \begin{scope}[shift={(0,0)}, x=0.5cm, y=0.5cm]
    % 垂直線 (x 固定)
    \foreach \x in {0,...,18}
      \draw[gray!50, very thin] (\x,0) -- (\x,-55);
    % 水平線 (y 下降)
    \foreach \y in {0,...,55}
      \draw[gray!50, very thin] (0,-\y) -- (18,-\y);
  \end{scope}
\end{tikzpicture}


\end{document}