There is very useful technique for this kind of problem.
A(n) = C1 * A(n-1) - C2 * A(n-2) + C3 * A(n - 3).
Let's introduce matrix B:
C1 -C2 C3
1 0 0
0 1 0.
A(n-1) A(n)
B x A(n-2) = A(n-1)
A(n-3) A(n-2)
and so on..
So to find A(n) you should muultiply matrix B^n by initial vector (A2, A1,
A0).
B^n can be calculated using fast exponention algorithm.
Complexity is O(k^3 * log(n)), where k - size of the matrix B, so k=3.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
