求n为模n的前r个二项式系数之和的算法

Question

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

（（nC1 + nC2 + nC3 + ... + nCr）％M

其中r <= n。

是否有解决此问题的有效算法？

Answer 1

请注意，固定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）= 1f（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为nC0 + nC1 + ... + nC(r-1)，模M的前r个二项式系数之和。与其通过减少n来减少nCk的计算，还不如减少k：我们需要[C0 ]已经作为总和的一部分；另外，我们的r可能比n小得多，因此通过增加n来获得值可能远不如增加r效率高。]

[这里是想法：首先请注意，如果r> n / 2，则我们有nC(k-1)其中n-r 下一步，应用身份

nC0 + ... + nC(r-1) = 2^n - (nCr + ... + nCn) = 2^n - (nC0 + ... + nC(n-r))
按顺序计算总和的项。如果整数没有大小限制，我们可以计算
nCk = n!/(k!(n-k)!) = n!/((k-1)!(n-(k-1)!) x (n-k+1)/k = nC(k-1) x (n-k+1)/k
问题是数字nCi（因此求和）会变得很大，因此我们必须使用大整数，这会减慢计算速度。但是，我们只需要结果mod M，因此，如果我们在循环内执行计算mod M，则可以使用sum = 0;
nCi = 1; // i=0
for i = 1 to r-1
  sum += nCi;
  nCi *= (n-k+1);
  nCi /= k;
sum %= M;
 s。
总和和积是简单的mod M，但除法不是。要将nCi除以k mod 10 ^ 6，我们需要以2 ^ s 5 ^ t u的形式写nCi和k，其中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），这似乎是最快的方法，除非发现以简单的数学表达式表示总和。

在O（1）时间复杂度中nCr％p的查询

int
时间复杂度：O（106）用于预计算，O（1）用于每个查询。

有关说明，请参考：

# Python 3 program to answer queries 
# of nCr in O(1) time. 
N = 1000001

# array to store inverse of 1 to N 
factorialNumInverse = [None] * (N + 1) 

# array to precompute inverse of 1! to N! 
naturalNumInverse = [None] * (N + 1) 

# array to store factorial of 
# first N numbers 
fact = [None] * (N + 1) 

# Function to precompute inverse of numbers 
def InverseofNumber(p): 
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1): 
        naturalNumInverse[i] = (naturalNumInverse[p % i] *
                                (p - int(p / i)) % p) 

# Function to precompute inverse 
# of factorials 
def InverseofFactorial(p): 
    factorialNumInverse[0] = factorialNumInverse[1] = 1

    # precompute inverse of natural numbers 
    for i in range(2, N + 1, 1): 
        factorialNumInverse[i] = (naturalNumInverse[i] *
                                factorialNumInverse[i - 1]) % p 

# Function to calculate factorial of 1 to N 
def factorial(p): 
    fact[0] = 1

    # precompute factorials 
    for i in range(1, N + 1): 
        fact[i] = (fact[i - 1] * i) % p 

# Function to return nCr % p in O(1) time 
def Binomial(N, R, p): 

    # n C r = n!*inverse(r!)*inverse((n-r)!) 
    ans = ((fact[N] * factorialNumInverse[R])% p *
                    factorialNumInverse[N - R])% p 
    return ans 

# Driver Code 
if __name__ == '__main__': 

    # Calling functions to precompute the 
    # required arrays which will be required 
    # to answer every query in O(1) 
    p = 1000000007
    InverseofNumber(p) 
    InverseofFactorial(p) 
    factorial(p) 

    # 1st query 
    N = 15
    R = 4
    print(Binomial(N, R, p)) 

    # 2nd query 
    N = 20
    R = 3
    print(Binomial(N, R, p)) 

Answer 3

在O（1）时间复杂度中nCr％p的查询