I was solving harejump using matrix exponentiation. To do so we need the base matrix F1 containing the solutions for the first 15 nos. So i used standard dp to solve for the first 15 nos. and then used matrix exponentiation. Here’s my AC solution. However seeing other solutions, i noticed that they have not created the base matrix. eg but their solutions still work. So I wanted to know why isnt it necessary to precompute the answers for the first 15 nos.?
I also struggled a lot with that problem and, in fact, got discouraged when I saw that the base matrix needed to be 15x15, so I ended up reading the editorial for the problem…
As you will see, they formulate it in a different way… Hope it can help you out:
well i have already solved the problem, but with a slow time due to precomputing answers for nos<=15. My problem is that i cant understand why solutions like these http://www.codechef.com/viewsolution/731949 w/o any base matrix work?
But, there is a matrix on that solution… In fact, a Matrix class is created…
but no base matrix , i mean F1, like the one we create for fibonacci
here’s my solution http://www.codechef.com/viewsolution/1714517, i hope u can make out what i m trying to ask through the difference in the 2 solutions.