Here is the code to calculate nCr % P by using Fermat's little theorem
long long power(long long x, long long y, long long p)
{
long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res*x) % p;
// y must be even now
y = y>>1; // y = y/2
x = (x*x) % p;
}
return res;
}
// Returns n^(-1) mod p
long long modInverse(long long n, long long p)
{
return power(n, p-2, p);
}
// Returns nCr % p using Fermat's little
// theorem.
long long nCrModPFermat(long long n, long long r, long long p)
{
// Base case
if (r==0)
return 1;
// Fill factorial array so that we
// can find all factorial of r, n
// and n-r
long long fac[n+1];
fac[0] = 1;
for (long long i=1 ; i<=n; i++)
fac[i] = fac[i-1]*i%p;
return (fac[n]* modInverse(fac[r], p) % p *
modInverse(fac[n-r], p) % p) % p;
}
To optimise the code, I precalculated the fac[]
array and passed it as an argument in the nCrModPFermat()
function:
long long nCrModPFermat(long long n, long long r, long long p,long long fac[])
{
//same code as above
}
int main()
{
long long fac[2001];
fac[0] = 1;
for (long long i=1 ; i<=2000; i++) //calculating factorials upto 2000
fac[i] = fac[i-1]*i%M;
for(i=0;i<2000;i++)
nCrModPFermat(2000,i,M,fac);
}
My outputs where not as expected. Strangely, when I declared the fac[]
array globally and calculated the factorials upto 2000 by calling a function:
long long fac[2001];
void funci()
{
fac[0] = 1;
for (long long i=1 ; i<=2000; i++) //calculating factorials upto 2000
fac[i] = fac[i-1]*i%M;
}
long long nCrModPFermat(long long n, long long r, long long p)
{
//same code as above
}
int main()
{
funci();
for(i=0;i<2000;i++)
nCrModPFermat(5000,i,M);
}
I got the expected outputs. I just want to know why passing the array caused an error in the code