exLucas
__ryp__
·
·
个人记录
要求
{n\choose m} \bmod p
其中 2 \le p \le 10^6，1 \le n, m \le 10^{18}。p 不一定是质数。
如果 p 是质数，我们可以直接用卢卡斯定理求解。
考虑将 p 分解，然后解出 n\choose m 模 p 的某个质因子次幂的值，最后用 CRT 合并。
那么问题转化为求 {n\choose m} \bmod p^k。
拆组合数定义，即 \dfrac {n!}{m!(n-m)!}。由于逆元不一定存在，不能直接计算。
考虑计算 \dfrac {n!} {p^k}，其中 k 是最大的整数使得 p^k \mid n!。然后得到原式为 \dfrac {n!p^{k1-k2-k3}}{m!(n-m)!} \bmod p^k。把指数拆出来，就可以求逆元了。
现在的问题是，求 \dfrac {n!} {p^k}，也就是把 1 到 n 中 p 的倍数全部抛除，计算剩下的数的乘积。
不是 $p$ 的倍数的部分，由于 $p^k \le 10^6$，可以按照 $p^k$ 分成许多块，每一块的乘积都是 $\prod\limits_{i=1,(i,p)=1}^{p^k} i$。最后剩下的散块，可以直接暴力。
然后可以根据逆元计算模 $p^k$ 的组合数，之后用 CRT 合并解。