Last edited on 2020.9.4
2023.9.21：本题单题目较老，将于近期更新。
2019 号题单，来放计数题。
计数题是 OI 中的一大题目类型，由于难度大、不那么套路而成为各类考试的热门。
本题单收录了一些计数/求和类型的题，大都比较巧妙（和简单），适合练习计数技巧。
下面是分类。
I. 基础计数
一些计数入门题，基本上是提高组难度。
- [USACO20FEB]Help Yourself G：考虑从左到右加入线段产生的贡献。
- [JSOI2015]子集选取：只需要快速幂。
- [USACO20JAN]Cave Paintings P：与连通块有关的计数，用并查集维护。
- 车的放置：排列组合的基础。
- [HNOI2010]合唱队：简单的区间计数 dp。
- [SDOI2016]排列计数：错排问题的简单应用。
- [HNOI2012]排队：排列组合的应用。
II. Polya 计数
有关置换的计数。
- 【模板】Pólya 定理：学习 Pólya 定理和 Burnside 引理。
- [HNOI2008]Cards：Pólya 定理简单应用，类似背包的计数。
- [SDOI2013]项链：Pólya 定理简单应用。
- [MtOI2018]魔力环：较难的有关置换的计数。
III. 高级计数的基础
掌握以下知识是高级计数的基础。
- 集合划分计数：了解对一个 EGF ln 和 exp 的组合意义。
- 十二重计数法：球放进盒子里的十二个不同情况。
- 拯救世界：OGF 的简单应用。
- 拯救世界2：EGF 的简单应用。
- Partitions：了解斯特林数。学习推式子。
- 有标号 DAG 计数：了解“枚举特殊元”的 dp 方法，以及用多项式优化。
- [SDOI2017]序列计数：正难则反的思想，用卷积优化。
IV. 计数 dp
本题单的重点。
- Emiya 家今天的饭：不记录无用信息，正难则反。
- [HNOI2011]卡农：非常精妙的计数 dp。正难则反。
- [ZJOI2010]排列计数：树上拓扑序计数。
- Periodni：笛卡尔树上树形 dp。
- [HNOI2015]落忆枫音：考虑新边的贡献在 DAG 上 dp。
- Bandit Blues：发现 dp 式是第一类斯特林数，用多项式优化。
- Let us count 1 2 3：树计数。
- [USACO20FEB]Help Yourself P：线段树上维护多项式。
- [SDOI2011]黑白棋：nim 游戏上的计数，考虑二进制位。
- [SDOI2019]移动金币：阶梯博弈，仍是考虑二进制位。
- 强迫症：一条线段会把圆分成两个部分。
- [NOI2020]命运：学习线段树合并优化计数 dp。类似的题： [PKUWC2018]Minimax。
- [USACO19JAN]Train Tracking 2 P：比较困难的计数题。
V. 其它计数
这类计数很精妙，但不太好归类。
- [HNOI2013]数列：考虑差分数组。
- [AH2017/HNOI2017]抛硬币：组合数化式子，要用扩展卢卡斯。
- LCS Again：很妙的题。
- [清华集训2016] 你的生命已如风中残烛：很妙的题。