省选内容学习清单

转自 Ignotus Orz

省选内容学习清单：

• 数学：

  1. 扩展中国剩余定理，扩展卢卡斯，BSGS，exBSGS
  2. 二项式反演，莫比乌斯反演，筛法（杜教筛，Min_25 筛），Miller-Rabbin 素性测试，Pollard-Rho
  3. 多项式：拉格朗日插值，FFT，NTT，MTT，FWT
  4. 多项式：求逆，ln，exp，开根
  5. 多项式：泰勒展开，牛顿迭代，泰勒级数
  6. 生成函数，卷积
  7. 线性代数：行列式，矩阵求逆，LGV 引理
  8. 组合数学：Burnside 定理，Pólya 定理，斯特林数
  9. 群论基础

• 数据结构：

  1. 线段树合并、分裂；李超线段树，zkw 线段树
  2. 平衡树：fhq-Treap，Splay；树套树
  3. 可持久化数据结构：可持久化线段树，可持久化字典树，可持久化平衡树
  4. 可并堆、可持久化可并堆
  5. K-D Tree，ODT
  6. 笛卡尔树
  7. （选）LCT，top tree

• 字符串：

  1. 后缀数组（SA）
  2. 后缀自动机（SAM，广义 SAM），回文自动机（PAM）
  3. 后缀平衡树，后缀树

• 动态规划：

  1. 插头 dp，动态 dp
  2. 刷题，领会思想，逐步构建解题的模型
  3. 计数 dp，树上、序列上、图上 dp 的优化

• 图论：

  1. 二分图，网络流（Dinic，ISAP，费用流，上下界网络流）
  2. 次短路，次小生成树，k 短路
  3. 点双连通分量，边双连通分量，割点，割桥，圆方树，静态仙人掌，动态仙人掌
  4. 生成树计数，Matrix-tree 定理
  5. 虚树

• 其它：

  1. 计算几何的数学基础
  2. 微积分
  3. 二维凸包，旋转卡壳，半平面交
  4. Linux 系统的使用
  5. 复杂分治的思想与模型的建立
  6. 各种树上问题
  7. 总结各种常见结论