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