[Contest][1]

[Practice][2]

**Author:** [Shivam Garg][3]

**Tester:** [Shiv Dhingra][4]

### DIFFICULTY

MEDIUM HARD

### PREREQUISITES

Matrix Exponentiation

### PROBLEM

Given a matrix, and several queries denoting the start point, **tell the number of ways to stay inside the matrix only with the given number of steps.**

### EXPLANATION

This question requires knowledge of Matrix Exponentiation. So, I would advise you to go through this [tutorial][5], and solve questions at the end in case you don’t have a basic idea about this topic.

Now, the matrix can be considered as a graph. In this graph, a cell (A,B) is connected to some other cell

(C,D) only if **1 ≤ max( | A - C | , | B - D | ) ≤ 2.**

So, you can simply make another matrix X of this graph. The dimensions of this matrix will be (N^2,N^2).

The value X(i,j) will denote the number of ways to reach i^{th} point in the input matrix to j^{th} point.

If we simply apply matrix exponentiation on this matrix for the Y steps, this should get the task done.

But, let’s examine the complexity first.

Matrix Exponentiation takes O((N^{2})^{3}Log(Y)) steps. In other words, this turns out to be O(N^{6}Log(Y)) iterations.

As N in our case is 20, and Y is 10^{14}, it turns out to be 47*6.4*10^{7} = 3*10^{9} , which will time out.

On careful observation, we will be able to notice that there is **symmetry in the matrix**.

Let’s consider a matrix for N=4, AND Y=1.

The number of ways corresponding to each point will be -

8 11 11 8

11 15 15 11

11 15 15 11

8 11 11 8

The really useful points are just (1/8 ^{th}*N^{2}) instead of N^{2}.

Let D = (N^{2})/8. Then, the complexity will be O(D^{3}Log(Y)).

Each of the Z queries can be then answered in O(1)

### SOLUTION

Setter’s solution -

```
[6]
[1]: https://www.codechef.com/CODR2018/problems/KRYP3/
[2]: https://www.codechef.com/problems/KRYP3/
[3]: http://codechef.com/users/shivamg_isc
[4]: http://codechef.com/users/lucifer2709
[5]: https://www.hackerearth.com/practice/notes/matrix-exponentiation-1/
[6]: https://www.codechef.com/viewsolution/17468290
```