2018.7-2024.2.3

cnblogs

正在施工：數(shù)論函數(shù)與篩法、回憶錄。

已經(jīng)寫好且在所有內(nèi)容寫完之前不會(huì)大修的（歡迎勘誤）：

圖論方向

• 圖論 I (2024.8.9)：你需要的所有圖論知識(shí)都在這里。
  • 基礎(chǔ)知識(shí)：拓?fù)渑判颉o向圖 DFS 樹。
  • 最短路：?jiǎn)卧醋疃搪窂剑˙ellman-Ford、Dijkstra、SPFA）、差分約束、全源最短路徑（Johnson、Floyd）、擴(kuò)展問題（最短路樹、刪邊最短路、平面圖最小割、\(k\) 短路、同余最短路）。
  • 無向圖最小生成樹：最小生成樹問題（Kruskal、Prim、Boruvka）、擬陣和生成樹（擬陣的性質(zhì)、擬陣上的最優(yōu)化問題、最小生成樹的性質(zhì)）、擴(kuò)展問題（次小生成樹、\(k\) 小生成樹、最小生成樹計(jì)數(shù)、最小度限制生成樹）。
  • 無向圖連通性之雙連通分量：雙連通的基本性質(zhì)（邊雙連通的性質(zhì)、點(diǎn)雙連通的性質(zhì)、Menger 定理）、Tarjan 求割點(diǎn)、割邊（Tarjan 法、差分法）、邊雙連通分量縮點(diǎn)。
  • 有向圖可達(dá)性之強(qiáng)連通分量：有向圖 DFS 樹、Tarjan 求 SCC、Kosaraju 算法。
  • 歐拉回路：歐拉圖判定（有向圖、無向圖、混合圖）、Hierholzer 算法。
• 圖論 II (2025.2.13)：進(jìn)階知識(shí) & 理性娛樂。
  • 2-SAT：布爾邏輯式相關(guān)概念、2-SAT 的求解與字典序最小解。
  • 點(diǎn)雙連通進(jìn)階之廣義圓方樹：點(diǎn)雙縮點(diǎn)、Tarjan 算法求廣義圓方樹、圓方樹的形態(tài)和性質(zhì)。
  • 雙連通進(jìn)階之耳分解和雙極定向：耳分解的存在性定理及其構(gòu)造、雙極定向的存在性定理及其構(gòu)造。
  • 支配樹：支配關(guān)系及其性質(zhì)（偏序集）、DAG 支配樹、一般圖支配樹。
• 網(wǎng)絡(luò)流 (2025.7.7)：
  • 網(wǎng)絡(luò)最大流：增廣路、最大流最小割定理、Edmonds-Karp、Dinic。
  • 無負(fù)環(huán)的費(fèi)用流：SSP、Primal-Dual。
  • 上下界網(wǎng)絡(luò)流：無源匯可行流、有源匯可行流、有源匯最大流、有源匯最小流、無源匯費(fèi)用流、有源匯費(fèi)用流、有負(fù)環(huán)的費(fèi)用流。
  • 常見模型：最小割點(diǎn)、集合劃分模型、最大權(quán)閉合子圖、切糕模型、區(qū)間選擇模型、最大密度子圖、二分圖相關(guān)、DAG 最小路徑覆蓋。
  • 網(wǎng)絡(luò)流 24 題。
• 同余最短路的轉(zhuǎn)圈技巧 (2024.8.11)：同余最短路不再需要最短路。
• 冷門科技 —— DFS 序求 LCA (2024.8.11)：還在為歐拉序 LCA 忘記開兩倍空間而煩惱？DFS 序也能求 LCA！

數(shù)據(jù)結(jié)構(gòu)方向

• 線段樹進(jìn)階 Part 1 (2024.8.12)：
  • 常見技巧：信息設(shè)計(jì)、抽象線段樹、維護(hù)歷史信息（歷史最值、歷史和）、動(dòng)態(tài)開點(diǎn)、標(biāo)記永久化、線段樹二分。
  • 可持久化線段樹：可持久化線段樹及其應(yīng)用（強(qiáng)制在線靜態(tài)二維數(shù)點(diǎn)、靜態(tài)區(qū)間第 \(k\) 小）、其它可持久化數(shù)據(jù)結(jié)構(gòu)。
  • 線段樹合并：線段樹合并及其應(yīng)用（可持久化、SAM 的 endpos 集合、整體 DP）、線段樹分裂。
  • 樹套樹：BIT 套線段樹（帶修二維數(shù)點(diǎn)、動(dòng)態(tài)逆序?qū)Α?dòng)態(tài)區(qū)間第 \(k\) 小）。

數(shù)學(xué)方向

• 同余代數(shù) (2025.1.28)：
  • 基礎(chǔ)知識(shí)：同余的性質(zhì)、Fermat 小定理、乘法逆元（\(\mathcal{O}(1)\) 在線逆元）、Lagrange 定理、（擴(kuò)展）Wilson 定理、Kummer 定理、步長和子環(huán)、（擴(kuò)展）Euler 定理、同余式的除法、*循環(huán)群和直積。
  • 二元線性不定方程：Bezout 定理、擴(kuò)展歐幾里得算法 exgcd、特解的數(shù)值范圍和通解形式。
  • 線性同余方程組：中國剩余定理 CRT、擴(kuò)展中國剩余定理 exCRT、*抽象代數(shù)中的 CRT。
  • 組合數(shù)取模：Lucas 定理、exLucas 定理。
  • 離散對(duì)數(shù)問題：大步小步算法 BSGS、擴(kuò)展大步小步算法 exBSGS。
  • 階與原根：階及其性質(zhì)與求法、原根（原根判定定理、原根存在定理、原根個(gè)數(shù)定理、原根的求法、原根和單位根）、*\((\mathbb Z / n\mathbb Z) ^ \times\) 的結(jié)構(gòu)、
  • N 次剩余問題：N 次剩余的定義、Legendre 符號(hào)、二次剩余的分布和判定、Euler 準(zhǔn)則、模意義下開平方根、模意義下開 N 次根。
• OI 中的群論 (2025.8.27)：群和群作用、軌道-穩(wěn)定子定理、Burnside 引理、Pólya 計(jì)數(shù)定理。