Matrix power

Binary exponentiation on matrices.

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 diag.
• Mod each mul.
• Pure python contests.