Fast Matrix Power

Problem

Raise a square integer matrix to a non-negative integer power p using binary exponentiation.

Square the matrix and halve the exponent, multiplying into the result whenever the current bit is set, exactly like fast integer power. The zeroth power is the identity matrix.

Hint

Matrix multiplication is not commutative, so always keep the result on the left.

Test cases

case 1

in: [[[1,2],[3,4]],0]

expected: [[1,0],[0,1]]

case 2

in: [[[1,2],[3,4]],1]

expected: [[1,2],[3,4]]

case 3

in: [[[1,2],[3,4]],2]

expected: [[7,10],[15,22]]

case 4

in: [[[1,0],[0,1]],5]

expected: [[1,0],[0,1]]

case 5

in: [[[2,0],[0,3]],3]

expected: [[8,0],[0,27]]

Starter codePython

def matrix_power(mat, p):
    # Your code here
    pass

5 test cases · run your code against them in the editor