Counting

小球入盒问题是所有组合问题的基础，它计算的是形如 “\(n\) 个球放进 \(m\) 个盒子的方案数” 的一类问题，在这类问题中一般存在三种限制 ：

• 小球是否有编号。
• 盒子是否有编号。
• 盒子中球的数量是无限制，至少一个还是至多一个。

理由同上，方案数为 ：

• 将要计数的总体分成很多个部分，每个部分分别计算贡献。
• 有些时候一个集合 \(S\) 联合产生贡献，为了避免算重，可以将这个集合的贡献放在其中的某个元素上计算，比如标号最小的那一个。
• 可以考虑划分阶段，每次加入一个元素时计算答案增量。
• 如果需要计算在一个大的部分中选…