Can anybody help in finding Matrix Exponentiation in this Recurrence Relation

Problem Here

Actually recurrence relation is dp[n][0]= dp[n-1][0]+dp[n-1][1]

Here 0 denotes doesnt go while 1 denotes had gone to workout and n denotes day
answer is ans[n]= dp[n][0]+dp[n][1];

now how to use matrix exponentiation in this

1 Like

I’ve explained them here.

1 Like

You are thinking more than needed.

If you check the answers for different N, you will get a sequence as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \cdots for 0 <= N <= 10^{18}.

Well, now you familiar with this sequence I think. Ring a Bell, it’s a Fibonacci Sequence.
There are tons of articles out there to solve this problem which boils down to calculate the N^{th} term of the Fibonacci Sequence.

Recently @anon79763389 has posted a nice article related to different methods of calculating the Nth term of the Fibonacci Sequence.
You can refer to the article here:


Thanks :slight_smile: Very will explained

yeah i was just wondering how to form matrix :slight_smile: