# Problem Link

**Author:** Eklavya Sharma

**Tester:** Bhuvnesh Jain

**Editorialist:** Eklavya Shama

# Difficulty

Easy-Medium

# Prerequisites

Matrix Exponentiation, Modular Arithmetic

# Problem

You are given a matrix of size m by n.

You have to perform w operations on it.

In each operation, add to each cell the sum of its neighbors.

What will be the final matrix?

# Explanation

We need to do w transformations on the matrix where each transformation is of this form:

A(i, j) → A(i-1, j-1) + A(i-1, j) + A(i-1, j+1) + A(i, j-1) + A(i, j) + A(i, j+1) + A(i+1, j-1) + A(i+1, j) + A(i+1, j+1)

Here addition has to be done modulo p.

In cells where i is 1 or m or where j is 1 or n, the above transformation is invalid.

However, it’s not difficult to find out the transformation in those cases,

so we’re not writing them here.

We can express the above transformation as a sequence of these 2 transformations:

- A(i, j) → A(i-1, j) + A(i, j) + A(i+1, j)
- A(i, j) → A(i, j-1) + A(i, j) + A(i, j+1)

The first transformation is a row transformation can done by pre-multiplying by a matrix of size m by m.

The second transformation is a column transformation can done by post-multiplying by a matrix of size n by n.

Let M_{k} be a matrix of size k where M(i, j) is 1 if absolute difference between i and j is ≤ 1 and 0 otherwise.

The matrix corresponding to the first transformation is M_{m}

and that of the second transformation is M_{n}.

After w transformations, A will become M_{m}^{w} A M_{n}^{w}.

# Time complexity

M_{k}^{w} can be calculated in time O(log(w) * k^{3}) using fast exponentiation.

Therefore total time complexity is O(log(w) * (m^{3} + n^{3})).