快速ñ选择k模p对于大的n？ [英] Fast n choose k mod p for large n?

问题描述

我所说的大N的东西，在数以百万计。 p为素数。

我已经试过 <一href="http://apps.top$c$cr.com/wiki/display/tc/SRM+467">http://apps.top$c$cr.com/wiki/display/tc/SRM+467 但功能似乎是不正确的（我用144测试它选择6mod5，这让我0时，它应该给我2）

我已经试过 <一href="http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690">http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 但我不明白，这完全

我也做了一个使用逻辑（组合（N-1，K-1，P）％，P +组合（N-1，K，P）％P），但它给了我一个堆叠memoized递归函数溢出的问题，因为n较大

我已经试过卢卡斯定理，但它似乎是减缓或不准确的。

所有我想要做的是建立一个快速/准确ñ选择k模p对于大的n。如果有人可以帮助给我一个很好的实现这一点，我会非常感激。谢谢你。

根据要求，击中堆栈memoized版本溢出的大的n：

 的std ::地图＆LT;的std ::对＆LT;很长很长，很长很长＆gt;中久长＆GT;备忘录;

长长的组合（久N久，长长的K，很长很长P）{
   如果（N＆LT; K）返回0;
   如果（0 == N）返回0;
   如果（0 == k）的回报1;
   如果（N == k）的回报1;
   如果（1 == k）的回报N;

   地图＆LT;的std ::对＆LT;很长很长，很长很长＆gt;中久长＆GT;：迭代它;

   如果（（IT = memo.find（的std :: make_pair（N，K）））！= memo.end（））{
        返回它 - ＆gt;第二个;
   }
   其他
   {
        长长值=（组合（N-1，K-1，p）的％的p +的组合（N-1，K，P）％P）％磷;
        memo.insert（的std :: make_pair（的std :: make_pair（N，K），值））;
        返回值;
   }
}
 

解决方案

所以，在这里是如何解决你的问题。

当然，你知道公式：

 梳子（N，K）= N！/（K！*（NK）！）=（N *（N-1）* ...（N-K + 1 ））/ K！
 

（见<一href="http://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients" rel="nofollow">http://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients)

您知道如何计算分子：

 长长的解析度= 1;
对于（很久很久我= N，I＆GT; N- K表; --i）{
  RES =（RES * I）％P;
}
 

现在，作为p为素数的每个整数，它是倒数的互素以P 的是明确的，即一个 ¹ 可以找到。这时可以使用费马大定理的一个 ^P-1 = 1（模p）=> A * A ^P-2 = 1（模p）等等来实现< SUP> 1 = A ^P-2 。 现在，所有你需要做的是（例如使用二进制方法）来实现快速幂：

 长长度（长一长，很长很长K，很长很长P）{
  长长的解析度= 1;
  长长CUR =一个;

  而（K）{
    如果（K％2）{
      RES =（RES * CUR）％P;
    }
    K / = 2;
    CUR =（CUR * CUR）％P;
  }
  返回水库;
}
 

现在，您可以添加分母为我们的结果是：

 长长的解析度= 1;
对（很长很长I = 1; I＆LT; = K ++ I）{
  RES =（RES *度（I，P-2））％P;
}
 

请注意我用很长很长，到处避免类型的溢出。 ！当然，你并不需要做 K 幂 - 你可以计算K（模p），然后除以只有一次：

 很长很长DENOM = 1;
对（很长很长I = 1; I＆LT; = K ++ I）{
  DENOM =（DENOM * I）％P;
}
RES =（RES *学位（DENOM，对2））％P;
 

编辑：按@ dbaupp的评论，如果K> = P k个！将等于0模p和^（K！） - 1将不被限定。为了避免这种情况的第一计算的程度与其中p是在正*（N-1）...（N-K + 1）和在k-！并加以比较：

  INT get_degree（长N久，很长很长P）{//返回学历，其中p为N！
  INT degree_num = 0;
  长长的U =磷;
  长长的TEMP = N;

  而（U＆LT; =临时）{
    degree_num + =温度/ U;
    U * = P;
  }
  返回degree_num;
}

长长的组合（INT N，INT K，很长很长P）{
  INT num_degree = get_degree（N，P） -  get_degree（N  -  K，P）;
  INT den_degree = get_degree（K，P）;

  如果（num_degree＆GT; den_degree）{
    返回0;
  }
  长长的解析度= 1;
  对于（很久很久我= N，I＆GT; N  -  K; --i）{
    长长的TI =我;
    而（TI％P == 0）{
      TI / = P;
    }
    RES =（RES * TI）％P;
  }
  对（很长很长I = 1; I＆LT; = K ++ I）{
    长长的TI =我;
    而（TI％P == 0）{
      TI / = P;
    }
    RES =（RES *度（TI，P-2，P））％P;
  }
  返回水库;
}
 

编辑：！还有一个优化可添加到上述的溶液 - 而不是计算在k-每个多的倒数！我们可以计算K（模p），然后计算该数的倒数。因此，我们要付出的对数为幂只有一次。当然，我们再次丢弃每个倍数为P约数。我们只需要改变的最后一个循环这一点：

 很长很长DENOM = 1;
对（很长很长I = 1; I＆LT; = K ++ I）{
  长长的TI =我;
  而（TI％P == 0）{
    TI / = P;
  }
  DENOM =（DENOM * TI）％P;
}
RES =（RES *学位（DENOM，P-2，P））％P;
 

What I mean by "large n" is something in the millions. p is prime.

I've tried http://apps.topcoder.com/wiki/display/tc/SRM+467 But the function seems to be incorrect (I tested it with 144 choose 6 mod 5 and it gives me 0 when it should give me 2)

I've tried http://online-judge.uva.es/board/viewtopic.php?f=22&t=42690 But I don't understand it fully

I've also made a memoized recursive function that uses the logic (combinations(n-1, k-1, p)%p + combinations(n-1, k, p)%p) but it gives me stack overflow problems because n is large

I've tried Lucas Theorem but it appears to be either slow or inaccurate.

All I'm trying to do is create a fast/accurate n choose k mod p for large n. If anyone could help show me a good implementation for this I'd be very grateful. Thanks.

As requested, the memoized version that hits stack overflows for large 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;
   }  
}

解决方案

So, here is how you can solve your problem.

Of course you know the formula:

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

(See http://en.wikipedia.org/wiki/Binomial_coefficient#Computing_the_value_of_binomial_coefficients)

You know how to compute the numerator:

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

Now, as p is prime the reciprocal of each integer that is coprime with p is well defined i.e. a^-1 can be found. And this can be done using Fermat's theorem a^p-1=1(mod p) => a*a^p-2=1(mod p) and so a^-1=a^p-2. Now all you need to do is to implement fast exponentiation(for example using the binary method):

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

And now you can add the denominator to our result:

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

Please note I am using long long everywhere to avoid type overflow. Of course you don't need to do k exponentiations - you can compute k!(mod p) and then divide only once:

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

EDIT: as per @dbaupp's comment if k >= p the k! will be equal to 0 modulo p and (k!)^-1 will not be defined. To avoid that first compute the degree with which p is in n*(n-1)...(n-k+1) and in k! and compare them:

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

EDIT: There is one more optimization that can be added to the solution above - instead of computing the inverse number of each multiple in k!, we can compute k!(mod p) and then compute the inverse of that number. Thus we have to pay the logarithm for the exponentiation only once. Of course again we have to discard the p divisors of each multiple. We only have to change the last loop with this:

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;

这篇关于快速ñ选择k模p对于大的n？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！