本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-23 16:49:12

要求

$${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$ 的倍数的乘积是 $\lfloor \dfrac n p\rfloor p^{\lfloor \frac n p\rfloor}$。

不是 $p$ 的倍数的部分，由于 $p^k \le 10^6$，可以按照 $p^k$ 分成许多块，每一块的乘积都是 $\prod\limits_{i=1,(i,p)=1}^{p^k} i$。最后剩下的散块，可以直接暴力。

然后可以根据逆元计算模 $p^k$ 的组合数，之后用 CRT 合并解。