Log(n) 中的 Tetranacci 数

我偶然发现一个问题，需要我计算第n个四联数 https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Tetranacci_numbers时间复杂度为 O(log n)。

我已经看到了几种解决方案斐波那契数列 http://algosolver.blogspot.com/2011/09/fibonacci-log-n.html

我一直想遵循类似的过程（矩阵乘法/快速加倍）来实现这一点，但我不确定如何准确地做到这一点（以类似的方式采用 4 x 4 矩阵和 1 x 4 似乎不起作用）。使用动态编程/通用循环/任何其他基本思想，我无法实现亚线性运行时。任何帮助表示赞赏！

矩阵乘法当然有效。下面介绍如何推导矩阵。

我们想要的是找到构成方程的条目

[a b c d] [T(n-1)]   [T(n)  ]
[e f g h] [T(n-2)]   [T(n-1)]
[i j k l] [T(n-3)] = [T(n-2)]
[m n o p] [T(n-4)]   [T(n-3)]

对所有人来说都是如此n。扩张。

a T(n-1) + b T(n-2) + c T(n-3) + d T(n-4) = T(n)
e T(n-1) + f T(n-2) + g T(n-3) + h T(n-4) = T(n-1)
i T(n-1) + j T(n-2) + k T(n-3) + l T(n-4) = T(n-2)
m T(n-1) + n T(n-2) + o T(n-3) + p T(n-4) = T(n-3)

这里明显的设置是a = b = c = d = 1（使用递归）和e = j = o = 1 and f = g = h = i = k = l = m = n = p = 0（基本代数）。

初始向量是

[T(3)]   [1]
[T(2)]   [0]
[T(1)] = [0]
[T(0)]   [0]

根据定义。