我已经多次遇到此问题，但无法解决。可能会发生某些情况，或者其他情况会导致错误的回答，否则我编写的程序会太慢。我正式是在谈论计算nCk mod p其中p是质数n是一个大数，且1
我尝试了什么：
我知道因子分解的递归公式，然后将其建模为动态编程问题，但是我觉得它很慢。递归公式为(nCk) + (nCk-1) = (n+1Ck)。我在将值存储在数组中时要避免模数，以免发生溢出，但是我不确定对结果执行mod p会避免所有溢出，因为可能需要将其删除。
最佳答案
要计算nCr，有一个基于规则nCr = (n - 1)C(r - 1) * n / r的简单算法：
def nCr(n,r):
if r == 0:
return 1
return n * nCr(n - 1, r - 1) // r
现在在模算术中，我们还没有除法运算，但是我们有模逆，当模数为质数时，模逆也一样好
def nCrModP(n, r, p):
if r == 0:
return 1
return n * nCrModP(n - 1, r - 1) * modinv(r, p) % p
这是Rosettacode上的一个implementation of modinv
关于c - 有效计算nCk mod p，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13780137/