找到大数的组合值 [英] To find combination value of large numbers

问题描述

我想为大整数找到（n选择r），我还必须找出该数字的mod。

  long long int select（int a，int b）
 {
 if（b> a）
 return（-1） 
 if（b == 0 || a == 1 || b == a）
 return（1）; 
 else 
 {
 long long int r =（（选择（a-1，b））％10000007+（选择（a-1，b- 1））％10000007）％10000007 ; 
 return r; 
} 
} 
  

我使用这段代码，得到TLE。如果有其他方法可以告诉我。

解决方案

我还没有评论的声誉，我想指出，rock321987的答案很好：

这是快速的 不能处理所有输入（

）。 它有一个输出符合uint64_t。

C（67，33）= 14,226,520,737,620,288,370 （验证正确性和大小）

b $ b

不幸的是，其他实现的8,829,174,638,479,413这是不正确的。还有其他方法来计算nCr，这不会像这样破坏，但这里真正的问题是没有尝试利用模数。

请注意p = 10000007是素数，这允许我们利用所有整数具有逆模p的事实，并且该逆是唯一的。此外，我们可以很快地发现逆。另一个问题有关于如何执行此操作的答案此处

1. > x / y mod p == x *（y inverse）mod p;和


2. xy mod p ==（x mod p）（y mod p）

修改其他代码一点，并概括问题我们有以下：

  #include< iostream> 
 #include< assert.h> 
 
 // p必须是素数且小于2 ^ 63 
 uint64_t inverseModp（uint64_t a，uint64_t p）{
 assert（p <（1ull < ））; 
 assert（a< p）; 
 assert（a！= 0） 
 uint64_t ex = p-2，result = 1; 
 while（ex> 0）{
 if（ex％2 == 1）{
 result =（result * a）％p; 
} 
 a =（a * a）％p; 
 ex / = 2; 
} 
 return result; 
} 
 
 // p必须是素数
 uint32_t nCrModp（uint32_t n，uint32_t r，uint32_t p）
 {
 assert（r < n）。 
 if（r> n-r）r = n-r; 
 if（r == 0）return 1; 
 if（n / p-（n-r）/ p> r / p）return 0; 
 
 uint64_t result = 1; //中间结果可能溢出32位
 
 for（uint32_t i = n，x = 1; i> r; --i，++ x）{
 if ！= 0）{
 result * = i％p; 
 result％= p; 
} 
 if（x％p！= 0）{
 result * = reverseModp（x％p，p）; 
 result％= p; 
} 
} 
返回结果; 
} 
 
 int main（）{
 uint32_t smallPrime = 17; 
 uint32_t medNum = 3001; 
 uint32_t halfMedNum = medNum>> 1; 
 std :: cout<< nCrModp（medNum，halfMedNum，smallPrime） std :: endl; 
 
 uint32_t bigPrime = 4294967291ul; // 2 ^ 32-5是最大素数2 ^ 32 
 uint32_t bigNum = 1ul<< 24; 
 uint32_t halfBigNum = bigNum>> 1; 
 std :: cout<< nCrModp（bigNum，halfBigNum，bigPrime） std :: endl; 
} 
  

对于任何32位输入，等待。为了证明一点，我包括了对24位n的计算，以及最大32位素数。我的个人电脑花了〜13秒来计算这个。检查 wolfram alpha 的答案，但是注意它可能超过那里的标准计算时间。

如果p比（nr）小得多，仍然有改进的余地，其中r <= nr 。例如，我们可以预先计算所有的倒数模p，而不是按需多次。

I want to find (n choose r) for large integers, and I also have to find out the mod of that number.

long long int choose(int a,int b)
{
    if (b > a)
        return (-1);
    if(b==0 || a==1 || b==a)
        return(1);
    else
    {
        long long int r = ((choose(a-1,b))%10000007+(choose(a-1,b-  1))%10000007)%10000007;
        return r;
    }
}

I am using this piece of code, but I am getting TLE. If there is some other method to do that please tell me.

解决方案

I don't have the reputation to comment yet, but I wanted to point out that the answer by rock321987 works pretty well:

It is fast and correct up to and including C(62, 31)

but cannot handle all inputs that have an output that fits in a uint64_t. As proof, try:

C(67, 33) = 14,226,520,737,620,288,370 (verify correctness and size)

Unfortunately, the other implementation spits out 8,829,174,638,479,413 which is incorrect. There are other ways to calculate nCr which won't break like this, however the real problem here is that there is no attempt to take advantage of the modulus.

Notice that p = 10000007 is prime, which allows us to leverage the fact that all integers have an inverse mod p, and that inverse is unique. Furthermore, we can find that inverse quite quickly. Another question has an answer on how to do that here, which I've replicated below.

This is handy since:

1. x/y mod p == x*(y inverse) mod p; and
2. xy mod p == (x mod p)(y mod p)

Modifying the other code a bit, and generalizing the problem we have the following:

#include <iostream>
#include <assert.h>

// p MUST be prime and less than 2^63
uint64_t inverseModp(uint64_t a, uint64_t p) {
    assert(p < (1ull << 63));
    assert(a < p);
    assert(a != 0);
    uint64_t ex = p-2, result = 1;
    while (ex > 0) {
        if (ex % 2 == 1) {
            result = (result*a) % p;
        }
        a = (a*a) % p;
        ex /= 2;
    }
    return result;
}

// p MUST be prime
uint32_t nCrModp(uint32_t n, uint32_t r, uint32_t p)
{
    assert(r <= n);
    if (r > n-r) r = n-r;
    if (r == 0) return 1;
    if(n/p - (n-r)/p > r/p) return 0;

    uint64_t result = 1; //intermediary results may overflow 32 bits

    for (uint32_t i = n, x = 1; i > r; --i, ++x) {
        if( i % p != 0) {
            result *= i % p;
            result %= p;
        }
        if( x % p != 0) {
            result *= inverseModp(x % p, p);
            result %= p;
        }
    }
    return result;
}

int main() {
    uint32_t smallPrime = 17;
    uint32_t medNum = 3001;
    uint32_t halfMedNum = medNum >> 1;
    std::cout << nCrModp(medNum, halfMedNum, smallPrime) << std::endl;

    uint32_t bigPrime = 4294967291ul; // 2^32-5 is largest prime < 2^32
    uint32_t bigNum = 1ul << 24;
    uint32_t halfBigNum = bigNum >> 1;
    std::cout << nCrModp(bigNum, halfBigNum, bigPrime) << std::endl;
}

Which should produce results for any set of 32-bit inputs if you are willing to wait. To prove a point, I've included the calculation for a 24-bit n, and the maximum 32-bit prime. My modest PC took ~13 seconds to calculate this. Check the answer against wolfram alpha, but beware that it may exceed the 'standard computation time' there.

There is still room for improvement if p is much smaller than (n-r) where r <= n-r. For example, we could precalculate all the inverses mod p instead of doing it on demand several times over.

这篇关于找到大数的组合值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！