我们如何计算N选择K模数为素数而不溢出？

Question

如何在不调用溢出的情况下在C或C++中计算机(N选择K)%M？

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

Answer 1

要计算(n选择k)%M,你可以分别计算分母(n!)模数M和分母(k!*(n - k)!)模数M,然后将分母乘以分母的模乘法逆(在M).由于M是素数,你可以使用费马的小定理来计算乘法逆.

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

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