因此，这是解决问题的方法。

当然，您知道公式：

comb(n,k) = n!/(k!*(n-k)!) = (n*(n-1)*...(n-k+1))/k!

（请参阅http://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients）

您知道如何计算分子：

long long res = 1;
for (long long i = n; i > n- k; --i) {
  res = (res * i) % p;
}

现在，由于p为质数，因此 与p互质数 的每个整数的倒数都得到了很好的定义，即可以找到-1。这可以使用费马定理a p-1 = 1（mod p）=> a * a p-2 = 1（mod p）做到-1 = a p-2。现在，您需要做的就是实现快速幂运算（例如，使用二进制方法）：

long long degree(long long a, long long k, long long p) {
  long long res = 1;
  long long cur = a;

  while (k) {
    if (k % 2) {
      res = (res * cur) % p;
    }
    k /= 2;
    cur = (cur * cur) % p;
  }
  return res;
}

现在，您可以将分母添加到我们的结果中：

long long res = 1;
for (long long i = 1; i <= k; ++i) {
  res = (res * degree(i, p- 2)) % p;
}

请注意，我在各处都使用long long以避免类型溢出。当然，您不需要做k幂运算-您可以计算k！（mod p），然后只除一次：

long long denom = 1;
for (long long i = 1; i <= k; ++i) {
  denom = (denom * i) % p;
}
res = (res * degree(denom, p- 2)) % p;

编辑：如果k> = p k，则按@dbaupp的注释！将等于0模p，并且将不定义（k！）^-1。为了避免这种情况，首先计算p在n *（n-1）…（n-k
+ 1）和k中的度数！并比较它们：

int get_degree(long long n, long long p) { // returns the degree with which p is in n!
  int degree_num = 0;
  long long u = p;
  long long temp = n;

  while (u <= temp) {
    degree_num += temp / u;
    u *= p;
  }
  return degree_num;
}

long long combinations(int n, int k, long long p) {
  int num_degree = get_degree(n, p) - get_degree(n - k, p);
  int den_degree = get_degree(k, p);

  if (num_degree > den_degree) {
    return 0;
  }
  long long res = 1;
  for (long long i = n; i > n - k; --i) {
    long long ti = i;
    while(ti % p == 0) {
      ti /= p;
    }
    res = (res * ti) % p;
  }
  for (long long i = 1; i <= k; ++i) {
    long long ti = i;
    while(ti % p == 0) {
      ti /= p;
    }
    res = (res * degree(ti, p-2, p)) % p;
  }
  return res;
}

编辑：还有一个可以添加到上面的解决方案的优化-代替计算k！中每个倍数的反数，我们可以计算k！（mod
p），然后计算该数的反数。因此，我们只需要为对数支付一次对数。当然，我们必须再次丢弃每个倍数的p个除数。我们只需要使用以下命令更改最后一个循环：

long long denom = 1;
for (long long i = 1; i <= k; ++i) {
  long long ti = i;
  while(ti % p == 0) {
    ti /= p;
  }
  denom = (denom * ti) % p;
}
res = (res * degree(denom, p-2, p)) % p;