Ans += MOD; ans %= MOD; Why we are adding the mod?

Learn CP on Unacademy
1

Today i am solving a problem and my datatype is overflowing . When i see editorial there is code something link this

  ll ans=power(n,k,MOD);
   for(auto x:aa){
    ans-=power(x.se,k,MOD);
    ans += MOD;
    ans %= MOD;

   }

In this code Why we are adding the mod ?
n upto 10^5
k upto 100
problem: Problem - C - Codeforces
Solution : Submission #178620231 - Codeforces
Submission #178621584 - Codeforces
Maybe I am wrong.
The use of mod is to decrease the range of answers in order to save in the range of data type.
suppose Anwer 10^7+55 then on mod answer =55.

In this question first, we calculate the power of the number within the range of mod then apply something :
( (power(n,k) in range of mod ) + mod - (power(pi,k) in range of mod) )%mod

here we take the first term power(n,k) out of range by adding mod then subtract power(pi,k) and again tack them in range by applying mod.

2

I am not sure about the actual problem. It seems that ans can be negative.
We do this thing when we take modulo of negative number.

4

problem: Problem - C - Codeforces
Solution : Submission #178620231 - Codeforces
Submission #178621584 - Codeforces
You are right anwer is becoming negative in some testcase
But Why in combinatorics logic answer is becomeing negative…

5

I checked out the problem. Nice one, had great time solving it.
My solution:

In the problem, we want to find n^k - sum(pi^k), where pi - is the size of some subtrees with only red nodes.
But the answer can get negative in this example:
Let’s say:
n^k = 10^9 + 100; and pi^k=10000;
Here n^k%MOD = 93; and pi^k % MOD = 10000;
So we get 93-10000 which is negative.

6

Maybe I am wrong.
The use of mod is to decrease the range of answers in order to save in the range of data type.
suppose Anwer 10^7+55 then on mod answer =55.

In this question first, we calculate the power of the number within the range of mod then apply something :
( (power(n,k) in range of mod ) + mod - (power(pi,k) in range of mod) )%mod

here we take the first term power(n,k) out of range by adding mod then subtract power(pi,k) and again tack them in range by applying mod.

1 Like
7

That’s because you are subtracting something from ans, it can be possible that ans become negative.

As you know before subtraction ans is in between [0,MOD-1]
now let’s suppose whatever you are subtracting is greater than ans in this case ans become negative.

now as you know :- (x)%m == (x+m)%m
it can be proved as :-
let’s take RHS.
(x+m)%m = x%m + m%m
as m%m = 0;
RHS = x%m

Hence if we add mod to ans and take % again ans won’t change in case ans in +ve else it become +ve and gives us right ans for example

ans = 10;
mod = 17;
subtract = 14;

ans - subtract = -4
if you take direct mod it will give wrong answer so you can just add mod to it
(-4+17) % 17 = 13.

8

ok,
Today I study the modulo
there are some properties in modulo
As one, you said to add the mod in case tacking mod of negative number.

After all negative answers come due to the first modulo(n,k) operation in the power calculation .which should be some large number (>sum of all pow(pi,k))
in real.

In the modulo-tacking Problem, we try to take answers between 0 to modulo-1 at every step of the calculation.
If we have some data type that can store the large number then we do not need the modulo concept in this problem.
Are we getting some answer as in this case? I mean
the real answer = will be some modulo times + the answer come in the case we make an answer at each step between mod and 0