如何以最佳复杂度计算非常大的n（例如10^14）的tribonacci数。Tribonacci号码被定义为F(n)=F(n-1)+F(n-2)+F(n-3)与F0=1, F1=2, F2=4。
F(n)=F(n-1)+F(n-2)+F(n-3)
F0=1, F1=2, F2=4
或复发定义为 F(n)=aF(n-1)+bF(n-2)+cF(n-3)用F0=1, F1=2, F2=4。
F(n)=aF(n-1)+bF(n-2)+cF(n-3)
我想计算log（n）中的第n个项，就像第n个斐波那契数。
如何使用矩阵幂计算第n个项来生成基本矩阵？
以前，我尝试使用DP来实现它，但是由于我们无法采用如此大的数组，因此无法正常工作。类似地，由于大量10/10数量级的堆栈溢出，递归在这里也不起作用。
Tribonacci数的 _最佳_渐近复杂度将使用矩阵求幂方法，如Fibonacci数的方法。具体来说，这是正确的写操作，它是O（logn）整数运算，而不是O（n）（如动态编程方法）或O（3n）（如朴素的解决方案）。
感兴趣的矩阵是
[1, 1, 1] M = [1, 0, 0] [0, 1, 0]
第 n 个tribonacci数位于 _M n的_左上角。必须通过平方计算矩阵幂，以实现log（n）复杂度。
（对于F(n+3) = a F(n+2) + b F(n+1) + c F(n)，矩阵为：
F(n+3) = a F(n+2) + b F(n+1) + c F(n)
[a, b, c] M = [1, 0, 0] [0, 1, 0]
结果为{F n + 2，F n + 1，F n } = M n {F 2，F 1，F 0}。）
