查找大 n 和 k 模 m 的二项式系数

Question

我想计算 nCk mod m 具有以下约束：

n<=10^18

k<=10^5

m=10^9+7

我读过这篇文章：

计算大 n 和 k 的二项式系数 (nCk)

但是这里 m 的值为 1009。因此，使用卢卡斯定理，我们只需要计算 1009*1009 个不同的 aCb 值，其中 a,b<=1009

如何在上述限制下做到这一点。 我无法在给定的约束下创建一个 O(m*k) 空间复杂度的数组。

救命！

Answer 1

(n, k)

的二项式系数由以下公式计算：

(n, k) = n! / k! / (n - k)!

为了使此方法适用于大数

n

和

k

模

m

，请注意：

1. 以

   m

   为模的数的阶乘可以逐步计算，如下 每一步都会得到结果

   % m

   。然而，当 n 达到 10^18 时，这会太慢。因此，存在更快的方法，其中复杂性受模数限制，您可以使用其中的一些方法。

2. 除法

   (a / b) mod m

   等于

   (a * b^-1) mod m

   ，其中

   b^-1

   是

   b

   模

   m

   的倒数（即

   (b * b^-1 = 1) mod m

   ）。

这意味着：

(n, k) mod m = (n! * (k!)^-1 * ((n - k)!)^-1) mod m

使用扩展欧几里得算法可以有效地找到数的倒数。假设您已经解决了阶乘计算，算法的其余部分很简单，只需注意乘法时的整数溢出即可。以下是适用于

n=10^9

的参考代码。为了处理更大的数字，阶乘计算应该替换为更有效的算法，并且代码应该稍微调整以避免整数溢出，但主要思想将保持不变：

#define MOD 1000000007

// Extended Euclidean algorithm
int xGCD(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1, gcd = xGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (long long)(a / b) * y1;
    return gcd;
}

// factorial of n modulo MOD
int modfact(int n) {
    int result = 1;
    while (n > 1) {
        result = (long long)result * n % MOD;
        n -= 1;
    }
    return result;
}

// multiply a and b modulo MOD
int modmult(int a, int b) {
    return (long long)a * b % MOD;
}

// inverse of a modulo MOD
int inverse(int a) {
    int x, y;
    xGCD(a, MOD, x, y);
    return x;
}

// binomial coefficient nCk modulo MOD
int bc(int n, int k)
{
    return modmult(modmult(modfact(n), inverse(modfact(k))), inverse(modfact(n - k)));
}

Answer 2

只需使用以下事实即可

(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]

所以你实际上只有

2*k=2*10^5

因素。对于数字的倒数，您可以使用 kfx 的建议，因为您的

m

是质数。

Answer 3

首先，您不需要预先计算并存储所有可能的 aCb 值！它们可以根据情况进行计算。

其次，对于特殊情况，当 (k < m) and (n < m^2), the Lucas theorem easily reduces to the following result:

(n 选择 k) mod m = ((n mod m) 选择 k) mod m

然后自从 (n mod m) < 10^9+7 you can simply use the code proposed by @kfx.

Answer 4

我们想要计算 nCk (mod p)。 0 时我会处理 <= k <= p-2, because Lucas's theorem handles the rest.

威尔逊定理指出，对于素数 p，(p-1)！ = -1 (mod p)，或等价 (p-2)！ = 1 (mod p)（除法）。

除法： (k!)^(-1) = (p-2)!/(k!) = (p-2)(p-3)...(k+1) (mod p)

因此，二项式系数为 n!/(k!(n-k)!) = n(n-1)...(n-k+1)/(k!) = n(n-1)... (n-k+1)(p-2)(p-3)...(k+1) (mod p)

瞧。您不必进行任何逆计算或类似的事情。编码也相当容易。需要考虑的几个优化：(1) 您可以将 (p-2)(p-3)... 替换为 (-2)(-3)...； (2) nCk 是对称的，即 nCk = nC(n-k)，因此选择需要执行较少计算的一半。

Answer 5

解决这个问题的真正简单的方法就是使用两件事：

1. 第 n 行中的下一个二项式系数为 nC(k + 1) = nCk * (n - k + 1) / k;
2. 根据费马小定理和模乘逆：k^(-1) = k^(m - 2) mod m 或换句话说 ModPow(k, m - 2, m)。其中 ModPow 是函数对一个数字执行另一个数字的幂除法。可以通过求幂和平方轻松实现。

现在我们可以计算 nC(k + 1) mod m = [(nCk * (n - k + 1) mod m) * ModPow(k, m - 2, m)] mod m。在以 k = 1 到 k 开始的 for 循环中，我们可以快速找到 nCk mod m。