Hello all,
I want to calculate combination of two numbers n and r i.e nCr. I know that how to store factorial of numbers greater than 20 in array but I don’t know how to use that array in further calculations.Please help.
@rjohari you are wrong.
This will be very clumpsy task to do that way ,
usually the problem involved calculating nCr in competitive coding will mention the line that
"nCr will fit in long long int " or you have to find ( nCr mod m .)
but if you do it by calculating factorial it will definitely exceed the limits of long long int .
here is the correct approach :-
link text
also i am pasting the code for calculating nCr mod m :-
long modPow(long a, long x, long p) {
//calculates a^x mod p in logarithmic time.
long res = 1;
while(x > 0) {
if( x % 2 != 0) {
res = (res * a) % p;
}
a = (a * a) % p;
x /= 2;
}
return res;
}
long modInverse(long a, long p) {
//calculates the modular multiplicative of a mod m.
//(assuming p is prime).
return modPow(a, p-2, p);
}
long modBinomial(long n, long k, long p) {
// calculates C(n,k) mod p (assuming p is prime).
long numerator = 1; // n * (n-1) * ... * (n-k+1)
for (int i=0; i<k; i++) {
numerator = (numerator * (n-i) ) % p;
}
long denominator = 1; // k!
for (int i=1; i<=k; i++) {
denominator = (denominator * i) % p;
}
// numerator / denominator mod p.
return ( numerator* modInverse(denominator,p) ) % p;
}
1 Like
thank you it helped me 
welcome
There is easier way how to do it, quite easy to implement with big numbers also.
You know Pascal’s triangle, right?
We know that:
So you do not need multiplication/deletion, just addition 
2 Likes