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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.