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 许可协议,转载请注明出处。