简单计数题

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] 你的生命已如风中残烛：很妙的题。