12470 - Tribonacci

Difficulty : medium

Solution Description :

Power of a (Square) matrix problem

In this problem
f(4) = f(3) + f(2) + f(1)
f(5) = f(4) + f(3) + f(2)
so, f(n) = f(n-1) + f(n-2) + f(n-3). and  f(n+1) = f(n) + f(n-1) + f(n-2). 

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

Matrix A

Matrix B

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

| f(n-2) |

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

| f(n-1) |


[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 f(n) + f(n-1) + f(n-2). To get this, from matrix A, we need, one f(n), one f(n-1), and one f(n-2) . So, the 1st row of M will be [ 1 1 1 ].

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

| ----- | | f(n-2)| | ------ |


[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 0].

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

| ----- | | f(n-2)| | ------ |

Similarly, 3nd item of B is f(n-1) which we can get by simply taking 1 f(n-1) from A. So, the 3rd row of M is [0 0 1].

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

| 0 1 0 | | f(n-2)| | f(n-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:

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

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


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

Now the question what is the matrix use for 11.
-> 11 = 8 + 2 + 1
So, for m=11 you can use = M^8 * M^2 * M = M^11
For find the final ans you need some extra work.

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

Input n
If n is less than 4 then print (n-1)
else m = n - 3 and find the ans using method which is describe in above.