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.? asked 13 Jan '13, 18:55

Hello, 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: Good luck, Bruno answered 13 Jan '13, 19:03
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?
(14 Jan '13, 01:23)
But, there is a matrix on that solution... In fact, a Matrix class is created..
(14 Jan '13, 01:30)
but no base matrix , i mean F1, like the one we create for fibonacci
(14 Jan '13, 01:48)
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.
(14 Jan '13, 01:51)
