分步时按前一步的结果分类

解题套路

逐个安排元素时，本来想写成 $m_1\times m_2\times\cdots$，却发现第 $j$ 步能选几种要看前面选了什么——这时不要硬乘，也不必推倒重来：

1. 找到「方法数开始依赖前面」的那一步；
2. 按前面的结果分成几类，使得每一类内部第 $j$ 步的方法数是同一个常数；
3. 每类内部照常分步相乘；
4. 类间相加。

一个标准例子

三人站 $7$ 级台阶、每级最多 $2$ 人。先甲（$7$ 种）、再乙（$7$ 种），到丙就卡住了：丙能选几级要看甲乙是不是站在同一级。于是按这一点分两类：

• 甲乙同级：这样的 (甲, 乙) 有 $7$ 种；那一级已满，丙只剩 $6$ 级 $\Rightarrow 7\times6=42$；
• 甲乙异级：这样的 (甲, 乙) 有 $7\times6=42$ 种；两级各只站一人，丙随意 $\Rightarrow 42\times7=294$。

合计 $42+294=336$。

与「先算总数再减」的分工

同一道题往往两条路都通：分类是正面切，补集是反面挖。判据很简单——

• 依赖只有两三种情形（本例就两种）$\Rightarrow$ 分类，过程直白；
• 违规的情形只有一小撮、而无限制的总数一眼可得 $\Rightarrow$ 用补集更省。

注意

• 分类轴要保证类内是常数，不是随便切一刀：切完仍然「有的 $6$ 种有的 $7$ 种」，等于没切。
• 各类的前几步方法数也要重新数（本例里「甲乙同级」只有 $7$ 种，不是 $7\times7$），这是最常见的漏算处。