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

Question

问题陈述：计算二项式系数 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)
}

我知道 modular inverse 的定义，但我仍然很困惑它在这里的相关性。有人可以帮我澄清这段代码吗？

Answer 1

阶乘formulaC(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++ 中计算二项式系数模素数 p

Compute binomial coefficient module prime p in C++

c++

primes

modulo