Fibonacci with a 2×2 Matrix

[[1,1],[1,0]]^n relates to Fibonacci numbers—fast doubling alternative.

Try this in Python

def mat_mul(a, b):
    return [
        [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
        [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
    ]

base = [[1, 1], [1, 0]]
print(mat_mul(base, base))

Key takeaways

• Matrix exponentiation uses same fast-power as integers.
• Mod every multiply in contests.
• Fast doubling is even shorter code for Fib only.