「Algorithm」扩展Lucas学习笔记

本来没打算学的，既然模拟赛考到了就还是学一下吧

Pre-Knowledge

• ex_gcd
• CRT or ex_CRT(合并模线性方程组)
• A strong will

Brief Introduction

我们都知道，Lucas定理是当$n,m$比较大（大于$P$）时，用来求，其中$P$为质数的一个工具。它长这样：

把 $n$ 和 $m$ 表示成 $P$ 进制数，对 $P$进制下的每一位分别计算组合数，最后乘起来。这样递归计算的话就能保证需要求的$n,m$在$P$的范围内了

但是当不为质数的时候就需要用到扩展Lucas了，但其实它和Lucas没有半毛钱关系

Analysis

1. 把$p$质因数分解，即分解成$P = \prod p_i^{k_i}$的形式，那么只需要分别求出，利用CRT或ex_CRT就能合并答案

2. 把组合数展开：

   考虑把$n!,m!,(n-m)!$这三项中含$p_i$的因子提出来，变形得到

   其中$a1, a2, a3$分别表示$n!,m!,(n-m)!$含$p_i$的次数

3. 解决这个子问题，注意在计算上式的分母时需要用ex_gcd求逆元

最后一步步往上推就行了

Process

重点在于如何求

先举一个例子吧，假设$n = 19, p = 3, k = 2$

这里真的随便手玩一下就懂了

$19!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10 \times 11\times 12\times 13\times 14\times 15\times 16\times 17\times 18\times 19$

把所有$p$的倍数的项提出来：

$19!=3^6 \times (1\times 2\times 3\times 4\times 5\times 6)\times(1\times 2\times 4\times 5\times 7\times 8\times 10 \times 11\times 13\times 14\times 16\times 17\times 19)$

不难注意到最后一个括号里的数在模$p^k$意义下是不断循环的，即

$19!=3^6 \times (1\times 2\times 3\times 4\times 5\times 6)\times(1\times 2\times 4\times 5\times 7\times 8)\times (10 \times 11\times 13\times 14\times 16\times 17)\times 19$

很显然，$(1\times 2\times 4\times 5\times 7\times 8)$和$(10 \times 11\times 13\times 14\times 16\times 17)$在模$p^k$意义下相等

那么

$19!=3^6 \times 6!\times(1\times 2\times 4\times 5\times 7\times 8)^2\times 19$

---

通过上面这个例子，我们可以形式化地得出以下式子：

其中$num_i$表示不含$p$因子的数字

考虑每一项的意义以及如何求：

• $p^{\lfloor \frac{n}{p} \rfloor}$ ：因为最后我们要求，需要除掉$p^a$，因此可以在这里直接不乘这一项
• $\lfloor \frac{n}{p} \rfloor!$ ：直接递归求解，边界条件是$n=0$答案为$1$
• ：也就是小于的部分循环了次。可以直接暴力求出，然后做一遍快速幂
• ：循环最后会剩下一部分多的，直接暴力乘起来即可

Complexity

瞎分析一波

首先分析一下求解的复杂度

$T(n) = T(\frac{n}{p}) + O(p^k)$

根据主定理容易得到$T(n) = O(p^k )$

另外，ex_gcd求逆元那里还有一个的复杂度

总复杂度为

$O\Big(\sum (p_i^{k_i} + \log P)\Big)$

Code

还没写