10754 - Fantastic Sequence

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  |   | ------ |

[Note: ----- means, we are not concerned about this value]

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