10870 - Recurrences

Difficulty : medium

Solution Description :

Power of a (Square) matrix problem

If d=2
f(3) = a1*f(2) + a2*f(1)
f(4) = a1*f(3) + a2*f(2)
f(5) = a1*f(4) + a2*f(3)
so, f(n) = a1*f(n-1) + a2*f(n-2). and  f(n+1) = a1*f(n) + a2*f(n-1). 

Let, we know, f(n) and f(n-1); we want to get f(n+1)
From the above situation, matrix A and B can be formed as shown below:

Matrix A

Matrix

|  f(n)  |
| f(n-1) |

| f(n+1) | |  f(n)  |


[Note: matrix A will be always designed in such a way that, every state on which f(n+1) depends, will be present]
So, now, we need to design a 2x2 matrix M such that, it satisfies M x A = B as stated above.
The first element of B is f(n+1) which is actually a1*f(n) + a2*f(n-1). To get this, from matrix A, we need, a1* f(n), and a2* f(n-1). So, the 1st row of M will be [ a1 a2 ].

|a1 a2 | x | f(n) | = | f(n+1) |
| ---- |   | f(n-1)|   | ------ |


[Note: ----- means, we are not concerned about this value]
Similarly, 2nd item of B is f(n) which we can get by simply taking 1 f(n) from A. So, the 2nd row of M is [1 0].

| --- | x |  f(n)  | = | ------ |
| 1 0 |   | f(n-1) |   |  f(n)  |

[I hope you know how a matrix multiplication is done and how the values ar assigned!]
Thus we get the desired 2 x 2 matrix M:

|a1 a2| x |  f(n)  | = | f(n+1) |
|1 0 |   | f(n-1) |   |  f(n)  |


Similarly for d=3 we get the desired 3 x 3 matrix M:

|a1 a2 a3| x | f(n) | = | f(n+1)|
|1 0 0 |   |f(n-1)| | f(n) |

|0 1 0 | |f(n-2)| = | f(n-1)|


and so on.
For n=1 you can use = M
For n=2 you can use = M * M = M^2
For n=4 you can use = M^2 * M^2 = M^4
For n=8 you can use = M^4 * M^4 = M^8
ans so on.

Now the question what is the value use for 11.
-> 11 = 8 + 2 + 1
So, for n=11 you can use = M^8 * M^2 * M = M^11

For find the final ans you need some extra work.
If d=2

for n=11, M^11 X | f(2) |
| f(1) |

If d=5
| f(5) |
| f(4) |
for n=11, M^11 X | f(3) |
| f(2) |
| f(1) |
After that, the ans is upper left corner value of the final matrix.

If n<=d then do not need to calculate anything, because f(1), f(2), f(3)..........f(d) given in the input.
Otherwise,
If d = 1, you need to calculate f(n) = find the final matrix upper left corner value for n
If d = 2, you need to calculate f(n) = find the final matrix upper left corner value for n - 1
If d = 3, you need to calculate f(n) = find the final matrix upper left corner value for n - 2
If d = 4, you need to calculate f(n) = find the final matrix upper left corner value for n - 3