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

Question

我正在尝试求出固定 n 的前 r 个二项式系数的总和。

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

其中 r < = n。

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

Answer 1

请注意，固定 n 的 "first" 二项式系数是 nC0。让f(n) = nC0 + nC1 + ... + nC(r-1)。使用 "Pascal's triangle" 身份，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),

IE。， 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 有一个以上的质因数，则可以使用中国剩余定理将计算简化为前面的情况。

Answer 2

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

我们要计算固定n的前r个二项式系数之和，nC0 + nC1 + ... + nC(r-1)，modulo 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)) 其中 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（因此和）会变得很大，所以我们必须使用大整数，这会减慢计算速度。但是，我们只需要结果modM，所以如果我们在循环内进行计算modM，就可以使用ints。

求和和乘积很简单 mod 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)，这似乎是最快的，除非发现求和的简单数学表达式。

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

Algorithm to find Sum of the first r binomial coefficients for fixed n modulo m

algorithm

modulo

binomial-coefficients

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