當n非常大時，有效地計算nCr mod p

我需要高效地計算nCr mod p。現在，我寫了這段代碼，但它超出了時間限制。請建議更優化的解決方案。當n非常大時，有效地計算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。如果錯了，請指出！

來源

2013-11-02 OneMoreError

你正在使用哪個版本的python？ – inspectorG4dget

我正在使用Python 2.7.2 – OneMoreError

爲什麼你擔心溢出？ Python的整數類型沒有固定的存儲空間;它會佔用盡可能多的存儲空間。 –

從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（A，P-2，P）來計算模逆。這符合費馬小定理，該定理指出（a（p-1）與1模p一致），其中p是素數。因此它意味着（a ^（p-2）與a ^（ - 1）模p一致）。

C++到Python的轉換應該很容易:)

來源

2013-11-02 06:56:28 batbaatar

另外，請注意，modPow已經在Python中以'pow（）'的形式可用。 –

幫我出去了一噸。在其他地方很難找到這個實施。 – ryan1234

關於最後一個問題：我想在你的代碼的錯誤是計算產品，降低它模k，然後通過r!劃分結果。這與減數模k之前不一樣。例如，3*4/2 (mod 10) != 3*4 (mod 10)/2。

來源

2013-11-02 08:20:55

當n非常大時，有效地計算nCr mod p

回答

相關問題