Использование концепции модульной мультипликативной инверсии для расчета nCr % MOD

Я рассчитываю nCr% MOD для больших значений n

Я использую соотношение (n+1)Cr=(nCr)*(n+1)/(n+1-r)

Мне нужно перебирать цикл для разных значений n, сохраняя r постоянным.

llu fact=1;
/*The loop begins from i>=M+1 */
fact=(fact*(i-1)*modInverse(i-M,MOD))%MOD;  // Single statement executed during each iteration of loop


  Here I'm calculating (i-1)C(M-1)
  Here M and MOD are constant values 
  MOD=1000000009 and llu refers to unsigned long long

Что я делаю именно

(n+1)Cr % MOD = [ (nCr) * (n+1) * modInverse(n+1-r) ] % MOD

Здесь modInverse вычисляет модульную мультипликативную инверсию согласно следующему определению:

llu modPow(llu a, llu x, llu p)
{
    //calculates a^x mod p
    llu res = 1;
    while(x > 0)
    {
        if( x % 2 != 0)
        {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return (res%MOD);
}
llu modInverse(llu a, llu p)
{
    //calculates the modular multiplicative of a mod m assuming p is prime
    return modPow(a, p-2, p);
}

Теперь проблема в том, что я не получаю правильных значений nCr для больших значений n (порядка 10 ^ 6). Мой подход

(n+1)Cr % MOD = [ (nCr) * (n+1) * modInverse(n+1-r) ] % MOD

концептуально неправильно?


c++ conceptual
person CPPCoder    schedule 13.03.2014    source источник
comment
Я работаю над той же идеей, что и (a*b)%c= ((a%c)*(b%c))%c   -  person CPPCoder    schedule 14.03.2014
comment
Вы пробовали добавлять суффикс ULL или LLU при делении на 2? х /= 2LLU; Обычно при кодировании и не указании компилятору типа литералов возникают проблемы такого рода усечения.   -  person Salvador Medina    schedule 20.01.2015

Ответы (1)


arrow_upward
0
arrow_downward

Да, формула внизу математически верна.

Однако выполнение 2 умножений перед получением модуля увеличивает вероятность проблемы переполнения.

Например, MOD равно O(10^10), поэтому modInverse также равно O(10^10). Если n равно O (10 ^ 6), то произведение равно O (10 ^ 26), что равно O (2 ^ 86) и вызовет переполнение для uint64 и даст вам неправильный ответ. Вместо этого рассмотрим:

(n+1)Cr % MOD = [ ([(nCr) * (n+1)] % MOD) * modInverse(n+1-r) ] % MOD

Вас также может заинтересовать мой ответ на этот подозрительно похожий вопрос< /а>.

person Jim Wood    schedule 22.04.2015