时间戳

首页 > 解决方案 > 在 C++ 中计算二项式系数模块素数 p

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)
}

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

标签： c++primesmodulo

解决方案

阶乘公式 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。

推荐阅读