8

nCr mod p効率的に計算する必要があります。今、このコードを書きましたが、制限時間を超えています。より最適なソリューションを提案してください。

私の場合、p = 10^9 + 7 and 1 ≤ n ≤ 100000000

nCr mod p32 ビット整数に収まることが保証されているため、オーバーフローがないことも確認する必要があり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は正しく機能するようです。間違っていたら指摘してください！

4

2 に答える 2

11

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) を使用して mod 逆を計算することに注意してください。これは、(a^(p-1) は p を法とする 1 に合同である) と述べているフェルマーの小定理に従っており、ここで p は素数です。したがって、(a^(p-2) は a^(-1) modulo p に合同) であることを意味します。

C++ から Python への変換は簡単なはずです :)

于 2013-11-02T06:56:28.613 に答える
2

最後の質問について: あなたのコードの間違いは、積を計算し、モジュロを減らしk、結果を で割ることだと思いますr!。これは modulo を減らす前の除算と同じではありませんk。たとえば、3*4 / 2 (mod 10) != 3*4 (mod 10) / 2.

于 2013-11-02T08:20:55.007 に答える