Walks on a Cube — Solution & Editorial

Back to the Problem

The (1, 1) entry of the adjacency matrix's N-th power counts closed walks of length N from vertex 1. Fast matrix exponentiation.

Complexity: O(V³ log N)