Best known algos for calculating nCr % M

general
, , ,
21

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

22

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.

1 Like