PROBLEM LINK:
Problem Statement:
You are given a chess board of N$*$M(N<=1e18,M<=8) dimension. Rows are numbered 1 to N (top to bottom) and columns are numbered from 1 to M(left to right). You have one knight (horse) at 1,1. The knight that we have is a bit different from the original one. Our knight if it is at (x,y) (xth row,yth column) can move only to positions (x+1,y+2),(x+1,y-2),(x+2,y+1),(x+2,y-1) only if they are inside the board. Find the number of ways to reach to reach (N,M) from (1,1). As the number of ways can be very large, output the value modulo 1e9+7.
Editorial:
Prerequisites : Matrix Exponentiation
To get the basic idea about matrix exponentiation watch this video by Gaurav Sen AKA gkcs
Once you understand that the answer for current row depends linearly on the answers for the previous two rows(DP) and get the idea of matrix exponentiation, it just boils down to filling the numbers in the matrix appropriately.
Idea of DP
Let x,y be xth row and yth column in the chess board and let DP(x,y) be the number of ways to reach x,y.
x,y can be reached by a knight from previous rows from locations (x-1,y+2) (x-1,y-2) (x-2,y-1) (x-2,y+1)
Therefore dp(x,y)=dp(x-1,y+2)+dp(x-1,y-2)+dp(x-2,y-1)+dp(x-2,y+1).
We can assume each row to be a state and do matrix multiplication like fibonacci series but with different set of coefficient values.
- Exponentiation takes logN operations
- And each multiplication take m^3 operations as the matrices being multiplied are square matrices of 2$*$m dimension
Time Complexity: O(logN$*$m^3)