对于很大的N和一个比较大的质数p，如何快速计算nCk % p？

Question

对于比较小的数据规模，比如说：

- P不大（P <= 10000），用Lucas定理就可以很轻松的解决，时间复杂度是O(log(n))，非常地快。
- P很大，但是n不大（P <= 10^9, n <= 100000），那根据组合的定义，计算乘法逆元就好了，如果不预处理就是O(nlogn)，也还挺快的。

但是如果数据范围达到了P <= 10^9+7, N <= 10^100，P为质数，应该如何快速计算？

Answer 1

你是说想找到一个比利用LUCAS定理算法复杂度更低的算法吗？
N达到这个量级时，计算机存储超过330位，绕不开大数计算，而这个问题如果不考虑计算机运算位数限制的话显然LUCAS定理是最优办法，因此我觉得快速算法的核心在大数运算上