递归关系[关闭]

如何以最佳复杂度计算非常大的 n （例如 10^14 ）的 tribonacci 数。 Tribonacci 数定义为F(n)=F(n-1)+F(n-2)+F(n-3) with F0=1, F1=2, F2=4.

或复发定义为F(n)=aF(n-1)+bF(n-2)+cF(n-3) with F0=1, F1=2, F2=4.

我想计算 log(n) 中的第 n 项，就像第 n 个斐波那契数一样。

如何生成基础矩阵以使用矩阵求幂来计算第 n 个 学期？

以前我尝试使用 DP 来实现它，但由于我们无法采用如此大尺寸的数组，因此它无法正常工作。类似地，由于 10^14 的大量数量的堆栈溢出，递归在这里不起作用。

The best asymptotic complexity for tribonacci numbers will be using a matrix exponentiation method like the one for Fibonacci numbers. Specifically, written correctly, this is O(log n) integer operations, rather than O(n) (like the dynamic programming method) or O(3ⁿ) (like the naive solution).

兴趣矩阵是

    [1, 1, 1]
M = [1, 0, 0]
    [0, 1, 0]

and the nth tribonacci number is in the upper left corner of Mⁿ. The matrix exponentiation must be computed by squaring to achieve log(n) complexity.

(for F(n+3) = a F(n+2) + b F(n+1) + c F(n)，矩阵为：

    [a, b, c]
M = [1, 0, 0]
    [0, 1, 0]

and the result is {F_n+2,F_n+1,F_n} = Mⁿ {F₂,F₁,F₀}, also see here.)