本文整理并简要介绍了所有在《算法竞赛进阶指南》中作者留坑未填的知识点，供学完这本书后进行参考。
“留坑未填”包括但不限于书中有如下描述的部分：“感兴趣的读者自行查阅资料”、“学有余力的读者自行研究”、“因内容所限，这里不再赘述”等。

0x05 奇数码问题的扩展结论

在这一节中作者介绍了奇数码问题两个局面互相可达的充要条件，且把其扩展到了 $\forall M\times N$ 的情况，但没有证明结论的充分性。并留了一道扩展题目 POJ2893 $M\times N$ Puzzle。

0x14 Manancher 算法

俗称马拉车算法，该算法可以 $O(n)$ 解决最长回文子串问题。

0x14 后缀数组的倍增与 DC3 实现

作者介绍了复杂度 $O(n\log^2 n)$ 朴素的后缀数组实现，而更快的（也是最常用的）实现还有 $O(n\log n)$ 的倍增法与 $O(n)$ 的 DC3。

0x23 舞蹈链(Dancing Links X，DLX)

DLX 是专门解决精确覆盖与重复覆盖问题的数据结构，而著名的 $n$ 皇后问题与数独问题都可化为精确覆盖问题。DLX 的本质是双向十字循环链表。

0x31 Miller-Robin 素性检验

效率更高的素性检验算法，理论基于费马小定理与二次探测定理。由于是随机性算法，有一定概率出现错误，但可通过调参降低错误率。

0x31 Pollard’s Rho 分解大数因子

效率更高的分解因子算法，期望复杂度 $O(n^{\frac{1}{4}})$，需要用到 Miller-Robin 辅助实现。

0x32 积性函数

“延伸出狄利克雷卷积、莫比乌斯反演以及一系列快速求和问题”。说白了就是莫得灵魂的推式子

0x33 指数循环节

证明欧拉定理推论需要用到的知识，在 OI 中可以用来处理指数降幂。

0x33 高次同余方程

即形如 $a^x\equiv b\pmod p$ 或 $x^a\equiv b\pmod p$ 的方程。前者可以通过 BSGS(Baby Step,Giant Step)或 exBSGS 解决，后者需要“原根、阶、指标”等内容。

0x36 生成函数

证明 Lucas 定理的工具，当然其用途绝不仅仅如此，在组合计数中应用十分广泛。多项式操作全家桶，请

0x39 Dinkelbach 迭代法

求解 0/1 分数规划问题的另一种方法，与二分法各有各的优势。但我咋觉得没啥用

0x43 标记永久化

作者在注释里提到的技巧，适合用于二维线段树与主席树等标记难以下传的情况。并在 0x48 留了一道思考题 HDOJ4348 To the Moon。

0x46 各种平衡树

Splay、RB Tree、SBT、替罪羊树、无旋 Treap(fhq-Treap)一大堆。感觉除了 RB Tree（主要是难写）都挺有用的。

0x47 KD-Tree

在线维护平面最近点对以及一系列多维偏序问题的数据结构，NOI2019 D2T1考到了 KD-Tree。

0x56 插头 DP

即轮廓线 DP，对状态的表示要更加精炼，一般与整幅图相关。并推荐了CDQ的论文《基于连通性状态压缩的动态规划》。

0x5B Garsia-Wachs 算法

与 Huffman 树很像，但与之不同的是有相邻的限制条件，解决石子合并问题可以做到 $O(n\log n)$。论文的证明我至今都没看懂

0x63 朱-刘算法

由朱永津与刘振宏在上个世纪60年代提出，$O(nm)$ 复杂度解决有向图的最小树形图问题。

0x64 仙人掌图

无向连通图的任意一条边至多只出现在一条简单回路里的图为仙人掌图。
以下是经典图

0x67 Lenguar-Tarjan 算法

通过计算支配树在 $O(n\log n)$ 时间内求出有向图给定起点的必经点集。并推荐了作者本人在 WC 上的课件《图连通性若干拓展问题探讨》。

结语：作者是毒瘤。我是菜鸡。