A solution with complexity ~\mathcal O(TN^2)~:

For each second, starting with ~0~, we compute a matrix of ~1~s and ~0~s, where a ~1~ denotes a square reachable by the knight in the respective second. The matrix for second ~0~ has ~0~s in all positions, except for the starting position of the knight. From each matrix, we can compute the matrix for the next second, up to second ~T~. The next matrix is computed by mapping all ~1~s to all squares reachable by any of the ~8~ possible jumps from that square, and then zeroing out all positions blocked during the next second.

The memory complexity of this algorithm is ~\mathcal O(N^2)~, since we need only two matrices (the current and the next one) at any moment. This solution is worth ~40\%~ of points.

A solution with complexity ~\mathcal O(TN)~:

Instead of the matrix of ~1~s and ~0~s, we will use a sequence of numbers, where each number represents a row of the matrix and its binary digits correspond to the ~1~s and ~0~s from the previous solution. For simplicity, we will continue to use the term matrix in the remainder of the description.

The mapping of ~1~s in all ~8~ directions can now be implemented using bit operations, which is more efficient than the previous solution.

The remaining problem is quickly computing the matrix of squares blocked in second ~t~. Notice that if ~t~ is divisible by ~K_{ij}~, then the square ~(i, j)~ is blocked during second ~t~.

If ~K_{ij}~ is greater than ~1\,000~, we can simply generate all moments when the square will be blocked, since there will be less than ~1\,000~ such moments.

If ~K_{ij}~ is less than ~1\,000~, the problem can be solved using prime factorization. Notice that, if ~K_{ij}~ divides ~t~, all prime factors of ~t~ (including the ones with exponent ~0~) must have greater or equal exponents than the corresponding exponents in the factorization of ~K_{ij}~.

Let us denote by ~F(p^q)~ the matrix with a ~1~ in position ~(i, j)~ if ~q~ is greater than or equal to the exponent of the prime number ~p~ in the factorization of ~K_{ij}~.

Now the matrix of squares blocked in second ~t~ can be expressed as:

$$\displaystyle F(p_1^{q_1}) \mathbin{\&} F(p_2^{q_2}) \mathbin{\&} \dots \mathbin{\&} F(p_k^{q_k}) \tag{1}$$

where ~p_1, p_2, \dots, p_k~ are all primes less than ~1\,000~, ~q_1, q_2, \dots, q_k~ are their exponents in the factorization of ~t~, and ~\&~ is the bitwise AND operation.

The direct computation of the above expression ~(1)~ is slow. However, notice that at most ~7~ primes in a factorization will have positive exponents, while all other exponents will be ~0~.

Before the main algorithm, we will precompute, for each interval ~[x, y]~, the following:

$$\displaystyle G(x, y) = F(p_x^0) \mathbin{\&} F(p_{x+1}^0) \mathbin{\&} \dots \mathbin{\&} F(p_y^0)$$

The expression ~(1)~ can now be quickly computed by using ~F(p^q)~ for all primes with a positive exponent, and the precomputed ~G~ for all other primes (with exponents of ~0~, grouped in at most ~8~ intervals), combining all values with a bitwise AND.

Now that we can compute the matrix of squares blocked in second ~t~, we can simply apply it to the current matrix of possible positions using a bitwise AND, thus obtaining the final matrix for second ~t~.