快速ñ选择模p对于大的n？快速ñ选择模p对于大的n？(Fast n choose k mod p f

我所说的“大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但我不完全理解

我还提出，使用逻辑电路（组合第（n-1，K-1，P）％P +的组合（N-1，K，P）％P），但它给我堆栈溢出的问题，因为一个memoized递归函数n是大

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

所有我想要做的就是创建一个快速/准确ñ选择模p为大的n。如果有人可以帮助显示我要一个很好的实现，我会非常感激。谢谢。

按照要求，命中栈memoized版本大的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;
   }  
}

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是素数的每一个整数的倒数即互质与对被很好地定义即^-1可以找到。并且这可以使用费马定理的^p-1 = 1（mod p）的=> A * A ^P-2 = 1（mod p）的等等^-1 =一个^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;
}

请注意，我用的很长很长，到处避免类型溢出。当然，你并不需要做k幂-你可以计算K（模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的评论，如果K> = P 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-每个多的倒数！我们可以计算K（模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;

Answer 2:

对于大型k ，我们可以通过利用两个基本事实显著降低工作：

如果p是一个素数，的指数p为素因式分解n! 由下式给出(n - s_p(n)) / (p-1)其中s_p(n)是中的数字的总和n在基座p表示（因此对于p = 2 ，它的popcount）。因此的指数p中的质因数分解choose(n,k)是(s_p(k) + s_p(nk) - s_p(n)) / (p-1)特别地，它是零，如果且仅当加入k + (nk)在碱进行时没有进位p （指数为携带的数量）。
威尔逊定理： p为素数，当且仅当(p-1)! ≡ (-1) (mod p) (p-1)! ≡ (-1) (mod p) 。

的指数p中的因式分解n! 通常是由计算

long long factorial_exponent(long long n, long long p)
{
    long long ex = 0;
    do
    {
        n /= p;
        ex += n;
    }while(n > 0);
    return ex;
}

对于整除的检查choose(n,k)由p是不是绝对必要的，但它是合理的，有第一次，因为它会经常发生的情况，然后它的较少的工作：

long long choose_mod(long long n, long long k, long long p)
{
    // We deal with the trivial cases first
    if (k < 0 || n < k) return 0;
    if (k == 0 || k == n) return 1;
    // Now check whether choose(n,k) is divisible by p
    if (factorial_exponent(n) > factorial_exponent(k) + factorial_exponent(n-k)) return 0;
    // If it's not divisible, do the generic work
    return choose_mod_one(n,k,p);
}

现在，让我们来仔细看看n! 。我们的数字分开≤ n进入的倍数p和数字互质p 。同

n = q*p + r, 0 ≤ r < p

的倍数p贡献p^q * q! 。数字互质p贡献的产物(j*p + k), 1 ≤ k < p为0 ≤ j < q ，和的产物(q*p + k), 1 ≤ k ≤ r 。

对于数字互质p我们只感兴趣的贡献模p 。每个完整的运行的j*p + k, 1 ≤ k < p是全等(p-1)! 模p ，因此共它们产生的贡献(-1)^q模p 。最后一个（可能）不完整的运行产生r! 模p 。

因此，如果我们写

n   = a*p + A
k   = b*p + B
n-k = c*p + C

我们得到

choose(n,k) = p^a * a!/ (p^b * b! * p^c * c!) * cop(a,A) / (cop(b,B) * cop(c,C))

其中cop(m,r)是所有数的乘积互质p被≤ m*p + r 。

有两种可能性， a = b + c和A = B + C ，或a = b + c + 1个A = B + C - p 。

在我们的计算中，我们已经事先消除了第二种可能性，但这不是必需的。

在第一种情况下，明确权力p取消了，我们只剩下

choose(n,k) = a! / (b! * c!) * cop(a,A) / (cop(b,B) * cop(c,C))
            = choose(a,b) * cop(a,A) / (cop(b,B) * cop(c,C))

任何权力p分choose(n,k)来自choose(a,b) -在我们的情况下，会出现没有，因为我们之前已经淘汰这种情况下-和，虽然cop(a,A) / (cop(b,B) * cop(c,C))不需要是一个整数（例如考虑choose(19,9) (mod 5)考虑到表达模时p ， cop(m,r)减小到(-1)^m * r! ，因此，由于a = b + c ，则(-1)取消和我们留下的

choose(n,k) ≡ choose(a,b) * choose(A,B) (mod p)

