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

Question

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

algorithmmodulobinomial-coefficients

4

我正在尝试找到一个固定n的前r个二项式系数之和。

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

其中 r ≤ n。

是否有一种有效的算法来解决这个问题？

- Rohit Sharma

n和m的范围是多少？ - MrGreen

1

这似乎是一个相关的问题...http://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n - user4723924

@MrGreen M = 10^6，而r、n <= 10^9。 - Rohit Sharma

@user4723924：不，幅度的估计并不能说明模M的值。 - Douglas Zare

1

@Rohit Sharma：这个问题的来源是什么？看起来像是从一个竞赛编程网站上提取而来。如果是这样，你应该加上注释并提供链接。为什么不从nC0开始呢？ - Douglas Zare

2个回答

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,

等等。

要执行模 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 有多个质因子，则可以使用中国剩余定理将计算缩减到前面的情况。

- Edward Doolittle

为什么 (n+m) 选择 (r-1) 等于 n 选择 (r-1) mod m？例如，11 选择 11 是 1，但是 21 选择 11 = 352716，mod 10 这些不相等。 - Douglas Zare

当然，你是正确的。如果m是质数，那么根据卢卡斯定理，循环长度为m^k，其中k为某个数，但对于复合数m，情况要复杂得多。 - Edward Doolittle

我喜欢这个答案中的最后一段。如果你已经在计算二项式系数，为什么不直接计算 nC0、nC1、nC2、...、nCr 模 M 的值并将它们相加再对 M 取模呢？为什么要费力去定义和使用 f(n) 呢？ - Matt

是的，我完全同意，并且我也有同样的想法。然而，我所提到的那篇论文并不是完全易于转化为代码的，因此我一直在思考一种解决问题的方法，这种方法不使用该论文的结果。我认为我有一个解决方案：从三角形的边缘开始比从顶部开始更好。我很快会提交另一个答案。 - Edward Doolittle

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Edward Doolittle · Accepted Answer

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

我们想要计算固定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))其中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（因此sum）可能会变得非常大，所以我们必须使用大整数，这会减慢计算速度。然而，我们只需要对结果进行mod M运算，在循环内执行mod M计算时可以使用int。

Sum和product直接mod M计算很简单，但division不是。要将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整除，然后除以2或5。但是，似乎应该有更快的方法。

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