Perrin Numbers Modulo — Solution & Editorial

Back to the Problem

Build the 3×3 companion matrix of the order-3 recurrence and exponentiate it in O(log N).

Complexity: O(log N)