在第二种情况下，我们发现

choose(n,k) = choose(a,b) * p * cop(a,A)/ (cop(b,B) * cop(c,C))

由于a = b + c + 1 。在最后一位的进位意味着A < B所以模p

p * cop(a,A) / (cop(b,B) * cop(c,C)) ≡ 0 = choose(A,B)

（其中，我们可以用一个乘法由模逆替换的划分，或把它看作有理数的一致性，这意味着该分子是由整除p ）。无论如何，我们再次找到

choose(n,k) ≡ choose(a,b) * choose(A,B) (mod p)

现在，我们可以重现的choose(a,b)的一部分。

例：

choose(144,6) (mod 5)
144 = 28 * 5 + 4
  6 =  1 * 5 + 1
choose(144,6) ≡ choose(28,1) * choose(4,1) (mod 5)
              ≡ choose(3,1) * choose(4,1) (mod 5)
              ≡ 3 * 4 = 12 ≡ 2 (mod 5)

choose(12349,789) ≡ choose(2469,157) * choose(4,4)
                  ≡ choose(493,31) * choose(4,2) * choose(4,4
                  ≡ choose(98,6) * choose(3,1) * choose(4,2) * choose(4,4)
                  ≡ choose(19,1) * choose(3,1) * choose(3,1) * choose(4,2) * choose(4,4)
                  ≡ 4 * 3 * 3 * 1 * 1 = 36 ≡ 1 (mod 5)

现在执行：

// Preconditions: 0 <= k <= n; p > 1 prime
long long choose_mod_one(long long n, long long k, long long p)
{
    // For small k, no recursion is necessary
    if (k < p) return choose_mod_two(n,k,p);
    long long q_n, r_n, q_k, r_k, choose;
    q_n = n / p;
    r_n = n % p;
    q_k = k / p;
    r_k = k % p;
    choose = choose_mod_two(r_n, r_k, p);
    // If the exponent of p in choose(n,k) isn't determined to be 0
    // before the calculation gets serious, short-cut here:
    /* if (choose == 0) return 0; */
    choose *= choose_mod_one(q_n, q_k, p);
    return choose % p;
}

// Preconditions: 0 <= k <= min(n,p-1); p > 1 prime
long long choose_mod_two(long long n, long long k, long long p)
{
    // reduce n modulo p
    n %= p;
    // Trivial checks
    if (n < k) return 0;
    if (k == 0 || k == n) return 1;
    // Now 0 < k < n, save a bit of work if k > n/2
    if (k > n/2) k = n-k;
    // calculate numerator and denominator modulo p
    long long num = n, den = 1;
    for(n = n-1; k > 1; --n, --k)
    {
        num = (num * n) % p;
        den = (den * k) % p;
    }
    // Invert denominator modulo p
    den = invert_mod(den,p);
    return (num * den) % p;
}

为了计算模逆，可以使用费马（所谓小）定理

如果p是素数， a不被整除p ，则a^(p-1) ≡ 1 (mod p) 。

并计算出逆作为a^(p-2) (mod p) ，或使用适用的方法，以更广泛的参数，扩展欧几里德算法或持续分数展开，这给你的任何一对互质的模逆（正）整数：

long long invert_mod(long long k, long long m)
{
    if (m == 0) return (k == 1 || k == -1) ? k : 0;
    if (m < 0) m = -m;
    k %= m;
    if (k < 0) k += m;
    int neg = 1;
    long long p1 = 1, p2 = 0, k1 = k, m1 = m, q, r, temp;
    while(k1 > 0) {
        q = m1 / k1;
        r = m1 % k1;
        temp = q*p1 + p2;
        p2 = p1;
        p1 = temp;
        m1 = k1;
        k1 = r;
        neg = !neg;
    }
    return neg ? m - p2 : p2;
}

如计算a^(p-2) (mod p) ，这是一个O(log p)算法，对于某些输入它的显著更快（它实际上是O(min(log k, log p))因此对于小k和大p ，这是相当快），对其他人来说是比较慢。

总体而言，我们需要这样最多O（log_p K）来计算二项式系数模p ，其中每个二项式系数至多需要O（P）操作，生成O的总复杂性（P * log_p k）的操作。当k比显著较大p ，比所述好得多O(k)溶液中。对于k <= p ，其降低到O(k)一些开销溶液。

文章来源: Fast n choose k mod p for large n?