[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;
}
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;}
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 & 1returns $$$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$$$.