Модульная арифметика: деление на факториалы% Prime

Я хочу эффективно рассчитать ((X+Y)!/(X!Y!))% P (P как 10^9+7)

Это обсуждение дает некоторое представление о распределении по модулю. Меня беспокоит то, что не обязательно, чтобы модульное обратное всегда существовало для числа. В основном, я ищу реализацию кода для решения проблемы.

Для умножения это очень просто:

public static int mod_mul(int Z,int X,int Y,int P)
{
// Z=(X+Y) the factorial we need to calculate, P is the prime
long result = 1;
while(Z>1)
  {
    result = (result*Z)%P
    Z--;
  }
return result;
}

Я также понимаю, что многие факторы могут быть отменены в делении (до принятия модуля), но если число делителей увеличивается, то мне трудно эффективно придумать алгоритм деления. (Цикл по списку (множители (X) + множители (Y)...), чтобы увидеть, какой делит текущий множитель числителя).

Изменить: я не хочу использовать решения BigInt.

Существует ли какое-либо решение на основе Java / Python или какой-либо стандартный алгоритм / библиотека для отмены факторов (если обратный вариант не является полным доказательством) или подход к этому типу проблемы.

Источник

3 ответа

Для того, что вам нужно, вот способ сделать это эффективно:

  1. C(n,k) = C(n-1,k) + C(n-1,k-1)

  2. Используйте динамическое программирование для расчета эффективности при подходе снизу вверх

  3. C(n,k)%P = ((C(n-1,k))%P + (C(n-1,k-1))%P)%P

    Следовательно, F(n,k) = (F(n-1,k)+F(n-1,k-1))%P

Еще один более быстрый подход: -

  1. C (n, k) = C (n-1, k-1) * n / k

  2. F (n, k) = ((F (n-1, k-1) * n)% P * inv (k)% P)% P

inv (k)% P означает модульную инверсию k.

Примечание: - Попробуйте оценить C(n,n-k) if (n-k<k) because nC(n-k) = nCk

Источник

((X+Y)!/(X!Y!)) низкоуровневый способ написания биномиального коэффициента ((X+Y)-choose-X). И хотя вы не сказали этого в своем вопросе, комментарий в вашем коде подразумевает, что P прост. Соедините их вместе, и теорема Лукаса применима непосредственно: http://en.wikipedia.org/wiki/Lucas%27_theorem.

Это дает очень простой алгоритм, основанный наP представления X+Y а также X, Будь то BigInts Требуется невозможно угадать, потому что вы не дали никаких ограничений на свои аргументы, кроме того, что они ints. Обратите внимание, что ваш образец mod_mul код может не работать вообще, если, например, P больше квадратного корня из максимума int (так как result * Z может переполниться потом).

Источник

Это биномиальные коэффициенты - C(x+y,x),

Вы можете рассчитать это по-другому C(n,m)=C(n-1,m)+C(n-1,m-1),

Если вы согласны со сложностью времени O(x*y), код будет намного проще.

http://en.wikipedia.org/wiki/Combination

Источник
Другие вопросы по тегам