You can use the matrix exponentiation method (linear recurrence method).
You can find detailed explanation and procedure in this or this blog. Run time is O(log n).
I don’t think there is a better way of doing this.
You can use the matrix exponentiation method (linear recurrence method).
You can find detailed explanation and procedure in this or this blog. Run time is O(log n).
I don’t think there is a better way of doing this.