How to calculate tribonacci number for very large n ( say 10^14 ) in best complexity. Tribonacci numbers are defined as F(n)=F(n-1)+F(n-2)+F(n-3) with F0=1, F1=2, F2=4.

Or recurrence defined as F(n)=aF(n-1)+bF(n-2)+cF(n-3) with F0=1, F1=2, F2=4.

I want to Calculate nth term in log(n) just like nth Fibonacci number.

How can I generate the Base Matrix for using matrix exponentiation to calulate the nth term?

Previously I was trying to implement it using DP but as we cannot take array of such large size its not working fine. Similarly Recursion didn't work here due to stack overflow for very large numbers of order of 10^14.

algorithm dynamic recursion
Edit
Report