组合数

从$n$个元素中选出$m$个元素的方案数，常用$C_n^m$或$C(n,m)$表示。

注意$C_n^m$是从$n$个元素里选$m$个元素的方案数！

定理一

$$C^m_n=C^{n-m}_{n}$$ 解释： 互补原理，从$n$个元素中选$m$个元素等价于从$n$个元素中选$(n-m)$个元素。

定理二

$$C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$$

解释： 考虑从$n$个元素当中选一个特殊元素出来，对于这个元素由两种情况：

1. 该元素被包含在选出的$m$个元素当中，因此这种情况的方案数是$C_{n-1}^{m-1}$。
2. 该元素不被包含在选出的$m$个元素当中，因此这种情况的方案数是$C_{n-1}^m$。

将这两种情况的方案数相加，就得到了$C_n^m$的结果。因此可以用记忆化搜索实现计算$C_n^m$的结果。

之前的代码把表示方法搞错了，简直耻辱