I was practicing DP through CSES when I got to the Two Sets II problem, wherein I got the confusion on the usage of mod to get the correct answer.
I had read earlier that if we wish to take mod of a summation, we have to take mod of individual elements of the series and then take the mod of summation.
But here are my two submitted codes:
- Accepted: not taking the overall mod on summation.
- Wrong Answer: taking the overall mod on summation.
Wrong Answer Code
Accepted Code
Due to this, I got confused about how we should be taking the mod and, in general, how you tackle such situations. (Right now, I'm looking for a discussion like the one from which I got to know of the binary search method of while (r-l > 1), which I now use, so I can only stress more on the concept of the problem.)
Whenever the sum can be bigger than the mod you must take a mod, which is almost always. For example if you add two numbers the max of each of them is MOD-1 so the sum can be 2*MOD-2. In CP, you don't need to decide on where to add mod though just put it after every operation. Some people use auxillary functions or even mod int templates.
PS: If the thing you are taking mod of can be negative you must make it positive because in C++ mod works in a way different than math (see Auxillary for example).
https://github.com/atcoder/ac-library/blob/master/atcoder/modint.hpp
"if you add two numbers the max of each of them is MOD-1 so the sum can be 2*MOD-2"
"Whenever the sum can be bigger than the mod you must take a mod, which is almost always."
Yes, but then that gave me the wrong answer while taking up the mod on the sum and rather got accepted when I removed the mod on the sum. My major confusion is why taking mod on sum caused us harm. It is not getting a negative value anywhere in between so we won't have conflict in there.
CSES submissions are private.
Oh thanks a lot for that, I'm sorry I didn't knew about that and have now put them in spoilers.
another thing — you can't just divide a number under mod to get the correct answer. you should be multiplying by the modular inverse.
You can try writing the first one as