type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于我的个人博客：欢迎大佬们来逛逛
递推（杨辉三角）
对于求一个数字的组合数： 可以分解为这两种形式：
- ：选择当前数
- ：不选择当前数
因此就得到了递推公式：
由于需要用到二重循环，因此此方法适用的范围是： 左右
时间复杂度：
快速幂+乘法逆元
考虑组合数的计算公式：
我们可以直接计算这个式子中的每一项。
费马小定理：如果 是一个质数，并且 和 互质，则满足：
乘法逆元：如果 与 都是质数，并且满足同余方程式： ，则称 为 模 的乘法逆元，即：
那么我们可以将费马小定理进行转化，得到：
则如果 和 都是质数， 就是 模 的乘法逆元。
因此我们要求 模 的乘法逆元，直接计算 即可
我们规定：
- 数组为阶乘数组，保存每个数字阶乘意义下的阶乘。
- 数组为逆元数组，保存每个数组阶乘意义下的逆元。
因此就可以转换为
如何求这个数组的值呢？
- 对于阶乘来说比较容易。
- 对于逆元，需要进行转化： ，因此就是
容易得知此方法计算组合数的使用范围大概是： ，其主要限制为 循环和数组空间大小
时间复杂度：
卢卡斯定理
此方法用于非常大的 和 ，但是 却比较小的计算。
定理：
即计算组合数就可以利用拆分的方法。（就不证明了）
然后注意到 是一个质数，因此 和 对其取余后，最后的结果一定比 小。
因此就可以对第二个式子进行 快速幂+逆元 的方法，我们知道这个方法的瓶颈是过大的 导致空间不够或者循环过大，通过这种方法缩小后便可以直接使用此方法。
我们便可以利用递归来依次缩小 和 的值，进而计算部分组合数，最后相乘即可，递归结束的条件是 ，此时返回 1 即可。
注意在计算某个 的时候，我们的两个数组的预处理是到 为止（因为不可能比 还大了）的。
此方法使用范围（大概）：
时间复杂度：
高精度组合数
如果我们需要求 而不需要求其模数，我们可以发现这个数字将会变得非常大，因为组合数的增长是非常快的！此时我们必须要采用高精度的方法。
此方法我们仍然需要用到公式：
步骤：
- 首先预处理所有 范围内的质数，使用线氏筛。
- 然后统计某个数阶乘意义下能够包含质数的个数
- 先处理 能够包含某质数的个数
- 再处理 能够包含某质数的个数
- 再处理 能够包含某质数的个数
- 最后一式减去二三两式就处理出了 所包含的某质数的个数
- 最后对所有的质数都执行相同的操作，然后用 ，其中 p是质数。
其中 可以表示为：
我们用高精度乘法来维护。
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/2ebad643-7241-4411-95cd-ba976cbe2f20
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。