 # HAREJUMP - Editorial

EASY

### EXPLANATION

The question requires some Mathematics and the whole system can be seen as State Transitions. The number of ways to reach a state(X) is equal to number of ways of reaching the states which can help the rabbit reach state(X).

Hence F(x) = ∑ F(x- jump lengths)

The above recursive equation if used will result in a TLE as X can be up to 10^18. So a faster approach was required.

Matrix Exponentiation by squaring can help solve this problem. This is a very standard problem and many elite coders could solve this problem with many optimizations. For newbies who did get the recursion but could not solve the problem within Time Limit, I suggest to read about how Matrix Exponentiation can be used to solve Fibonacci problem. Refer to this link to know more

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.

1 Like

The article here is very tough to understand for a newbie like me it would be helpful if someone can explain or give a link to understand the Matrix Exponentation?

Could understand it easily with the help of tester’s solution. 