IEMCO8F - Editorial

editorial
, , , ,
1

Problem -

Contest

Solution -

In the given problem we are given a recurrence relation and we have to find N th number based on this relation.
F(n)= a∗f(N−1)+b∗f(N−2)+c∗f(N−3)+d∗f(N−4)+e
if(N<10^6) then we have just solved this problem using dynamic programming and would have created a array of size 10^6 and based on this relation stored the value in the given array.
int fib(int N)
{
int arr[N+1];
arr[0]=0; arr[1]=1; arr[2]=2; arr[3]=3;
// These four intial value are given in question
for(int i=4;i<=N;i++)
{
arr[i]=a∗f(N−1)+b∗f(N−2)+c∗f(N−3)+d∗f(N−4)+e;
}
// put modulus such the value not overflow
}
But in our problem N<=10^18 so this process will give tle. So we need to find some other method.
Matrix exponential is one of that method that can be used to solve the given problem in O( log N ) time complexity .

So basically in matrix exponential we multiply matrix to find our result .
so to solve this problem you need to know

  1. How to multiply two matrix .
  2. How to find n th power of a matrix.
    We see this pattern in every matrix exponential problem
    | | | f(n) | | f(n+1) |
    | f(n-1) | | f(n) |
    M x | f(n-2)| = | f(n-1) |
    | … | | … |
    | f(n-k)| |f(n-k+1)|
    so based on our problem we have to create matrix M such that after multiplying it with matrix B we get matrix C.
    For our given problem matrix M is
    | a b c d e | | f(n) | | f(n+1) |
    | 1 0 0 0 0 | | f(n-1)| | f(n) |
    | 0 1 0 0 0 | * | f(n-2)| = | f(n-1) |
    | 0 0 1 0 0 | | f(n-3)| | f(n-2) |
    | 0 0 0 0 1 | | 1 | | 1 |

So for given problem we have create our matrix M . In case you didn’t the solution try to multiply matrix M with matrix B for better understanding.

Now if we multiply matrix M with C we will get a matrix of | f(n+2) | as first element so basically as we again multiply matrix M again and again we will get next element .

Time complexity

O(log N) where N is the N th number of recurrence relation .
You can refer to these links for better understanding

4 Likes