如何求大C(n，r)的模？

Question

如何找到C (n，r) mod k

0 < n,r < 10^5
k = 10^9 + 7 (large prime number)

我已经找到了使用Lucas定理 这里解决这个问题的链接。

但在n，r，K都很大的情况下，这对我没有帮助。这个问题的延伸是:-

找出如下数列之和:-

(C(n,r) + C(n, r-2) + C(n, r-4) + ...... ) % k

最初的约束条件仍然有效。

谢谢。

Answer 1

我知道复杂度为O(r*log_n)的算法，首先看看不带mod的calc C(n，r)算法：

int res = 1;
for(int i=1; i<=r; i++){
  res*=(n+1-i);
  res/=i;
}

在你的例子中，你不能除法，因为你使用模运算。但是你可以在模乘逆元素上乘积，关于它的信息，你可以在这里找到逆。你的代码会是这样的：

int res = 1;
for(int i=1; i<=r; i++){
  res*=(n+1-i);
  res%=k;
  res*=inverse(i,k);
  res%=k;
}

Answer 2

这是动态规划的典型用例。帕斯卡三角

C(n, r) = C(n-1, r) + C(n-1, r-1)

我们也知道

C(n, n) = 1
C(n, 0) = 1
C(n, 1) = n

您可以将模数应用于每个子结果以避免溢出。时间和内存复杂度都是O(n^2)。

Answer 3

我认为，更快的方法将是使用模块逆。

复杂度将和log(n)一样低

例如

ncr( x, y) % m将是

a = fac(x) % m;
b = fac(y) % m;
c = fac(x-y) % m;

现在，如果您需要计算(a / b ) % m，您可以执行(a % m) * ( pow( b , m - 2) % m ) // Using Fermat’s Little Theorem

https://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/