我想使用以下约束条件来计算nCk mod m:
n
k
m = 10 ^ 9 + 7
我已经阅读了这篇文章:
Calculating Binomial Coefficient (nCk) for large n & k
但是这里m的值为1009。因此，使用卢卡斯定理，我们只需要计算aCb的1009 * 1009个不同值，其中a，b
如何在上述限制下做到这一点。
在给定约束下，我无法制作O(m * k)空间复杂度的数组。
帮助!
最佳答案
只需使用以下事实
(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]
所以实际上您只有
2*k=2*10^5因素。对于数字的倒数，因为m是素数，所以可以使用 kfx 的建议。