Как найти Choose (m, n)% P для больших входов?
P = (10^9 + 7)
Choose(m, n) = m! / (n! * (m - n)!)
Я хочу рассчитать стоимость Choose(m, n) mod P для большого m а также n,
Как я могу сделать это в C ++?
Решение
Это то, что я использую, поскольку у него довольно хороший диапазон без слишком большого промежуточного переполнения. Однако 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;
}
РЕДАКТИРОВАТЬ: Предполагается, что вам нужны интегральные результаты. Вы можете перейти к результатам с плавающей запятой и получить больший диапазон, если вам это нужно, и можете потерять точность.
Другие решения
Вы можете использовать тот факт, что умножение закрыто под Zп означающий, что: a b mod p = (a mod p) (b mod p) mod p. Используя эту теорему, можно рассчитать б мод р эффективно (например, это Реализация Python.
Далее мы можем использовать Теорема Эйлера говоря: -1 мод р = а(Р-2) мод р.
Теперь, когда мы знаем эти факты, мы можем найти эффективное решение: сначала мы умножим все элементы в числителе, таким образом, это диапазон от к + 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;
}
Теперь нам все еще нужно разделить его на (П-к)!. Мы можем сделать это, сначала рассчитав (П-к)! мод р как мы уже делали в предыдущем фрагменте кода:
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 в Zп, значение знаменателя den в Zп, а затем вы используете теорему Эйлера, чтобы найти обратный знаменатель в Zп, так что вы можете умножить и выполнить последнюю операцию по модулю. Тогда вы можете вернуть его.