FIBEQN Editorial by Satwant Rana
The problem asks us to calculate \sum_{i = 0}^n{F_i\ k^i}, and time limit suggests we need to do it in O(log\ N) time.
The model solution makes use of the fact that F_i = \frac{\phi^i - \psi^i}{\phi-\psi}, where \phi = \frac{1 + \sqrt5}{2} and \psi = \frac{1 - \sqrt5}{2}. Leveraging this fact we can perform computations in \mathbb Z[\sqrt5].
So the problem asks us to calculate \sum_{i = 0}^n{\frac{\phi^i - \psi^i}{\phi-\psi}\ k^i} = \frac{\frac{(\phi\ k)^i - 1}{\phi - 1} - \frac{(\psi\ k)^i - 1}{\psi - 1}}{\phi - \psi}. This can be done in O(log N) time with logarithmic exponentiation in \mathbb Z[\sqrt5].