Matrix Exponentiation (Fast Power)

Square repeatedly like pow for integers—O(d^3 log n) for dense d×d.

Try this in Python

def mat_pow(M, n):
    size = len(M)
    res = [[1 if i == j else 0 for j in range(size)] for i in range(size)]
    base = [row[:] for row in M]
    while n:
        if n & 1:
            res = mat_mul(res, base)
        base = mat_mul(base, base)
        n //= 2
    return res


def mat_mul(a, b):
    return [[sum(a[i][k] * b[k][j] for k in range(len(b))) for j in range(len(b[0]))] for i in range(len(a))]

print(mat_pow([[1, 1], [1, 0]], 5))

Key takeaways

• Identity matrix is ones on diagonal.
• Apply modulo on each multiply if required.
• Use numpy only if allowed—contests often pure python.