Walks of Astronomical Length — Solution & Editorial

Back to the Problem

The adjacency matrix's K-th power counts walks: entry (1, N) of A^K. Binary exponentiation of the matrix does it in O(N³ log K).

Complexity: O(N³ log K)