The N-th Term of a Recurrence — Solution & Editorial

Back to the Problem

Build the K×K companion matrix of the recurrence and raise it to the appropriate power; multiply by the initial state vector. For N < K just print the given value.

Complexity: O(K³ log N)

Watch out: Index the state vector consistently (newest-first vs oldest-first) — the single most common bug.