我的算法书 - 乘法原理

一句话算法

乘法原理处理的是“分步骤完成一件事”：每一步有多少种选择，总方案数就把每一步的选择数乘起来。

问题模型

如果完成一件事必须依次完成 $k$ 个步骤：

第 1 步 -> 第 2 步 -> ... -> 第 k 步

并且：

第 $1$ 步有 $a_1$ 种选择。
第 $2$ 步在任意第 $1$ 步选择后都有 $a_2$ 种选择。
…
第 $k$ 步在前面步骤确定后都有 $a_k$ 种选择。

那么总方案数是：

a_1a_2\cdots a_k

“乘法原理”

完成一个对象需要连续做若干个步骤，且每个完整方案都能唯一拆成这些步骤的选择，则总方案数等于各步骤选择数的乘积。

核心直觉

乘法原理不是“看到两个数就乘”，而是“走一条决策树”。

例如先从集合 $A$ 中选一个元素，再从集合 $B$ 中选一个元素：

A: a1, a2, a3
B: b1, b2

每个 $a_i$ 后面都可以接两个选择：

a1 -> b1, b2
a2 -> b1, b2
a3 -> b1, b2

共有：

3\times 2=6

个有序对。

这 $6$ 个对象是：

(a_1,b_1),(a_1,b_2),(a_2,b_1),(a_2,b_2),(a_3,b_1),(a_3,b_2)

与加法原理的区别

加法原理是“分类”：做法属于哪一类。

乘法原理是“分步”：一个完整做法由哪些步骤组成。

原理	判断问题	关键词
加法原理	这件事可以分成哪些互斥类别？	或者、分类、选一种
乘法原理	这件事要经过哪些连续步骤？	先后、每一步、同时确定

例如：

从红球或蓝球中任选一个：分类，用加法。
先选一个红球，再选一个蓝球：分步，用乘法。

算法步骤

解决乘法原理计数题时，可以按下面四步做。

定义完整方案：先说清楚一个答案长什么样。
拆成步骤：把一个完整方案拆成若干个必须依次确定的选择。
计算每步选择数：注意后一步的选择数是否依赖前一步。
相乘：若每个完整方案都被唯一表示，直接乘起来。

如果后一步选择数会随前一步不同而变化，就不能简单写成固定乘积，需要分类后再乘：

\sum_{\text{第一步选择 }x} \text{后续方案数}(x)

算法证明

两步情况

设第一步选择集合为 $A$ ，第二步选择集合为 $B$ ，其中：

|A|=m,\quad |B|=n

完整方案是一个有序对：

(a,b),\quad a\in A,\ b\in B

对每个固定的 $a$ ，都能搭配 $n$ 个不同的 $b$ 。这样的 $a$ 一共有 $m$ 个，所以总数为：

\underbrace{n+n+\cdots+n}_{m\text{ 个}}=mn

多步情况

把前 $k-1$ 步看成一个大步骤。若前 $k-1$ 步共有：

a_1a_2\cdots a_{k-1}

种方案，每种方案后面都能接 $a_k$ 种第 $k$ 步选择，那么总数是：

a_1a_2\cdots a_{k-1}\cdot a_k

因此多步乘法原理成立。

复杂度分析

乘法原理本身是计数工具，不是固定算法。

若只计算公式，时间复杂度通常是 $O(k)$ ，其中 $k$ 是步骤数。
若答案很大，需要使用高精度或在模意义下计算。
若每一步选择数依赖前面状态，可能需要动态规划或搜索，不再只是简单相乘。

代码实现

本文不提供代码模板。乘法原理通常直接出现在推导中，真正需要模板的场景会落到排列、组合、动态规划或快速幂等具体算法上。

测试用例

有序对计数

集合：

A = {a1, a2, a3}
B = {b1, b2}

从 $A$ 中选一个，再从 $B$ 中选一个，方案数：

3\times 2=6

排队问题

有 $n$ 个不同的人排成一队。

第一个位置有 $n$ 种选择，第二个位置有 $n-1$ 种选择，依次类推，总数是：

n(n-1)(n-2)\cdots 1=n!

密码问题

一个长度为 $6$ 的密码，每位可以是 0..9，允许重复。

每一位都有 $10$ 种选择，总数是：

10^6

应用分类详解

乘法原理的本质是“一个方案由多个独立步骤拼成”。看到题目要求按位、按位置、按阶段依次确定对象时，应优先尝试乘法原理。

一、位置填充

典型模式： 若干个位置，每个位置填一个对象。

识别信号： 排队、座位、密码、字符串、路径每一步选择。

核心建模： 第 $i$ 个位置有多少种选择，把每个位置的选择数相乘。

应用场景	经典题目	核心思路
密码数量	基础计数题	每一位独立选择
全排列	本书排列组合章节	位置选择数依次为 $n,n-1,\ldots,1$
固定长度字符串	字母表计数	每个字符位置有固定选择数

二、对象组合成有序结构

典型模式： 一个答案是若干部分拼成的有序结构。

识别信号： 有序对、三元组、坐标、边的两个端点。

核心建模： 每一部分分别确定，完整结构由这些选择唯一决定。

三、递归分步

典型模式： 当前选一个对象后，剩余问题规模减少。

识别信号： “先选一个”“剩下的问题相同”“每次少一个”。

核心建模： 得到递推式，例如全排列：

f(n)=n\cdot f(n-1)

最终得到：

f(n)=n!

四、概率中的样本空间

典型模式： 多次实验，每次实验有若干种结果。

识别信号： 掷骰子、抛硬币、抽牌顺序、随机字符串。

核心建模： 样本空间大小由每次实验结果数相乘得到。例如抛 $n$ 次硬币共有 $2^n$ 种结果。

经典例题

1. 不同人的排队数量

$n$ 个不同人排成一队，有：

n!

种排法。它是乘法原理最直接的应用。

2. 固定长度密码数量

长度为 $L$ ，字符集大小为 $m$ ，允许重复，则密码数量为：

m^L

3. 棋盘坐标数量

一个 $n\times m$ 棋盘中，一个格子由行号和列号唯一确定。行号有 $n$ 种，列号有 $m$ 种，所以格子数是：

nm

参考

本书排列组合章节：math/combinatorics/combinatorics/index.md
本书加法原理章节：math/combinatorics/rule_of_sum/index.md