Problem link - JAM11 Problem - CodeChef
where is this solution going wrong. i am using matrix exponentiation to calculate the nth number in the recurrence relation in log(N) time
https://www.codechef.com/viewsolution/36179316
Although it can be easily solved using O(n) approach as the contraints permits O(n) solution also. but i would like to know what’s wrong with this solution.
just add a line at line 73 , res[i][j]%=mod;
edit:Sry,my first assumption was wrong (I didn’t read code completely).
The problem is actually that you aren’t modding enough. You have this on line 72: res[i][j] += (A[i][k] * B[k][j]) % mod;. This means the value that’s added to res[i][j] will be less than mod, but res[i][j] itself could be greater than mod. So when res becomes the new matrix and you multiply two values in res together, it could overflow. To fix that, you would also want to mod the values of res at every step.
With that modification, here’s my accepted submission to prove it works: CodeChef: Practical coding for everyone
(also, for my OCD, please fix the spelling of multiply in your function 
)
