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
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
thank you it helped me
welcome