exLucas

· · 个人记录

本文参考了 \texttt{Great\_Influence} 大佬和 \texttt{Fading} 大佬的题解。

求 \dbinom n m\bmod p。

考虑到 p 不一定是质数，设 p=\prod{p_i}^{k_i}，p_i \in \text{Prime}。

那么可以先对于所有 i 求出 \dbinom n m\bmod {p_i}^{k_i}，最后 \text{crt/excrt} 合并答案。

\dbinom n m\bmod {p}^{k} =\dfrac{n!}{m!(n-m)!} \bmod {p}^{k}

可以把上式阶乘里的 p 揪出来。

定义 f(n) 为 n! 里面 p 的个数，即 f(n) = \max\{k|\dfrac{n!}{p^k}\in \mathbb{N}^{+}\}。

设 n!=xp^{f(n)}，m!=yp^{f(m)}，(n-m)!=zp^{f(n-m)}

则原式 =\dfrac{x}{yz} \times p^{f(n)-f(m)-f(n-m)} \bmod {p}^{k}

显然 f(n) 是可以在对数时间内求得的，因为我们有

f(n)=\begin{cases}\lfloor\dfrac{n}{p}\rfloor+f(\lfloor\dfrac{n}{p}\rfloor),x\ge p\\0,x<p\end{cases}

小学知识，感性理解即可

剩下的 \dfrac{x}{yz} 因为里面的 p 都被扒光了，所以可以直接求逆元

问题是怎么求 x,y,z？

考虑一下一个结成把一些倍数扒光后剩下什么

比如 22! \bmod 3^2

=1 \times 2 \times {\color{red}3} \times 4 \times 5 \times {\color{red}6} \times 7 \times 8 \times {\color{red}9} \times 10 \times 11 \times {\color{red}12} \times 13 \times 14 \times {\color{red}15} \times 16 \times 17 \times {\color{red}18} \times 19 \times 20 \times {\color{red}21} \times 22 \bmod 3^2

把 3 的倍数都揪走：

=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 \times 20 \times 22 \times 3^7 \times 7! \bmod 3^2

你发现 1 \sim 8 这段和下面 10 \sim 17 这段循环了，它们 \bmod\;3^2 的值一样，于是

=(1 \times 2 \times 4 \times 5 \times 7 \times 8)^2\times 19 \times 20 \times 22 \times 3^7 \times 7! \bmod 3^2

前面循环节长度显然是 p^k 级别的，剩下几个零散的数数量也是 p^k 级别的。

循环部分我们快速幂求解，零散部分我们暴力乘，剩下的递归下去即可。

于是我们就能够轻松计算出 x,y,z 了。

最后算上求逆元、快速幂等时间，我们在 \mathcal{O(plogn)} 时间内实现了 \text{exLucas} 算法。