Climbing Stairs (1,2,3) — Solution & Editorial

Back to the Problem

The count is the tribonacci recurrence f(n)=f(n−1)+f(n−2)+f(n−3); use 3×3 matrix exponentiation for huge N.

Complexity: O(log N)