Mythsman


乐极生悲,苦尽甘来。


大组合数取模的Lucas定理

一般情况下,我们计算大组合数取模问题是用递推公式进行计算的:
$$
C_n^m=(C_{n-1}^m+C_{n-1}^{m-1}) mod\ p
$$
其中p相对较小的素数。但是当n和m过大时,计算的耗费就急剧增加$O(mn)$,在实践中不适用。当这时候就需要Lucas定理进行快速运算:
$$
C_n^m=\prod_{i=0}^{k}C_{n_i}^{m_i}\ mod\ p
$$
其中:
$$
m=m_kp^k+m_{k-1}p^{k-1}+...+m_1p+m_0
$$
$$
n=n_kp^k+n_{k-1}p^{k-1}+...+n_1p+n_0
$$
证明方法也很简单,主要用到如下等式:
$$
C_p^j\equiv 0\ mod\ p\ ( 1 \leq j \leq p-1 )
$$
$$
(1+x)^{p}\equiv 1+x^p \ mod\ p
$$
应用这个公式,可以的到如下递归式

这里的$Lucas(n,m,p)$就是$C_n^m\ mod\ p$,递归终点就是当n=0的时候。时间复杂度是$O(log_p(n)*p)$.