我想使用以下约束来计算nCk mod m:
n <= 10 ^ 18
k <= 10 ^ 5
m = 10 ^ 9 + 7
/ p>
计算二项系数( nCk)但是这里m的值是1009.因此,使用Lucas定理,我们只需要计算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 对于数字的倒数,您可以使用 kfx 的建议,因为您的 m 是素数。
I want to compute nCk mod m with following constraints:
n<=10^18
k<=10^5
m=10^9+7
I have read this article:
Calculating Binomial Coefficient (nCk) for large n & k
But here value of m is 1009. Hence using Lucas theorem, we need only to calculate 1009*1009 different values of aCb where a,b<=1009
How to do it with above constraints. I cannot make a array of O(m*k) space complexity with given constraints.
Help!
解决方案Just use the fact that
(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]so you actually have just 2*k=2*10^5 factors. For the inverse of a number you can use suggestion of kfx since your m is prime.
更多推荐
找到大n和k模m的二项式系数
发布评论