我们如何计算 N 选择 K 模素数而不溢出？
我们如何在 C 或 C++ 中计算 (N 选择 K)% M 而不调用溢出？
对于特定情况，当N (4<=N<=1000)和K (1<=K<=N)和M = 1000003 >。
How can we computer (N choose K)% M in C or C++ without invoking overflow ?
For the particular case when N (4<=N<=1000) and K (1<=K<=N) and M = 1000003.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
要计算 (n 选择 k) % M，您可以分别计算分母 (n!) 模 M 和分母 (k!*(n - k)!) 模 M，然后将分母乘以分母的模乘逆 (在米）。由于 M 是素数，因此可以使用费马小定理来计算乘法逆元。
以下链接（问题 SuperSum）有一个很好的解释，带有示例代码：
http://www.topcoder.com/wiki/display/tc/SRM+467
To compute (n choose k) % M, you can separately compute the nominator (n!) modulus M and the denominator (k!*(n - k)!) modulus M and then multiply the nominator by the denominator's modular multiplicative inverse (in M). Since M is prime, you can use Fermat's Little Theorem to calculate the multiplicative inverse.
There is a nice explanation, with sample code, on the following link (problem SuperSum):
http://www.topcoder.com/wiki/display/tc/SRM+467
由于 1000000003 = 23 * 307 * 141623，您可以计算（n 选择 k）mod 23、307 和 141623，然后应用中国提醒定理[1]。计算n!、k!时并且 (nk)!，您应该每一步都计算 mod 23、307 和 141623，以防止溢出。
这样即使在 32 位机器上也应该避免溢出。
一个小小的改进是计算 (n 选择 k) mod 141623 和 7061 (23 * 307) （编辑：但计算逆模 7061 可能有点棘手，所以我不会这样做）
我很抱歉为了我糟糕的英语。
[1]http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Edit2：我发现的另一个潜在问题是计算 n 时！ mod 23 （例如）它可能是 0，但这并不意味着 (n 选择 k) 是 0 mod 23，所以你应该计算 23 除了 n!, (nk)! 多少次和k！在计算之前（n选择k）。计算起来很简单，p 除以 n！正好是楼层(n/p) + 楼层(n/p²) + ... 次。如果碰巧 23 整除 n!除以 k 的次数相同！和 (nk)!，您每次都会继续计算 (n 选择 k) mod 23 除以 23 的每个倍数。这同样适用于 307，但不适用于 141623
Since 1000000003 = 23 * 307 * 141623 you can calculate (n choses k) mod 23, 307 and 141623 and then apply the chinese reminder theorem[1]. When calculating n!, k! and (n-k)!, you should calculate everythinng mod 23, 307 and 141623 each step to prevent overflow.
In this way you should avoid overflow even in 32bit machines.
A little improvement would be to calculate (n choses k) mod 141623 and 7061 (23 * 307) (edit: but it can be a little tricky to calculate the inverse modulus 7061, so I wouldn't do this)
I'm sorry for my poor English.
[1]http://en.wikipedia.org/wiki/Chinese_remainder_theorem
Edit2: Another potentially problem I've found is when calculating n! mod 23 (for example) it will probably be 0, but that doesn't implies that (n choses k) is 0 mod 23, so you should count how many times 23 divides n!, (n-k)! and k! before calculating (n choses k). Calculating this is easy, p divides n! exactly floor(n/p) + floor(n/p²) + ... times. If it happens that 23 divides n! the same times it divides k! and (n-k)!, the you proceed to calculate (n choses k) mod 23 dividing by 23 every multipler of it every time.The same applies for 307, but not for 141623
您可以使用您提供的链接中的递归公式并进行 mod M 的计算。
You could use the recursive formula from the link you gave and do the calculation mod M.
这是一个简单的例子：
也就是说，您只需对每个操作数和乘积应用模数，或者当它变得很大时就应用模数。最后，模数必须应用于整体结果。
Here is a simple example:
That is, all you need to apply modulus to every operand and product, or as soon as it becomes big a number. And last the modulus must apply to the overall result.
使用斯特林近似计算二项式系数。然后像往常一样计算模数即可。
Use Stirling's approximation to calculate the binomial coefficient. Then just calculate the modulus as usual.