c++ - 特里波纳奇系列

Question

可能重复：重复
关系

如何找到 tribonacci 系列中的第 n 个数字？我需要和算法足够快，n最多可达 10^15。

Tribonacci 数定义为a(n) = a(n-1) + a(n-2) + a(n-3)其中 a(0)=a(1)=0, a(2)=1。

Answer 1

对于任何具有线性递归的序列，矩阵求幂算法都有效。

如果例如序列有重复

a[k] = x*a[k-1] + y*a[k-2] + z*a[k-3]

对于k >= 3和初始值，您可以通过相乘a[0], a[1], a[2]获得三元组(a[n+2], a[n+1], a[n])

|x y z|^n  |a[2]|
|1 0 0|  * |a[1]|
|0 1 0|    |a[0]|

通过逐步重复平方，可以使用幂运算将矩阵提升到 n^次方O(log n)。