4

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

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

其中 r < = n。

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

4

2 回答 2

4

我的第一个答案不满意有几个原因，其中一个是我引用的论文难以理解和实施。因此，我将针对以下问题提出不同的解决方案。

我们想要计算固定 n 的前 r 个二项式系数的和，以nC0 + nC1 + ... + nC(r-1)M 为模。不是通过减少 n 来减少计算量，而是nCk减少 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))where nr < 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（因此总和）可能会变得很大，因此我们必须使用大整数，这会减慢计算速度。但是，我们只需要结果 mod M，所以int如果我们在循环内执行计算 mod M，我们可以使用 s。

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

要将 k 和 n-k+1 放入 2^s 5^tu 的形式中，其中 u 与 10^6 互质，我们可以通过除以 2 来反复检查整除性，对 5 也是如此。但是，似乎应该有更快的方法。

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

于 2015-06-22T06:57:02.903 回答
3

请注意，固定的“第一个”二项式系数n是nC0。让f(n) = nC0 + nC1 + ... + nC(r-1). 使用“帕斯卡三角”恒等式，nCk = (n-1)C(k-1) + (n-1)Ck 我们有 

    nC0 + nC1 + nC2 + ... + nC(r-1)
    = (n-1)C(-1) + (n-1)C0 + (n-1)C0 + (n-1)C1 + (n-1)C1 + (n-1)C2 + ... + (n-1)C(r-2) + (n-1)C(r-1)
    = 2[(n-1)C0 + (n-1)C1 + (n-1)C2 + ... + (n-1)C(r-2)] + (n-1)C(r- 1)
    = 2[(n-1)C0 + ... + (n-1)C(r-1)] - (n-1)C(r-1),
即， f(n) = 2f(n-1) - (n-1)C(r-1) 因此可以通过将前一个加倍并减去 来从前一个计算每个总和(n-1)C(r-1)。

例如，如果r=3，那么 

    f(0) = 1,
    f(1) = 1 + 1 = 2 = 2f(0) - 0C2,
    f(2) = 1 + 2 + 1 = 4 = 2f(1) - 1C2,
    f(3) = 1 + 3 + 3 = 7 = 2f(2) - 2C2,
    f(4) = 1 + 4 + 6 = 11 = 2f(3) - 3C2,
    f(5) = 1 + 5 + 10 = 16 = 2f(4) - 4C2,
等等。

要执行 mod m 的计算，您需要预先计算二项式系数(n-1)C(r-1) mod m。如果m是素数，则二项式系数mod m随循环m^k（m大于的幂r-1）循环。如果m是素数的幂，则结果相当复杂。（参见http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf。）如果 m 有多个质因数，则可以使用中国剩余定理将计算简化为前面的情况。

于 2015-04-03T23:11:34.850 回答