我们如何在不调用溢出的情况下在 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)上有一个很好的解释和示例代码:
关于c++ - 我们如何计算 N choose K modules a prime number 而不会溢出？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4638988/