Best known algos for calculating nCr % M

To take as example :

“142857 = 27 * 11 * 13 * 37. You can find the result of nCr % m for each m = 27, 11, 13, 37.”

as 27 is not a prime, i hope we would have to resort to last method of finding all fact[n] and inverse-fact[n] for 27.

So we want nCr and we have x! for all x, WHY do we need inverse factorial ? Is it for (n-r)! and r!. To find inverse of (n-r) and r mod M and then multiply all of their factorials and then find % M.

1 Like

How would you calculate nCr mod 27?

You can’t use the inverse modulo here.

and also one can’t do this by nCr=(n-1)Cr+(n-1)C(r-1)
given that the minimum space would be just 2 rows but
each of size r which in this case is 1000000000?

what if do not want modulo, just ncr which does’t fit in even long long?

1 Like

What is the fastest among all the ways to calculate the value of nCr mod M? where M is definitely prime?

I think we should go for Inverse Modulo in this way. This is cheap, I mean O(m).

r[i] = 1

for ( i = 2 ; i < limit ; i ++ )
r[i] = ( mod - (mod/i)*r[mod%i]%mod )%mod;

Here is the link Modulo_inverse

1 Like

@imujjwalanand the last method described. Keep factorials and inverse-factorials modulo p. And you can get nCr % p in O(1) time with pre-computation of O§ and space O§

3 Likes

somebody plz upvote me .i need to ask some questions.

12 Likes

@gamabunta
somebody please upvote me , i have questions to ask
thank you

1 Like

In Java this works quite ok for large N,K
private static BigInteger binomial(final int N, final int K) {

BigInteger ret = BigInteger.ONE;
for (int k = 0; k < K; k++) {
    ret = ret.multiply(BigInteger.valueOf(N-k))
             .divide(BigInteger.valueOf(k+1));
}
return ret;

}

Thank you for such a helpful answer, I have a conceptual doubt that why M needs to be prime for this for Modular
multiplicative inverse to be applied, I mean the condition is only that A and M should be coprime for the existence of inverse so M need not be prime for that.
Am I missing something , Can you please explain reason for M to be prime.

In c++ if you want to calculate nCr for large number of n and r, Here is the simplest logic to do that

void noOfCombination(int n, int k){
int  i=0;
long long res=1;
if (k less_than n/2)
    k = n - k;
for(i = 0; i less_than k; i++){
    res *= (n-i);
    res /= (i+1);
}

  //output result
return;
}

enter code here

1 Like

Once i had to find C(n,r) mod p for very large n,r,p but p was prime. To be exact n<=(2e9) ,r<=(1e9) and p=(2e9)+33

I really googled it but got no answer. So finally came up with an idea and it worked so i thought to share it .please correct me if it might fail in any case:-

The basic idea was to divide n into parts such that we can find any factorial in O(N) time where N can be adjusted according to question’s complexity, i took N to be 1e5 because i had to calculate only 3 factorial per testcase. So i divided it into 20000 (it’s not random) groups each having product of all numbers in that group modulo p. 1st group contains number from 1 to 1e5 and 2nd group contains number from 1 to (2e5) and so on .generally ith group contains number from 1 to i*(1e5) let’s say we are keeping these values in array f[20001].
please keep f[0] equal to 1 and keep the value of groups starting from 1 index.

**Please don’t calculate your f array with in your program because that would be just stupid. I calculated with my IDE and kept it in a file and then copy ,pest **

Note:- if we increase the size of array f we can decrease the time to find factorial.

How to find factorial:-
let’s say we have to find factorial of any random number 1567394027
steps:-

n=1567394027
k=1e5 //(group size)

 a=n/k=15673
 fac=f[a];
start=(a*k)+1  //1567300001;
for(int i=start;i<=n;i++)
 fac=(fac*i)%p;
return fac;

total number of loops=(n%k)

as p is prime we can find multiplicative inverse in log(n) so i think this should work.
Please comment if you find anything wrong.

3 Likes

very nicely written @gamabunta. :slight_smile:

1 Like

@gamabunta: this one is a godd recipe for a tutorial on codechef and topcoder @admins do try to make it a tutorial …

2 Likes

@gamabunta: Firstly Thanks - Well written .

Lucas’s Theorem reduces nCr % M to

(n0Cr0 % M) (n1Cr1 % M) … (nkCrk % M)

Where,

(nknk-1…n0) is the base M representation of n

(rkrk-1…r0) is the base M representation of r

This is only where M is prime … But in that particular problem M is not prime and so can we reduce it into Base form (And still Lucas Theorem Holds) ? And if we use CRT how can we use it ?

Thanks
Anu :slight_smile:

1 Like

@gamabunta: yes probably if you explain chinese remainder that would be even more beneficial…I have read it a lot many times but forget it too easily.

Amazing Detail. Cheers. Just a great feeling seeing someone spend so much time and energy typing this out for others. :slight_smile:

P.S. @anudeep2011:Lucas’ Theorem holds true even for prime powers(like 27=3^3) (Called generalized Lucas’ theorem)

2 Likes

Would be great if there was separate thread about this in latex format. Great answer!!

hey can anyone tell me when to use lucas theorem and when to use fermat theorem.

1 Like

Lucas n>>p, else fermat.

2 Likes