# 10754 - Fantastic Sequence

 Tweet
Difficulty : medium

Solution Description :

Power of a (Square) matrix problem

If k=2
a(2) = c1*a(1) + c2*a(0) + c3
a(3) = c1*a(2) + c2*a(1) + c3
a(4) = c1*a(3) + c2*a(2) + c3
so, a(n) = c1*a(n-1) + c2*a(n-2)+c3. and  a(n+1) = c1*a(n) + c2*a(n-1)+c3.

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

[Note: matrix A will be always designed in such a way that, every state on which a(n+1) depends, will be present]

So, now, we need to design a 3x3 matrix
M such that, it satisfies M x A = B as stated above.
The first element of
B is a(n+1) which is actually c1*a(n) + c2*a(n-1) + c3. To get this, from matrix A, we need, c1* a(n), c2* a(n-1), and 1 c3. So, the 1st row of M will be [ c1  c2  1].
 |c1 c2 1 | x |  a(n) | = | a(n+1) || ------ |   | a(n-1)|   | ------ || ------ |   |   c3  |   | ------ |

Similarly, 2nd item of
B is a(n) which we can get by simply taking 1 a(n) from A. So, the 2nd row of M is [1 0 0].
 | ----- | x |  a(n)  | = | ------ || 1 0 0 |   | a(n-1) |   |  a(n)  || ----- |   |   c3   | = | ------ |

Similarly, 3th item of B is c3 which we can get by simply taking 1 c3 from A. So, the 3th row of M is [0 0 1].
 | ----- | x |  a(n)  | = | ------ || ----- |   | a(n-1) |   | ------ || 0 0 1 |   |   c3   | = |   c3   |

[I hope you know how a matrix multiplication is done and how the values ar assigned!]

Thus we get the desired 3 x 3 matrix
M:
 |c1 c2 1| x |  a(n)  | = | a(n+1) ||1  0  0|   | a(n-1) |   |  a(n)  ||0  0  1|   |   c3   | = |   c3   |

Similarly for k=3 we get the desired 4 x 4 matrix M:
 |c1 c2 c3 1| x | a(n) | = | a(n+1)||1  0  0  0|   |a(n-1)|   |  a(n) ||0  1  0  0|   |a(n-2)| = | a(n-1)||0  0  0  1|   |  c4  | = |  c4   |

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 k=2
| a(1) |
for n=11,   M^11  X  | a(0) |
|  c3  |

If k=4
| a(3) |
| a(2) |
for n=11,   M^11  X  | a(1) |
| a(0) |
|  c5  |

After that, the ans is upper left corner value of the final matrix.

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