type
status
date
slug
summary
tags
category
icon
password
Property
Mar 4, 2023 02:41 AM
一、基于动态规划思想的递推
当我们对组合数的转变关系进行分析时，可以得到一个关系（在
j不等于0时）：那么我们在求给定组合数之前，可以先进行初始化：
在需要求哪个组合数时，对其进行查询即可
时间复杂度
时间主要在预处理阶段，对于组合数 ，时间复杂度是
二、使用逆元进行预处理
已知组合数计算公式：
那么我们可以提前预处理出分子和分母的因子部分，在处以分母时，相当于乘上分母部分的逆元
因此，我们可以处理出分子与分母部分
886. 求组合数 II
完整代码如下：
时间复杂度：
在模MOD的情况下，每次快速幂的时间复杂度为，由于时间几乎都用在预处理阶段，因此综合来看时间复杂度为
问题：
由于该方法用到了快速幂求逆元，即费马小定理，因此要求MOD是质数，否则求逆元一步是不成立的
三、卢卡斯（Lucas）定理
887. 求组合数 III
有关证明这里不做赘述，具体的应用代码如下：
需要高精度
888. 求组合数 IV
在一些情况下，如果结果不要求对某个质数取模，可能结果很大，需要用到高精度进行计算
tips：
- 由于在进行高精度运算时，同时使用乘法和除法需要大量的计算机性能，因此需要将除法转换为乘上逆元。
- 我们需要对公式上下的各结果进行因式分解，在对阶乘进行因式分解时，需要用到以下结论：
a!中质因子n的个数等于上一篇
《Operating System：Three Easy Pieces》第三十六章 I/O设备
下一篇
《Operating System：Three Easy Pieces》第三十三章 基于事件的并发（进阶）
- 作者:GJJ
- 链接:https://blog.gaojj.cn/article/blog-62
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。