Tribonacci系列

Question

可能重复:重复
关系

如何在tribonacci系列中找到第n个数字？我需要和算法足够快到n10 ^ 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).