# 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?

short and sweet explanation.

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

Can anyone help me in this code that why am I getting a runtime error? This code is for problem HAREJUMP.

####################################CODE####################
def li(): return list(map(int,input().split()));
def si(): return input().split()
def ii(): return int(input())
def ip(): return input()

def sol(i,a,dp,inf):
if(dp[i]==0):
for j in a:
t=i-j;
if(t>=0):
dp[i]+=sol(t,a,dp,inf)%inf;
return dp[i]%inf;

for _ in range(int(input())):
n=ii(); a=li(); l=a.pop(0);
dp=[0]*(n+1); dp[0]=1; inf=1000000007;
print(sol(n,a,dp,inf)%inf)