c++ - 在C++中计算二项式系数模块素数p

问题陈述:计算二项式系数C(n，k)mod p。这里p是素数。
我已经在网上做了一些研究，但是我仍然不明白为什么以下代码可解决此问题:

factorial[0] = 1;
for (int i = 1; i <= MAXN; i++) {//compute factorial
    factorial[i] = factorial[i - 1] * i % m;
}
long long binomial_coefficient(int n, int k) {
    return factorial[n] * inverse(factorial[k] * factorial[n - k] % m) % m;//I don't get it why we have to multiply with inverse(factorial[k] * factorial[n - k] % m)
}

我知道模逆的定义，但是我仍然很困惑它在这里如何与之相关。有人可以帮我澄清一下此代码吗？

最佳答案

阶乘formula C(n, k) = n! / (k! (n-k)!)可以重写为C(n, k) k! (n-k)! = n!。然后:

两侧都带有mod p:C(n, k) k! (n-k)! ≡ n! mod p;

乘以模逆:C(n, k) k! (n-k)! inverse(k! (n-k)!) ≡ n! inverse(k! (n-k)!) mod p;

简化a inv(a) = 1:C(n, k) ≡ n! inverse(k! (n-k)!) mod p。

后者等效于C(n, k) mod p = ((n! mod p) (inverse(k! (n-k)!) mod p)) mod p。

关于c++ - 在C++中计算二项式系数模块素数p，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/64997030/