c++ - Tribonacciシリーズ

Question

重複の可能性：
漸化式

tribonacciシリーズのn：番目の数字を見つけるにはどうすればよいですか？n最大10^15のアルゴリズムが必要です。

トリボナッチ数は、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)することができます。