Domino Tilings of 2xN — Solution & Editorial

Back to the Problem

Tilings satisfy f(n)=f(n−1)+f(n−2) with f(1)=1, f(2)=2 — a Fibonacci shift solved by matrix power.

Complexity: O(log N)