numbers - 他们是否有任何优化算法来查找 tribonacci 系列的第 n 项（系列可以达到 10^18 项）

我正在做一个微软面试问题，问题是找到 Tribonacci 系列的第 N 项，其中 n 可以非常大（即 10^18）。

我尝试在这个问题上实现 Dp，但由于这个系列非常庞大，无法成功。

基本上尝试了简单的技术，在该技术中，我将术语预先计算到某个术语并返回所需的答案，但由于 N 可以达到 10^18，因此无法成功。

T(n) = T(n-1) + T(n-2) + T(n-3) // T(0)=T(1)=0 , T(2)=1

// 如果 T(n) 是大存储 T(n)= T(n)% 10^9 +7

我知道我没有以优化的方式尝试这个问题，任何帮助将不胜感激。

PS对不起，如果我在格式化问题时犯了任何错误。

标签： numbersdynamic-programmingmathematical-optimizationseries

斐波那契类型的序列可以转换为矩阵的幂次方，进而可以通过使用重复平方来优化。我不确定为什么在面试问题中会问这个问题，因为建立这种联系需要事先了解这种方法（因为我怀疑有人在面试的时间跨度内开发了这样的算法）。

对于斐波那契数列 {0,1,1,2,3,5 ...} ，矩阵为

M = 1 1
    1 0

和 F(n+1) = (M^n)[0][0]

对于 Tribonacci 序列 {0,0,1,1,2,4,7,13,...} ，矩阵为

M = 1 1 1
    1 0 0
    0 1 0

和 T(n+2) = (M^n)[0][0]

对于 Tetranacci 序列 {0,0,0,1,1,2,4,8,15,...}，矩阵为

M = 1 1 1 1
    1 0 0 0
    0 1 0 0
    0 0 1 0

和 T(n+3) = (M^n)[0][0]

通过重复平方求幂的 Wiki 文章，将 n <= 10^18 的循环次数减少到大约 64。