## 10754 - Fantastic Sequence
Difficulty : mediumSolution Description : Power of a (Square) matrix problem If k=2a(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:
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].
[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].
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].
[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:
Similarly for k=3 we get the desired 4 x 4 matrix M:
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 for n=11, M^11 X | a(0) | If k=4 for n=11, M^11 X | a(1) | 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 |
|||||||||||||||||||