Calcolo nCr mod in modo efficiente quando n è molto grande

Question

Ho bisogno di calcolare nCr mod p in modo efficiente. In questo momento, ho scritto questo pezzo di codice, ma supera il limite di tempo. Si prega di suggerire una soluzione più ottimale.

per il mio caso, p = 10^9 + 7 and 1 ≤ n ≤ 100000000

devo fare anche in modo che non v'è alcun trabocco come nCr mod p è garantito per adattarsi a 32 bit integer, tuttavia n! possono superare il limite.

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: Inoltre, penso che il mio codice potrebbe non essere completamente corretto. Tuttavia, sembra funzionare correttamente per il piccolo n. Se è sbagliato, perfavore segnalalo!

Answer 1

Da 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; 
} 

Si noti che usiamo modpow (a, p-2, p) per calcolare l'inverso mod. Questo è in accordo con il Piccolo Teorema di Fermat che afferma che (a^(p-1) è congruente a 1 modulo p) dove p è primo. Quindi implica che (a^(p-2) è congruente ad un^(- 1) modulo p).

C++ per la conversione Python dovrebbe essere facile :)

Answer 2

Circa l'ultima domanda: penso che l'errore nel codice è quello di calcolare il prodotto, ridurlo modulo k, e quindi dividere il risultato per r!. Non è la stessa cosa che si divide prima di ridurre il modulo k. Ad esempio, 3*4/2 (mod 10) != 3*4 (mod 10)/2.