gpt4 book ai didi

c++ - 我们如何计算 N choose K modules a prime number 而不会溢出?

转载 作者:可可西里 更新时间:2023-11-01 18:11:40 26 4
gpt4 key购买 nike

我们如何在不调用溢出的情况下在 C 或 C++ 中计算 ( N choose K)% M?

对于 N (4<=N<=1000)K (1<=K<=N)M = 1000003 的特殊情况.

最佳答案

要计算 (n choose k) % M,可以分别计算分母 (n!) 模 M 和分母 (k!*(n - k)!) 模 M,然后将分母乘以分母的模乘法逆(在 M 中)。由于M是素数,可以利用费马小定理计算乘法逆元。

在以下链接(问题 SuperSum)上有一个很好的解释和示例代码:

http://www.topcoder.com/wiki/display/tc/SRM+467

关于c++ - 我们如何计算 N choose K modules a prime number 而不会溢出?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4638988/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com