Can anybody help in finding Matrix Exponentiation in this Recurrence Relation

[kushoz]

Problem Here

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

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

[everule1]

I’ve explained them here.

Matrices, and why they are useful

I read somewhere that there are no good blogs on forming matrix relations, why are they associative, and matrices are not intuitive. So I’ll try outlining how matrices work, and how to make them feel “natural” in a sense.

Associativity

It’s very easy to prove they are associative by just brute forcing the answer, but there is a nice analogy, which makes the proof more natural. How do we do matrix multiplication. Say a[i][j] is the element in the i th row and j th column of a, we multiply a*b=c…

[striker22]

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: https://procoderforu.com/fibonacci-sequence/

[kushoz]

Thanks Very will explained

[kushoz]

yeah i was just wondering how to form matrix