Tính ncr mod p hiệu quả khi n là rất lớn

Question

Tôi cần tính nCr mod p hiệu quả. Ngay bây giờ, tôi đã viết đoạn mã này, nhưng nó vượt quá giới hạn thời gian. Vui lòng đề xuất giải pháp tối ưu hơn.

Đối với trường hợp của tôi, p = 10^9 + 7 and 1 ≤ n ≤ 100000000

Tôi có cũng để đảm bảo rằng không có tràn như nCr mod p được đảm bảo để phù hợp với 32 bit số nguyên, tuy nhiên n! có thể vượt quá giới hạ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: Ngoài ra tôi nghĩ mã của tôi có thể không hoàn toàn chính xác. Tuy nhiên, có vẻ như nó hoạt động chính xác cho n nhỏ. Nếu nó sai, xin vui lòng chỉ ra!

Answer 1

Từ 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; 
} 

Chú ý rằng chúng tôi sử dụng modpow (a, p-2, p) để tính nghịch đảo mod. Điều này phù hợp với Định lý nhỏ của Fermat, trong đó nói rằng (a^(p-1) là đồng dư với 1 modulo p) trong đó p là số nguyên tố. Do đó nó ngụ ý rằng (a^(p-2) là đồng dư với^(- 1) modulo p).

C++ để chuyển đổi Python nên dễ :)

Answer 2

Về câu hỏi cuối cùng: Tôi nghĩ rằng sai lầm trong mã của bạn là để tính toán sản phẩm, giảm nó modulo k, và sau đó chia kết quả bởi r!. Điều này không giống như chia trước khi giảm modulo k. Ví dụ: 3*4/2 (mod 10) != 3*4 (mod 10)/2.