Mussadi lal and stairs

Problem link - https://www.codechef.com/problems/JAM11/
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 :frowning:)

2 Likes

thanks @galencolin :slight_smile: