$exLucas$
$Description$
求
$$
C_n^m \bmod p
$$
不保证 $p$ 为质数， $1<=n, m <= 10^{18}$ 。
$Solution$
考虑先将 $p$ 质因数分解。
$$
p = \prod_{i}p_i^{a_i}
$$
显然 $p_i^{a_i}$ 两两互质，所以只需要分别求出 $C_{n}^{m} \bmod p^k$ ，构造出多个形如 $C_{n}^{m} = b_i \bmod p_i^{a_i} $ 的方程，最后用 $Crt$ 合并求解即可。
然后考虑求
$$
C_{n}^{m} \bmod p^k
$$
根据组合数公式
$$
C_{n}^{m} = \dfrac{n!}{m!(n-m)!}
$$
由于 $m!$ 与 $(n - m)!$ 中可能含有因子 $p$ ，不能直接求对于 $p^k$ 的逆元，所以考虑先提出 $n!, m!, (n - m)!$ 中的 $p$ ，最后乘回去即可。
也就是
$$
\dfrac{\dfrac{n!}{p^{k_1}}}{\dfrac{m!}{p^{k_2}} \times \dfrac{(n - m)!}{p^{k_3}}} \times p^{k_1 - k_2 - k_3}
$$
显然 $\dfrac{m!}{p^{k_2}}, \dfrac{(n - m)!}{p^{k_3}}$ 与 $p^k$ 互质，直接求逆元即可。
之后考虑如何求形如 $\dfrac{n!}{p^{a}} \bmod p^k$ 的式子。
先举个栗子，如果
$$
n = 23, p = 3, k = 2
$$
有
$$
23! = 1 \times 2 \times 3 \ldots \times 23
$$
提出 $p$ 的所有倍数
$$
3^{7} \times 7! \times (1 \times 2 \times 4 \times 5 \times 7 \times 8 \ldots)
$$
可以看出第一部分是 $p^{\left\lfloor\frac{n}{p}\right\rfloor}$ ，第二部分是 $\left\lfloor\frac{n}{p}\right\rfloor!$ ，第三部分是 $\prod_{gcd(d, p) = 1}^{n!}d$ 。
显然第一部分对于答案没有贡献，第二部分递归即可，所以现在还需要解决第三部分。
观察原式可发现
$$
1 \times 2 \times 4 \times 5 \times 7 \times 8 \equiv 10 \times 11 \times 13 \times 14 \times 16 \times 17 \pmod {p^k}
$$
显然，在 $\bmod {p^k}$ 意义下，第三部分的每一份乘积全部与 $\prod_{i = 1, gcd(i, p) = 1}^{p^k}$ 同余。
显然，这些部分有 $\frac{n}{p^k}$ 个，所以只需要暴力算出一次互质的，然后快速幂即可。
记住最后要加上不完整的块，也就是例子里的 $19 \times 20 \times 22 \times 23 $ 。
然后我们回到求组合数的过程，提出因子 $p$ ，最后乘上逆元与提出的 $p$ 即可。
对于原问题， $Crt$ 合并即可。
$Code:$
1 |
|