HAREJUMP - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

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
2

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?

Thanks in advance!

3

short and sweet explanation.

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