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

1 Like

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: https://www.codechef.com/viewsolution/36181953

(also, for my OCD, please fix the spelling of `multiply` in your function )

2 Likes

thanks @galencolin