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