找到固定 n 模 m 的前 r 个二项式系数之和的算法

Question

我试图找到固定 n 的前 r 个二项式系数的总和。

(nC1 + nC2 + nC3 + ... + nCr) % M

其中 r < = n。

有没有高效的算法来解决这个问题？

Answer 1

由于多种原因，我的第一个答案并不令人满意，其中之一是我引用的论文难以理解和实现。因此，我将针对以下问题提出不同的解决方案。

我们想要计算固定 n 的前 r 个二项式系数之和，nC0 + nC1 + ... + nC(r-1)，模 M。而不是减少计算nCk 通过减少 n，减少 k 更有意义:我们需要 nC(k-1) 作为总和的一部分；此外，我们的 r 可能远小于 n，因此通过递增 n 获取值的效率远低于递增 r。

思路是:首先注意如果 r > n/2 我们有 nC0 + ... + nC(r-1) = 2^n - (nCr + ... + nCn) = 2^ n - (nC0 + ... + nC(n-r)) 其中 n-r < n/2，因此我们将问题简化为 r <= n/2 的情况。

接下来，申请身份

nCk = n!/(k!(n-k)!) = n!/((k-1)!(n-(k-1)!) x (n-k+1)/k = nC(k-1) x (n-k+1)/k

按顺序计算总和的各项。如果整数的大小是无限的，我们可以计算

sum = 0;
nCi = 1; // i=0
for i = 1 to r-1
  sum += nCi;
  nCi *= (n-k+1);
  nCi /= k;
sum %= M;

这样做的问题是数字 nCi(因此和)会变得非常大，所以我们必须使用大整数，这会减慢计算速度。但是，我们只需要结果模 M，因此如果我们在循环内执行模 M 计算，我们可以使用 int。

Sum 和 product 是简单的模 M，但除法不是。要将 nCi 除以 k mod 10^6，我们需要将 nCi 和 k 写成 2^s 5^t u 的形式，其中 u 与 10^6 互质。然后我们减去指数，并乘以 u mod 10^6 的倒数。为了把 nCi 写成那种形式，我们还需要把 n-k+1 写成那种形式。

要将 k 和 n-k+1 变成 2^s 5^t u 的形式，其中 u 与 10^6 互质，我们可以通过除以 2 重复检查可除性，对于 5 也是如此。但是，看来应该有更快的方法。

无论如何，算法现在是 O(r)，这似乎是最快的，除非发现求和的简单数学表达式。