找到大n和k模m的二项式系数 [英] Finding binomial coefficient for large n and k modulo m

问题描述

我想使用以下约束来计算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的二项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！