current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free.
up vote 1 down vote favorite

I am trying to do http://www.spoj.com/problems/FIBTWIST/ problem by linear recursion. However, since the constraints are large I have to use matrix exponentiation. I have read http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html so according to it equations formed are

ft(n)=ft(n-1)+ft(n-2)+g(n)    ft(0)=0, ft(0)=1
g(n) =g(n-1)+1                g(1)=0

But now I am confused how to form matrices A and B of the form A*M=B. It is given as Type 7 in mentioned blogspot link but I am having difficulty in understanding it.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Define a third sequence, fut, Fibonacci-untwist, as

fut(n)=ft(n)+(n+2).

Then

fut(n)=ft(n)+n+1=ft(n-1)+ft(n-2)+(n-1)+(n+2)=fut(n-2)+fut(n-1)

So fut is just another solution of the Fibonacci recursion, and thus

fut(n)=f(n-1)*fut(0)+f(n)*fut(1)=2*f(n-1)+4*f(n)=2*f(n)+2*f(n+1)=2*f(n+2)

and finally

ft(n)=2*f(n+2)-(n+2)

Test:

    f(n):   0  1  1  2  3  5  8 13 21 34
2*f(n+2):   2  4  6 10 16 26 42 68
     n+2:   2  3  4  5  6  7  8  9
   ft(n):   0  1  2  5 10 19 34 59

and really, the last row is the difference of the second and third row.

share|improve this answer
    
I am not able to understand how did you got this equation fut(n)=f(n-1)*fut(0)+f(n)*fut(1) . And shouldn't be fut(n)=ft(n)+n+1. –  Anchit Jain Apr 2 '14 at 18:41
    
f(n-1) and f(n) form the basis of the solution space of the Fibonacci recursion. And no, the constant is correct this way. –  LutzL Apr 2 '14 at 18:48
    
I am still not getting the part of f(n-1) and f(n-2) . –  Anchit Jain Apr 2 '14 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.