c++ - 大きな入力に対して Choose(m, n) % P を見つける方法は?

Question

P = (10^9 + 7)
Choose(m, n) = m! / (n! * (m - n)!)

Choose(m, n) mod P大きなmとの値を計算したいn。C++ でそれを行うにはどうすればよいですか?

Answer 1

乗算がZ _pの下で閉じているという事実を使用できます。つまり、ab mod p = (a mod p) (b mod p) mod pです。この定理を使用すると、a b mod p を効果的に計算できます⁽たとえば、このPython 実装.

次に、 a ^-1 mod p=a ^(p-2) mod pというオイラーの定理を利用できます。

これらの事実がわかったので、効果的な解決策を考え出すことができます。まず、分子のすべての要素を乗算します。これはk+1 (包括的) からnまでの範囲であり、これは乗算であるため、次のことができます。常にモジュロを実行します。

long long numerator(int n, int k, int p) {
    long long l = 1;
    for(int j = k+1; j <= n; j++) {
        l = (l*j)%p;
    }
    return l;
}

これを(nk)で割る必要があります。. これを行うには、まず(nk) を計算します。mod pは、前のコード フラグメントで既に行ったように:

long long denominator(int n, int k, int p) {
    long l = 1;
    for(int j = 2; j <= n-k; j++) {
        l = (l*j)%p;
    }
    return l;
}

これを割るために、 の結果にオイラーの定理を使用できますdenominator。したがって、最初にpow関数をモジュロで実装します。

long long pow(long long a, int k, int p) {
    if(k == 0) {
        return 1;
    }
    long long r = pow((a*a)%p,k>>0x01,p);
    if((k&0x01) == 0x01) {//odd number
        r = (r*a)%p;
    }
    return r;
}

これで、これらを次のようにマージできます。

long long N_choose_K(int n, int k, int p) {
    long long num = numerator(n,k,p);
    long long den = denominator(n,k,p);
    return (num*pow(den,p-2,p))%p;
}

したがって、基本的に行うことは、Z p の分子、Z p の分母の値を決定し、次にオイラーの定理を使用して Znum pの_分母denの逆数を_見つけ、乗算して最後のモジュロを実行できるようにすることです_。手術。その後、返品できます。