快速 n 为大 n 选择 k mod p？

Question

我所说的“大 n”是指数以百万计的东西。 p 是素数。

我已经尝试过 http://apps.topcoder.com/wiki/display/tc/SRM+467 但该功能似乎不正确（我用 144 选择 6 mod 5 对其进行了测试，当它应该给我时它给了我 0 2)

我试过 http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 但我不完全理解

我还制作了一个使用逻辑 (combinations(n-1, k-1, p)%p + combination(n-1, k, p)%p) 的记忆递归函数，但它给了我堆栈溢出问题，因为n 很大

我试过卢卡斯定理，但它似乎很慢或不准确。

我要做的就是创建一个快速/准确的 n 为大 n 选择 k mod p。如果有人可以帮助我展示一个很好的实现，我将不胜感激。谢谢。

根据要求，对于大 n 命中堆栈溢出的记忆版本：

 std::map<std::pair<long long, long long>, long long> memo;

long long combinations(long long n, long long k, long long p){
   if (n  < k) return 0;
   if (0 == n) return 0;
   if (0 == k) return 1;
   if (n == k) return 1;
   if (1 == k) return n;

   map<std::pair<long long, long long>, long long>::iterator it;

   if((it = memo.find(std::make_pair(n, k))) != memo.end()) {
        return it->second;
   }
   else
   {
        long long value = (combinations(n-1, k-1,p)%p + combinations(n-1, k,p)%p)%p;
        memo.insert(std::make_pair(std::make_pair(n, k), value));
        return value;
   }
}

原文由 John Smith 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

你当然知道公式：

 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) 等 a -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;

编辑：根据@dbaupp 的评论 if k >= p the k!将等于 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!(mod p) 然后计算该数字的倒数，而不是计算 k! 中每个倍数的倒数。因此，我们只需要支付一次取幂的对数。当然，我们必须再次丢弃每个倍数的 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;

原文由 Ivaylo Strandjev 发布，翻译遵循 CC BY-SA 3.0 许可协议