Lucas定理
Ervin
·
·
个人记录
Lucas定理
\mathbb {Auther:Ervin}
组合数：
C_n^m=\dfrac{n!} {m!(n-m)!}
加上逆元,可以实现O(n)的做法
但是,如果n和m很大呢？？
比如要求C_n^m \ mod \ p,n\le 1e18,m\le 1e18, p\le 1e5
我们可以发现,n和m非常大,但是p很小,我们就可以利用这个p
然后,我们著名的卢卡斯(Lucas)在人群中站了出来(｀･д･´)说;"让老子来教你!"
$C_n^m\ mod\ p=C_{n/p}^{m/p}\times C_{c\% p}^{m\%p}\ mod\ p
对于C_{n/p}^{m/p},如果n/p还是很大,就可以一直递归下去