[problem:1420 D]↵
I dont know how to calculate N(c,r) by LOGIC applied in given below Mod_Inverse FUNCTION.↵
Without this logic, this problem can't be solved.↵
In the below code all factorials were precalculated till 3e6. ↵
Tell me what problem was there in directly doing n! / ( r! * (n-r)! )....instead of using Mod_Inverse FUNCTION ...↵
↵
((below code is not my code . I have got it from submissions.))↵
↵
below is a code segment only to calculate N(c,r)...↵
↵
(((( Fact[i] means (factorial i) or i! ))))↵
↵
~~~~~↵
ll NCR (ll n, ll r, ll p)↵
{↵
if (r == 0)↵
{↵
return 1;↵
}↵
return (( Fact[n] * Mod_Inverse(Fact[n - r], p) ) % p * Mod_Inverse(Fact[r], p) ) % p ;↵
}↵
↵
ll Mod_Inverse(ll a, ll m)↵
{↵
// m is A prime NUMBER.↵
return Fast_Mod(a, m - 2, m);↵
}↵
↵
ll Fast_Mod(ll a, ll b, ll m) ↵
{↵
ll Result = 1;↵
↵
while (b > 0) ↵
{↵
if (b & 1)↵
Result = (Result * a) % m;↵
↵
a = (a * a) % m;↵
b = b >> 1;↵
↵
}↵
↵
return Result;↵
}↵
↵
~~~~~↵
↵
↵
I dont know how to calculate N(c,r) by LOGIC applied in given below Mod_Inverse FUNCTION.↵
Without this logic, this problem can't be solved.↵
In the below code all factorials were precalculated till 3e6. ↵
Tell me what problem was there in directly doing n! / ( r! * (n-r)! )....instead of using Mod_Inverse FUNCTION ...↵
↵
((below code is not my code . I have got it from submissions.))↵
↵
below is a code segment only to calculate N(c,r)...↵
↵
(((( Fact[i] means (factorial i) or i! ))))↵
↵
~~~~~↵
ll NCR (ll n, ll r, ll p)↵
{↵
if (r == 0)↵
{↵
return 1;↵
}↵
return (( Fact[n] * Mod_Inverse(Fact[n - r], p) ) % p * Mod_Inverse(Fact[r], p) ) % p ;↵
}↵
↵
ll Mod_Inverse(ll a, ll m)↵
{↵
// m is A prime NUMBER.↵
return Fast_Mod(a, m - 2, m);↵
}↵
↵
ll Fast_Mod(ll a, ll b, ll m) ↵
{↵
ll Result = 1;↵
↵
while (b > 0) ↵
{↵
if (b & 1)↵
Result = (Result * a) % m;↵
↵
a = (a * a) % m;↵
b = b >> 1;↵
↵
}↵
↵
return Result;↵
}↵
↵
~~~~~↵
↵
↵
