Вычисление nCr mod p эффективно, когда n очень велико

Question

Мне нужно рассчитать nCr mod p эффективно. Прямо сейчас, я написал этот фрагмент кода, но он превышает срок. Пожалуйста, предложите более оптимальное решение.

Для моего случая, p = 10^9 + 7 and 1 ≤ n ≤ 100000000

Я должен также убедиться, что нет переполнения, как nCr mod p гарантированно поместился в 32 разрядное целое число, однако n! может превышать предел.

def nCr(n,k): 
    r = min(n-k,k) 
    k = max(n-k,k) 
    res = 1 
    mod = 10**9 + 7 

    for i in range(k+1,n+1): 
     res = res * i 
     if res > mod: 
      res = res % mod 

    res = res % mod 
    for i in range(1,r+1): 
     res = res/i 
    return res 

PS: Также я считаю, что мой код может быть не совсем корректным. Однако, похоже, это работает для небольших n правильно. Если это неправильно, укажите это!

Answer 1

http://apps.topcoder.com/wiki/display/tc/SRM+467 От:

long modPow(long a, long x, long p) { 
    //calculates a^x mod p in logarithmic time. 
    long res = 1; 
    while(x > 0) { 
     if(x % 2 != 0) { 
      res = (res * a) % p; 
     } 
     a = (a * a) % p; 
     x /= 2; 
    } 
    return res; 
} 

long modInverse(long a, long p) { 
    //calculates the modular multiplicative of a mod m. 
    //(assuming p is prime). 
    return modPow(a, p-2, p); 
} 
long modBinomial(long n, long k, long p) { 
// calculates C(n,k) mod p (assuming p is prime). 

    long numerator = 1; // n * (n-1) * ... * (n-k+1) 
    for (int i=0; i<k; i++) { 
     numerator = (numerator * (n-i)) % p; 
    } 

    long denominator = 1; // k! 
    for (int i=1; i<=k; i++) { 
     denominator = (denominator * i) % p; 
    } 

    // numerator/denominator mod p. 
    return (numerator* modInverse(denominator,p)) % p; 
} 

Обратите внимание, что мы используем modpow (а, р-2, р) для вычисления по модулю обратного. Это соответствует малой теореме Ферма, которая гласит, что (a^(p-1) конгруэнтно 1 по модулю p), где p - простое число. Отсюда следует, что (а^(р-2) совпадает с а^(- 1) по модулю р).

C++ для преобразования Python должно быть легко :)

Answer 2

О последнем вопросе: Я думаю, что ошибка в коде, чтобы вычислить продукт, уменьшить его по модулю k, а затем разделить результат на r!. Это не то же самое, что деление до уменьшения по модулю k. Например, 3*4/2 (mod 10) != 3*4 (mod 10)/2.