dhanunjaygurram12340's blog

HELP !!!!, I am scared of MOD
By dhanunjaygurram12340, history, 14 months ago, In English

This might super dumb to ask ,but I really need some clear cut answer to this nightmare of mine

Due to this one operation I lost confidence even in questions that I am capable of solving and many Wrong Submissions during the contests where I am having trouble to use this mod (sounds stupid)

Just a simple question....

WHEN & WHERE(i.e in which part of the code) DO I NEED TO USE (% MOD)?

Are there any golden rules on where to use %mod

Also what is the guarantee (or any proof kinda thing) that using %mod at a particular place do not change my final answer??

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
14 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

you can use it always with * and +. (a — b) % mod => (a%mod — b%mod + mod)%mod

→ Reply
  • »
    »
    14 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    be careful with -, since it is not just (a — b) % mod. Because a — b might be less than zero

    → Reply
    • »
      »
      »
      14 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      So any proof that using %mod at * , + == final_answer_without_mod%mod

      Or is it just '%' obeys distributive property with +,* ?

      → Reply
      • »
        »
        »
        »
        14 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        If x >= mod, you must use x%mod, but if x < mod, x%mod == x and nothing would be changed, so you always can use %. And I suggest using % always, not only in the end, as it can prevent owelflow

        → Reply
»
14 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

It's ok bro. I'm scared of it too

→ Reply
»
14 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Use a modulo integer class

→ Reply
»
14 months ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

Use modint as suggested by Mindeveloped, or write functions that apply mod for you and use them everywhere for your calculation. This can be better if you're going to offline competitions where you don't have a modint template at hand.

Spoiler

Example:

dp[i] = add(dp[i], mul(dp[i-1], dp[i-2]));
→ Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Using something like

This

might help, instead of using +, -, * and / to perform the operations safely. (/ is mostly just useless in case of modular operations)

(I know the above code applies Mod too many times and might increase overhead but I just like to keep the functions safe for big or negative inputs unless the time limit is too strict)

Additionally, avoid using int for variables that store modular values, as multiplication (or addition or subtraction) with big numbers can cause overflow.

As for when and where to apply %, you want to apply it after any operation whose result can be >= mod. If you use the * operator, make sure you don't do more than one multiplication (or addition or subtraction) without modding the previous result. For example,

Spoiler

Also, in case of negative numbers (like result of a subtraction), make sure you you add mod if res % mod returns a negative number.

However if you just use the functions given above, you don't have to pay too much attention to these details.

There might be other ways like using a modular integer class, but this is just what I'm comfortable with. Hope it helps!

→ Reply
»
14 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

I think the title is a bit rude

→ Reply