我想使用以下约束来计算nCk mod m：
n <= 10 ^ 18
k <= 10 ^ 5
m = 10 ^ 9 + 7
但是这里的m值为1009。因此，使用卢卡斯定理，我们只需要计算1009 * 1009 aCb的不同值，其中a，b <= 1009
如何在上述限制下做到这一点。在给定约束下，我无法制作O（m * k）空间复杂度的数组。
救命！
只需使用以下事实
(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]
所以你实际上只有2*k=2*10^5因素。对于数字的倒数，因为您是素数，所以可以使用 kfx的 建议m。
2*k=2*10^5
m
