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

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

n

k

m=10^9+7

我读过这篇文章：

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

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

Help!

二项式系数(n, k)由以下公式计算：

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

为了使这项工作适用于大量n and k modulo m观察到：

1. 一个数模的阶乘m可以一步步计算， 每一步都取得结果% m。然而，当 n 达到 10^18 时，这会太慢。所以有更快的方法其中复杂性受模数限制，您可以使用其中的一些。

2. 该部门(a / b) mod m等于(a * b^-1) mod m, where b^-1是b modulo 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)));
}