我如何找到大 C(n , r) 的 mod

Question

如何找到 C (n , r) mod k 其中

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

我找到了使用 Lucas theorem here 解决此问题的链接。

但在我的 n 、 r 、 K 都很大的情况下，这对我没有帮助。这个问题的扩展是：-

求系列之和，如：-

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

原始约束保持不变。

谢谢。

Answer 1

这是动态规划的典型用例。帕斯卡三角形给了我们

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 2

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

复杂度将低至 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

Answer 3

我知道复杂度为 O(r*log_n) 的算法首先看一下在没有 mod k:

的情况下计算 C(n,r) 的算法

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

在你的例子中，你不能除法，因为你使用 mod元运算。但是您可以乘以 mod 元乘法逆元素，有关它的信息，您可以在此处找到 https://en.wikipedia.org/wiki/Modular_multiplicative_inverse。你的代码将是这样的：

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

Answer 4

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

由于 k 是素数，对于每个 r < k 我们可以使用扩展欧几里得算法在 模乘逆 r^-1 =14=].

因此您可以将 ((n-r+1)!/r) % k 计算为 (((n-r+1)! % k) * r^-1) % k。重复 1~r 然后你会得到结果。

How do I find mod of large C(n , r)