我需要nCr mod p
有效地计算。现在,我已经写了这段代码,但是它超过了时间限制。请提出更优化的解决方案。
就我而言,p = 10^9 + 7 and 1 ≤ n ≤ 100000000
我还必须确保没有溢出,因为nCr mod p
保证适合 32 位整数,但n!
可能会超过限制。
def nCr(n,k):
r = min(n-k,k)
k = max(n-k,k)
res = 1
mod = 10**9 + 7
for i in range(k+1,n+1):
res = res * i
if res > mod:
res = res % mod
res = res % mod
for i in range(1,r+1):
res = res/i
return res
PS:另外我认为我的代码可能不完全正确。但是,它似乎适用于 smalln
正确。如有不对请指出!