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

Question

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

n<=10^18

k<=10^5

m=10^9+7

我已阅读这篇文章：

Calculating Binomial Coefficient (nCk) for large n & k

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

如何在上述约束下做到这一点。我无法在给定的约束条件下制作复杂度为 O(m*k) space 的数组。

求助！

Answer 1

(n, k)的二项式系数的计算公式为：

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

为了使这项工作适用于大数 n 和 k 模 m 观察到：

一个数的阶乘模m可以一步步计算，在每一步取结果% m。然而，这对于 n 高达 10^18 来说太慢了。所以有 faster methods 复杂度受模数限制，您可以使用其中的一些。
除法 (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

可以使用 Extended Euclidean algorithm 有效地找到数字的倒数。假设您已经解决了阶乘计算问题，算法的其余部分就很简单了，只需注意乘法运算时的整数溢出即可。这是最高可达 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

首先，您不需要预先计算并存储所有可能的aCb值！它们可以按案例计算。

其次，对于 (k < m) 和 (n < m^2) 的特殊情况，卢卡斯定理很容易简化为以下结果：

(n选k)modm=((nmodm)选k)modm

然后因为 (n mod m) < 10^9+7 你可以简单地使用 @kfx 提出的代码。

Answer 3

只需使用

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

所以你实际上只有 2*k=2*10^5 个因素。对于数字的倒数，您可以使用 kfx 的建议，因为您的 m 是素数。

Answer 4

我们要计算 nCk (mod p)。当 0 <= k <= p-2 时，我会处理，因为卢卡斯定理会处理其余部分。

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

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

因此，二项式系数为 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) 的意义上是对称的，因此选择需要您进行较少计算的那一半。

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

Finding binomial coefficient for large n and k modulo m

c++

algorithm

binomial-coefficients

modulus

modular-arithmetic