Как найти Choose(m, n)% P для больших входных данных?

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

Я хочу рассчитать значение Choose(m, n) mod P для больших m и n. Как я могу сделать это на С++?


c++ binomial-coefficients combinatorics
person SWARUPANANDA DHUA    schedule 01.11.2015    source источник
comment
Найдите Гамма-функцию.   -  person 1201ProgramAlarm    schedule 01.11.2015
comment
вы просматривали эту ссылку?   -  person HDJEMAI    schedule 01.11.2015

Ответы (2)


arrow_upward
1
arrow_downward

Это то, что я использую, так как он имеет довольно хороший диапазон без слишком большого промежуточного переполнения. Однако C(n,k) быстро становится большим, в конце концов, это O(n^k).

size_t N_choose_K(size_t n, size_t k)
{
    size_t numer = 1;
    size_t denom = 1;
    if (k > n - k) {
        k = n - k;
    }
    while (k > 0) {
        numer *= n;
        denom *= k;
        --n; --k;
    }
    return numer / denom;
}

РЕДАКТИРОВАТЬ: предполагается, что вам нужны интегральные результаты. Вы можете перейти к результатам с плавающей запятой и получить больший диапазон, если вам это нужно, и вы можете потерять точность.

person Sam Stump    schedule 05.01.2016
comment
Потому что, если вы посмотрите, p равно 10^9, что в основном является самым большим 32-битным числом. Вероятно, это что-то из Project Euler, где числа в любом случае будут гигантскими. - person Willem Van Onsem; 06.01.2016
comment
Ах я вижу. Тем не менее, он подходит для 64-битной системы с запасом места. Вы можете использовать рекурсивную формулу C(n,k) = C(n-1,k-1) + C(n-1,k) и сократить все промежуточные результаты (mod P). Это не будет быстро, но должно вычисляться правильно. - person Sam Stump; 06.01.2016
comment
Ну, однажды я реализовал более или менее эквивалентный подход на Java, и мой опыт показывает, что он начинает давать сбой, когда n больше, чем 150 (или что-то в этом порядке). Имейте в виду, что факториал растет очень быстро. Вам нужно чередовать вычисления по модулю. - person Willem Van Onsem; 06.01.2016

arrow_upward
0
arrow_downward

Вы можете использовать тот факт, что умножение замкнуто под Zp, что означает, что: ab mod p = (a mod p) (b mod p) mod p. Используя эту теорему, можно эффективно вычислить ab 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;
}

Теперь нам еще нужно разделить его на (n-k)!. Мы можем сделать это, сначала вычислив (n-k)! 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;
}

По сути, вы определяете числитель num в Zp, значение знаменателя den в Zp, а затем вы используете теорему Эйлера, чтобы найти обратный знаменатель в Zp, чтобы вы могли умножить и выполнить последнюю операцию по модулю. Потом можно вернуть.

person Willem Van Onsem    schedule 05.01.2016