Как рассчитать nCr% m

Question

При условии, что m is not prime как рассчитать nCr?

1 <= n, r <= 100000

Подобно этому, если мы имеем m простое, что мы можем сделать fact(n) * invmod(fact(r)) * invmod(fact(n-r))

где invmod(a) = power(a, m-2)

Что делать, если m не является простым?

Answer 1

Мы знаем, что

C(n,r) = fact(n)/(fact(r)*fact(n-r)) 

Но учти C (7,5):

C(7,5) = 7x6x5x4x3x2x1/(5x4x3x2x1 * 2x1) 
     = 7x6/2x1 

Итак, представьте, что вместо того, чтобы делать все продукты, мы просто делали это с наборами значений:

C(7,5) = product(set(1..7) - set(1..5))/product(1..2) 

Но на самом деле мы могли бы определить функцию кросс-отмены, которая взяла элементы в одном наборе и отменила значение val ЕЭС от второго набора, где это возможно:

crossCancel(numeratorSet, denominatorSet) -> 
    remainingNumers, remainingDenoms 

Это должно оставить нас с минимальным продуктом, который нуждается вычисления по модулю т, но мы можем пойти дальше. Если разделить каждый из оставшихся элементов в его факторы:

7x6/2 
= 7x3x2/2 

Дальнейшее снижение отменяет 2s

= 7x3 

В действительности, мы знаем, что Ncr предполагает сокращения общего продукта (5x4..1) каждый раз, так что мы можем сразу же сократить его

product(set(r+1..n))/product(set(1..n-r)) 

Кроме того, можно показать, что знаменатель всегда будет отменить в числителе (потому что, если г и п отделены друг от друга, например, 3, то 3 будет в знаменателе и 3-х последовательных чисел будет в числителе, так что надо отменить), поэтому мы знаем, что мы всегда можем сделать

product(set(factorsOf(r+1 .. n)) - set(1..n-r)) 

Учитывая это сейчас ограниченный продукт, он должен быть достаточно простым, чтобы определить, что продукт по модулю m должен быть.