Approach #1: Dynamic Programming [Accepted]
Intuition and Algorithm
Let f[r][c][steps]
be the probability of being on square (r, c)
after steps
steps. Based on how a knight moves, we have the following recursion:
where the sum is taken over the eight pairs .
Instead of using a threedimensional array f
, we will use two twodimensional ones dp
and dp2
, storing the result of the two most recent layers we are working on. dp2
will represent f[][][steps]
, and dp
will represent f[][][steps1]
.
Complexity Analysis

Time Complexity: where are defined as in the problem. We do work on each layer
dp
of elements, and there are layers considered. 
Space Complexity: , the size of
dp
anddp2
.
Approach #2: Matrix Exponentiation [Accepted]
Intuition
The recurrence expressed in Approach #1 expressed states that transitioned to a linear combination of other states. Any time this happens, we can represent the entire transition as a matrix of those linear combinations. Then, the th power of this matrix represents the transition of moves, and thus we can reduce the problem to a problem of matrix exponentiation.
Algorithm
First, there is a lot of symmetry on the board that we can exploit. Naively, there are possible states the knight can be in (assuming it is on the board). Because of symmetry through the horizontal, vertical, and diagonal axes, we can assume that the knight is in the topleft quadrant of the board, and that the column number is equal to or larger than the row number. For any square, the square that is found by reflecting about these axes to satisfy these conditions will be the canonical index of that square.
This will reduce the number of states from to approximately , which makes the following (cubic) matrix exponentiation on this matrix approximately times faster.
Now, if we know that every state becomes some linear combination of states after one move, then let's write a transition matrix of them, where the th row of represents the linear combination of states that the th state goes to. Then, represents a transition of moves, for which we want the sum of the th row, where is the index of the starting square.
Complexity Analysis

Time Complexity: where are defined as in the problem. There are approximately canonical states, which makes our matrix multiplication . To find the th power of this matrix, we make matrix multiplications.

Space Complexity: . The matrix has approximately elements.
Analysis written by: @awice