Aditya_Sharma's blog

(1420 DIV 2) problem D Rescue Nibel!( Help Needed...) Important Concept Of Combinatorics :::
By Aditya_Sharma, history, 4 years ago, In English

[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;
}
  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you so much.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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;

    }

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +10 Vote: I do not like it

      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$$$.

      → Reply