Author: Eklavya Sharma
Tester: Bhuvnesh Jain
Editorialist: Eklavya Shama
Matrix Exponentiation, Modular Arithmetic
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?
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 Mk 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 Mm
and that of the second transformation is Mn.
After w transformations, A will become Mmw A Mnw.
Mkw can be calculated in time O(log(w) * k3) using fast exponentiation.
Therefore total time complexity is O(log(w) * (m3 + n3)).