CareerCup

One example: K = 8, then
8th power = 4th power X 4th power
= (2th power X 2th power) X (2th power X 2th power)
Therefore it is a binary
O((logK)*O(n^3))

Ain't it ceil(logK)*O(n^3) ?

can we assume the matrix is a square matrix?

my bad, i just reread the question.

If I remember my linear algebra correctly, it is possible to solve this problem in constant time relative to K, i.e. assuming that the matrix is squared and is invertible (or the determinant != 0)

the basic idea is to make use of pre-calculated results. use dynamic programming. the solution by Anonymous is pretty clear and follows this idea.

A is nxn .. order is (n^3log(m))
Matrix pow(Matrix& A, int m)
{
     if (m == 0) return I; // identity matrix
     if (m==1) return A;
     Matrix b = pow(A, m/2);
     if (m&1) return b*b*A;
     else return b*b;
}