【learning】 扩展lucas定理

首先说下啥是lucas定理：

$binom n m equiv binom {n%P} {m%P} times binom{n/P}{m/P} pmod P$

借助这个定理，求binom n m时，若P较小，且n,m非常大时，我们就可以用这个定理要降低复杂度。

但是这个定理有一些限制，比如说要求p是质数，遇到一些毒瘤出题人不太好应对。

当P不是质数时，这时就要用到一个叫做扩展lucas定理的东西。

?

令P=prod p_i^{k_i}。

我们发现，如果对于每一个p_i^{k_i}，我们都求出binom n m % p_i^{k_i}的值，我们就可以用CRT将它们合并，以得到最终的binom n m。

下面考虑如何求binom n m % p_i^{k_i}。

首先考虑组合数的一个性质：

binom n m =dfrac{n!}{m!(n-m)!}

我们发现，我们可以考虑求出n!，m!的逆元，(n-m)!的逆元，然后就可以求出组合数了。

然而直接求的话，会发现m!和(n-m)!可能求不出逆元，因为m!可能会与p_i^{k_i}不互质。

我们定义一个函数F(n,p_i,k_i)=prod_{x=1,(x,p_i)=1}^{n}x pmod {p_i^{k_i}}，再定义G(n,p_i)表示n!中p_i的素因子个数。

则有：

$binom n mequiv dfrac{F(n,k_i)}{F(m,k_i)F(n-m,k_i)}times p_i^{G(n,p_i)-G(m,p_i)-G(n-m,p_i)} pmod {p_i^{k_i}}$

考虑如何求函数F

?

考虑如何求函数G，当n>0时，有：

G(n,p_i)=lfloor frac{n}{p_i} rfloor +G(lfloor frac{n}{p_i} rfloor,p_i)

当n=0时，G显然为0。