nCr mod p effizient berechnen, wenn n sehr groß ist

Question

Ich muss nCr mod p effizient berechnen. Im Moment habe ich dieses Stück Code geschrieben, aber es überschreitet das Zeitlimit. Bitte schlagen Sie eine optimalere Lösung vor.

Für meinen Fall p = 10^9 + 7 and 1 ≤ n ≤ 100000000

Ich muss auch darauf achten, dass kein Überlauf ist als nCr mod p garantiert in 32-Bit-Integer passen, kann jedoch n! den Grenzwert überschreiten.

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: Auch ich denke, dass mein Code möglicherweise nicht vollständig korrekt ist. Allerdings scheint es für kleine n richtig zu funktionieren. Wenn es falsch ist, bitte zeig es!

Answer 1

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

Hinweis, die wir verwenden modpow (a, P-2, P), um den mod invers zu berechnen. Dies steht in Übereinstimmung mit Fermat's kleinem Satz, der besagt, dass (a^(p-1) zu 1 modulo p kongruent ist) wobei p prim ist. Es impliziert also, dass (a^(p-2) zu einem^(- 1) modulo p) kongruent ist.

C++ Python Konvertierung sollte einfach sein :)

Answer 2

über die letzte Frage: Ich denke, dass der Fehler im Code ist, das Produkt zu berechnen, reduzieren sie k Modulo, und dann das Ergebnis durch r!. Dies ist nicht das Gleiche wie das Dividieren vor dem Reduzieren von Modulo k. Zum Beispiel 3*4/2 (mod 10) != 3*4 (mod 10)/2.