我想用以下约束计算 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) 空间复杂度的数组。
帮助!
最佳答案
(n, k)
的二项式系数的计算公式为:
(n, k) = n! / k! / (n - k)!
为了对大数 n
和 k
modulo 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)));
}
关于c++ - 求大 n 和 k 模 m 的二项式系数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35288485/