如何在C或C++中计算(N选择K)%M，避免溢出？
特别地，当N (4<=N<=1000)，K (1<=K<=N)，且M = 1000003时。
5个回答
13
要计算(n choose k) % M，可以分别计算被除数(n!)模M和除数(k!*(n - k)!)模M，然后将被除数乘以除数的模逆元素（在M下）。由于M是质数，因此可以使用费马小定理来计算乘法逆元。
以下链接（问题SuperSum）提供了一个很好的解释和示例代码：
- Piva
3
2为了获得额外的速度，将分子计算为从（K+1）到N的乘积，将分母计算为K！。我们知道在计算中不会有M的因数，因为它是质数且大于N。因此，我们可以放心地取消分子和分母，而不必担心我们要取消的内容可能是M的倍数（即0）。 - Steve Jessop
但是现在我发现1,000,000,003不是质数，你有什么解决办法吗？ - Quixotic
@Tretwick Marian：除非由于某种原因被禁止，否则只需获取一个大数库（GMP）并执行明显的操作。1000！/500！具有不到5k个二进制数字，这可能不太大，可以在其上进行约1000次算术运算。如果您需要优化，则最坏情况是1000选择500，它仅具有1k个二进制数字。因此，要聪明地计算它，尽早进行除法而不是首先进行所有乘法，并且数字永远不会显着变大。 - Steve Jessop
3
由于1000000003 = 23 * 307 * 141623，您可以计算 (n chooses k) mod 23、307 和 141623，然后应用中国剩余定理[1]。在计算 n!、k! 和 (n-k)! 时，每一步都应该计算模数为23、307 和 141623 的所有内容，以防止溢出。
这样即使在32位机器上也可以避免溢出。
稍微改进一下是计算 (n chooses k) mod 141623 和 7061 (23 * 307) (编辑：但计算模反数7061可能有点棘手，所以我不会这样做)
对我的糟糕英语感到抱歉。
[1]http://en.wikipedia.org/wiki/Chinese_remainder_theorem
编辑2：我发现另一个潜在的问题是，在计算 n! mod 23（例如）时，它很可能是0，但这并不意味着 (n chooses k) mod 23 是0，因此您应该在计算 (n chooses k) 之前计算23除 n!、(n-k)! 和 k! 的次数。计算这个很容易，p 恰好被 n! 整除 floor(n/p) + floor(n/p²) + ... 次。如果恰好有23个数被 n!、k! 和 (n-k)! 整除，那么您就可以通过每次除以23的倍数来计算 (n chooses k) mod 23。307也是如此，但141623则不然。
- Matías Marquez
1
对于小质数23和307，你可以使用http://en.wikipedia.org/wiki/Lucas%27_theorem而不是计算幂。 - Steve Jessop
2
你可以使用你提供的递归公式，并对计算结果进行M取模。
- Henrik
1
这里是一个简单的例子：
(A * B * C) % N ... is equal to... ((A % N) * (B % N) * (C % N)) % N;
也就是说，您需要对每个操作数和乘积应用模运算，或者在它变成一个大数时进行模运算。最后，模数必须应用于整体结果。
- Nawaz
3
使用32位整数仍可能在1000000000*1000上导致溢出。 - Yakov Galka
@ybungalobill：应用
((1000000000%N)*(1000)%N)%N。 - Nawaz2请注意，问题中的模数为M，而不是N，并且给出的示例虽然实际上不是质数，但大约为十亿。因此，
1000000000％N仍然是1000000000。为避免溢出，您需要一个像N ^ 2一样大的整数类型（例如，如果可用，则为long long或int64_t）。 - Steve Jessop-1
使用斯特林逼近公式来计算二项式系数。然后像往常一样计算模数即可。
- Alex Reynolds
2
4近似值如何帮助计算模M下的二项式系数？在模算术中，近似值几乎没有意义。 - Steve Jessop
抱歉，我错过了近似部分。 - Quixotic
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接