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
1 Like
ya solution got accepted. What is the logic behind?? both are not the same??
Where did you guys take care of negative numbers??
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…