笔记汇总

在实际题目中，搜索、动态规划 都有求 方案数 的作用。

但是搜索的 时间复杂度太高，$DP$ 也只能解决 无后效性问题，在这时我们就需要靠 数学 来力挽狂澜。

组合数 $C_n^m$

从 $n$ 个不同元素中取 $m$ 个元素的集合，产生的不同集合数量。

当所表示的变量，顺序更改 不增加方案总数时可使用。

排列数 $P_n^m$

从 $n$ 个不同元素中取 $m$ 个元素排成一列，产生的不同排列数量。

当所表示的变量，顺序更改 会影响方案总数时可使用。

等价式

$C_a^i * P_b^i = P_a^i * C_b^i = C_a^i * C_b^i * i!$

预处理

为了简化时间复杂度，通常用先 预处理 后查表的方法。

拆减法

将 不规则图形 拆成多个 规则图形 的组合。

注意这类题目往往具有后效性，可以 从小到大 枚举，及时剔除 不合法的方案

抽象法

排列组合本质上是计算集合的一类群，

例如说求$n$元方程正整数解的个数，就是在求满足总值为固定值的固定单元集合的一类群。

每个单元的大小又不是独立的，因此我们以单元位置建集合，所以不存在序数关系，可以用组合数表示，

注意，最后一个单元位置是固定的，$C^{n-1}_{m-1}$。

扩展一下，对于组合数 $C^n_m$，我们只需要将 $m$ 减少 $a$，

就可以算出，至少有 $a$ 个数在一集合的所有方案，记为 前置法。

这个方法也可以扩展到所有与 交集 相关的组合数中。