c++ - 如何为大输入找到选择（m，n）％P？

Question

P = (10^9 + 7)
Choose(m, n) = m! / (n! * (m - n)!)

我想计算Choose(m, n) mod P大m和的值n。我怎样才能在 C++ 中做到这一点？

Answer 1

这就是我使用的，因为它有一个相当好的范围，没有太多的中间溢出。然而 C(n,k) 变大很快，毕竟它是 O(n^k)。

size_t N_choose_K(size_t n, size_t k)
{
    size_t numer = 1;
    size_t denom = 1;
    if (k > n - k) {
        k = n - k;
    }
    while (k > 0) {
        numer *= n;
        denom *= k;
        --n; --k;
    }
    return numer / denom;
}

编辑：假设您需要积分结果。如果需要，您可以移动到浮点结果并获得更大的范围，并且可以承受失去准确性。

Answer 2

您可以使用乘法在Z _p下闭合的事实，这意味着：ab mod p = (a mod p) (b mod p) mod p。使用这个定理，可以有效地计算a ^b mod p（例如，这个Python 实现.

接下来我们可以利用欧拉定理说：a ^-1 mod p=a ^(p-2) mod p。

现在我们知道了这些事实，我们可以提出一个有效的解决方案：首先我们将分子中的所有元素相乘，因此这是从k+1（包括）到n的范围，并且由于这是一个乘法，我们可以总是执行一个模：

long long numerator(int n, int k, int p) {
    long long l = 1;
    for(int j = k+1; j <= n; j++) {
        l = (l*j)%p;
    }
    return l;
}

现在我们仍然需要将它除以(nk)！. 我们可以通过首先计算(nk) 来做到这一点！mod p就像我们在前面的代码片段中所做的那样：

long long denominator(int n, int k, int p) {
    long l = 1;
    for(int j = 2; j <= n-k; j++) {
        l = (l*j)%p;
    }
    return l;
}

现在为了对其进行划分，我们可以对 的结果使用欧拉定理denominator。因此我们首先pow用模数实现函数：

long long pow(long long a, int k, int p) {
    if(k == 0) {
        return 1;
    }
    long long r = pow((a*a)%p,k>>0x01,p);
    if((k&0x01) == 0x01) {//odd number
        r = (r*a)%p;
    }
    return r;
}

现在我们可以将它们合并在一起，例如：

long long N_choose_K(int n, int k, int p) {
    long long num = numerator(n,k,p);
    long long den = denominator(n,k,p);
    return (num*pow(den,p-2,p))%p;
}

所以你基本上要做的是你确定 Z p 中的分子，Z p 中分母的值，然后你使用欧拉定理找到 Z _pnum中分母_的den倒数，这样你_就可以乘以并执行最后一个模手术。然后你就可以退货了。