CODEWITHSUNDEEP
mathcombinationscombinatorics
kunal dave
kunal dave

Reputation: 21

how to calculte nCr % m

Provided that m is not prime how to calculate nCr ?

1 <= n, r <= 100000

Like if we have m prime, we can do is fact(n) * invmod(fact(r)) * invmod(fact(n-r))

where invmod(a) = power(a, m-2)

What to do if m is not prime ?

Upvotes: 2

Views: 124

Answers (1)

Phil H
Phil H

Reputation: 20151

We know that 

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

But consider C(7,5):

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

So imagine that instead of doing all the products, we just did this with sets of values:

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

But in fact we could define a cross-cancellation function which took the items in one set and cancelled values from a second set where possible:

crossCancel(numeratorSet, denominatorSet) -> 
   remainingNumers, remainingDenoms

This should leave us with the minimal product which needs calculating modulo m, but we can go further. If we split each of the remaining items into its factors:

  7x6 / 2
= 7x3x2 / 2

A further reduction cancels the 2s

= 7x3

In reality, we know that nCr involves cancelling the common product (5x4..1) every time, so we can immediately shorten it to 

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

Also it can be shown that the denominator will always cancel into the numerator (because if r and n are separated by e.g. 3 then 3 will be in the denominator and 3 consecutive numbers will be in the numerator, so one must cancel), so we know that we can always do

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

Given this now-limited product, it should be fairly straightforward to determine what the product modulo m should be.

Upvotes: 1

Related Questions