Why do we need long long for the variable to store the answer(ans variable)… we are doing mod in every step right… then why is long not suffecient?? getting ac with long long, but wa using long… pls explain

Instead of this line

ans=(ans*sum)%mod;

Use this:

ans=( (ans%mod) * (sum%mod) ) %mod ;

Then you might not require to use long long.

I used your WA solution in which you used int and modified your code by replacing above line and got AC

See this submission: http://www.codechef.com/viewsolution/5633094

Where did you guys take care of negative numbers??

ya solution got accepted. What is the logic behind?? both are not the same??

if(ans<0)ans+=mod; see the last few lines

okay as you asked about logic:

consider we have to multiply 4 and 5 and mod value is 3.

so as per your code:

ans=(4*5)%3 i.e ans=20%3 i.e. ans=2

and as per modified line;

ans=( (4%3) * (5%3) )%3 i.e.

ans=( (1) * (2) ) %3 i.e.

ans=2%3 i.e

ans=2

Here you may observe in second part value never increased more than mod value while operation where in first operation value was almost 6 times greater than that of mod value (20 is 6times > than 3) which may create overflow is int is used…!!

Hope you understood…

getting ac for ans=( (ans%mod) * (sum) ) %mod ; and also ac for ans=( (ans) * (sum%mod) ) %mod ; please explain why

i am sorry i didn’t attempted short contest so i have no idea about question, i just explained him that how to take mod in a proper manner, That’s it…

This is because value might not have been overflown!!

As per above example if you try to do this it is absolutely correct but still prone to overflow.

Wait btw what is **sum**?

sum is the sum of each column, it is small only

Then probably you are getting AC coz there was no overflow, because it is as simple, by performing mod operation twice you can highly reduce the value. As you saw in above example that even if you mod a single multiple it will get reduced and it will become less than MOD value, so while multiplication it will easily fit into an integer…

btw taking mod of negative value is not that hard…

You can just take mod of positive part of negative number, and then subtract the resulting value from MOD value…

EX:

-5%3

num=-5, MOD=3 do ans= (-num)%MOD ans=5%3 ans=2 newAns=MOD-ans newAns=3-2 newAns=1

it was mentioned in the constraints that the nos. in the matrix can be -ve, that’s why…