lucas定理

卢卡斯定理(lucas)

1.当n,m都很小的时候可以利用杨辉三角直接求。
C(n,m)=C(n-1,m)+C(n-1,m-1)；

 

2、n和m较大，但是p为素数的时候

Lucas定理是用来求 c(n,m) mod p，p为素数的值。

C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p

 

也就是Lucas(n,m)%p=Lucas(n/p,m/p)*C(n%p,m%p)%p

由费马小定理可知：m!*(n-m)! 关于P的逆元就是m!*(n-m)!的p-2次方

p较小的时候预处理出1-p内所有阶乘%p的值，然后用快速幂求出逆元，就可以求出解。p较大的时候只能逐项求出分母和分子模上p的值，然后通过快速幂求逆元求解。