By Aditya_Sharma, history, 5 weeks ago, [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;
}  Comments (8)
 » Auto comment: topic has been updated by Aditya_Sharma (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   Try to calculate $(10^9 + 8) / 2$ mod $10^9 + 7$. Without modular inverse: $(10^9 + 8) / 2 = 1 / 2 = 0$ (wrong) With modular inverse: $(10^9 + 8) / 2 = 1 / 2 = 1 \cdot (5 \cdot 10^8 + 4) = 5 \cdot 10^8 + 4$ (correct) So you need modular inverse to use division under mod.
•  » » Thank you so much.
•  » » I got what you said....(Very nice explanation with example...) NOW,can you also explain what is happening behind the scenes in the code below ? That is, what tempted us to do the below thing... Or I should just think that it just works like that ......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;}
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   Google Fast Modular Exponentiation/ Fast Exponentiation. This is basically a function to calculate pow(a,b)%m in log time.
•  » » » » thank you so much
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   Let's suppose that you want to calculate $6^{11}$ (I'm omitting mod, you just have to use it after each operation).You want to write $6^{11}$ as the product of some $6^{2^k}$ (so the exponents are powers of 2). You can use the binary representation of $11 = 1011_2$: the resulting product is $6^{2^3} \cdot 6^{2^1} \cdot 6^{2^0} = 6^{2^3+2^1+2^0} = 6^{11}$.Moreover, all these powers can be calculated in $O(log(b))$ by using the property $6^{2^{k+1}} = (6^{2^k})^2$.At the beginning, $result = 1 = 6^0$.For each step i, if there is a $1$ in the position i of the binary representation of $11$, you have to multiply $result$ by $6^{2^i}$; then you calculate $6^{2^{i+1}}$ by squaring $6^{2^i}$.Steps:0) $a = 6^1$, $b = 1011_2$1) $result := 6^0 \cdot a = 6^1$ (because the last digit in $b$ is $1$), $a := a \cdot a = 6^2$, $b := b / 2 = 101_2$. Notice that, when shifting $b$ to the right, you are basically deleting the last digit, so the new last digit of $b$ corresponds to the $(i+1)$-th digit from the right of the original $b$. In fact, b & 1 returns $1$ iff the last digit of $b$ is 1.2) $result := 6^1 \cdot a = 6^3$, $a := a \cdot a = 6^4$, $b := b / 2 = 10_2$.3) $a := a \cdot a = 6^8$, (the result is not updated because the last digit of $b$ is $0$), $b := b / 2 = 1_2$.4) $result := 6^3 \cdot a = 6^{11}$, $a := a \cdot a = 6^{16}$, $b := b / 2 = 0$.The algorithm stops because there are no other digits $1$ in $b$.
•  » » » » Thank you so much. I really appreciate your efforts and your explanations are fantastic.