🪚算法-组合数的求法
00 分钟
2023-1-12
2023-3-4
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》第三十三章 基于事件的并发(进阶)

评论
Loading...