CODEWITHSUNDEEP
c++algorithmmathmatrixrecurrence
Alexandru Valeanu
Alexandru Valeanu

Reputation: 21

Find the Nth term in a sequence in C++

I have found a problem in which you are given this type of sequence:

you have

  the first K terms : a1, a2, ... , ak; 
           K coefficients : b1, b2, ... , bk

and a recurrence: 

S(i) = b1*S(i-K) + b2*S(i-K+1) + ... + bk*S(i-1).

I have to find out the Nth term.

I believe this problem can be solved with fast matrix exponentiation but I am having hard time discovering the matrices I have to use. I am trying to write the problem in C++. Can anyone give me some hints about how should I treat this type of problem?

Upvotes: 2

Views: 982

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

As a shameless self-promotion, I coded up a program to solve linear recurrences using matrix multiplication. The comments at the top of the file describe what the matrix you want to form is, as well as how to use the repeated squaring algorithm to efficiently compute the nth term of the recurrence.

Hope this helps!

Upvotes: 1

Related Questions