0

The maximum value of n is 100 000 and k can be anywhere from 0 to 100 000. The problem asks to calculate the value modulo 100 003. So I've used a function to calculate the factorial of n,n-k and k and then print fact(n)/(fact(n-k)*fact(k))% 100 003. What am I doing wrong and what would be the solution?

    long long int fact (int z)
{
    long long int r;
    if(z<=1)return 1;
    r=1LL*z*fact(z-1);
    return r;
}
M.Ritz
  • 11
  • 1
  • 8
  • I don't see any `%` sign here, so you are taking the modulo outside of the function? If you do, you will run into integer overflow, as even a `long long` is clearly not large enough to hold a the intermediate number. Also: [Calculate value of n choose k](http://stackoverflow.com/questions/15301885/calculate-value-of-n-choose-k). But most importantly you might want to read up how module distributes wrt. to multiplication. – dhke Sep 01 '15 at 14:31
  • Possible duplicate of [Fast n choose k mod p for large n?](https://stackoverflow.com/questions/10118137/fast-n-choose-k-mod-p-for-large-n) – Bernhard Barker Nov 15 '17 at 18:21

3 Answers3

2

A long long is not big enough to hold fact(n) for interesting n, so you need a smarter algorithm.

applying the mod 100003 as you multiply is an easy way to keep things in range. But modular division is messy and in this case unnecessary.

Think about how to compute fact(n)/( fact(n-k)*fact(k) ) without ever needing to divide any big or modular numbers.

JSF
  • 5,281
  • 1
  • 13
  • 20
2

It will overflow for most z (z = 105 already overflows, for example).

Fortunately the integers modulo 100003 form a field (because 100003 is prime), so the entire calculation (even though it includes a division) can be done modulo 100003, thus preventing any overflow.

Most operations will be the same (except the extra modulo operation), but division becomes multiplication by the modular multiplicative inverse, which you can find using the extended Euclidian algorithm.

harold
  • 61,398
  • 6
  • 86
  • 164
  • Thank you very much. Can you please further explain how should I use the modulo in the factorial function? I think I did understand how to use the modular multiplicative inverse. – M.Ritz Sep 01 '15 at 20:40
  • @M.Ritz you can just apply it all the time, as in `return z * fact(z-1) % 100003` – harold Sep 02 '15 at 05:46
0

ncr=n!/((n-r)!*r!)

(a/b)%p!=((a%p)/(b%p))%p

using fermat little theorem we can compute this

Here fact() means factorial.

nCr % p = (fac[n] modInverse(fac[r]) % p modInverse(fac[n-r]) % p) % p;

Here modInverse() means modular inverse under modulo p.

calculating ,moduloINverse if p is prime as give

    long long modInverse( long long n, int p)
    {
        return expo(n, p - 2, p);
    }

 

long long expo(long long a, long long  b, long long mod) {
long long res = 1; 
while (b > 0) {
if (b & 1)res = (res * a) % mod;
a = (a * a) % mod;
b = b >> 1;}
 return res;}
MONU KUMAR
  • 11
  • 3