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

Question

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

n<=10^18

k<=10^5

m=10^9+7

我读过这篇文章：

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

但是这里m的值为1009。因此使用卢卡斯定理，我们只需要计算aCb的1009*1009个不同值，其中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的倒数（即）。bm(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是素数。