求组合数有O(n^2)和 O(n)的算法，但是当n十分大的的时候，就要用到卢卡斯定理了。
比如求C(n, m) % p ， n<=1e18,m<=1e18,p<=1e5。利用lucas定理时p一定要<=1e5，且p为素数。
Lucas定理：C(n, m) % p = C(n / p, m / p) * C(n%p, m%p) % p
对于C(n / p, m / p)，如果n / p 还是很大，需要递归。
模板：
LL Lucas(LL n, LL m, int p){ return m ? Lucas(n/p, m/p, p) * comb(n%p, m%p, p) % p : 1; }
卢卡斯扩展定理后续再更...
原文：https://www.cnblogs.com/FrankChen831X/p/10665946.html