如何以O(log n)时间求解递推式F(n)=F(n-3)+F(n-2)？

已知递推关系为 ( F(n) = F(n-2) + F(n-3) )，初始条件 ( F(0)=0 )、( F(1)=1 )、( F(2)=2 )。和你提供的斐波那契数列（二阶递推，用2×2矩阵）不同，这个递推式需要用3×3变换矩阵，因为我们需要保留最近3项的状态来完成递推转移，对应的变换矩阵如下：

[ 0  1  1 ]
[ 1  0  0 ]
[ 0  1  0 ]

推导过程 #

矩阵快速幂的核心是构造状态向量，通过矩阵乘法将递推关系转化为状态转移。对于这个递推式，我们构造包含最近3项的状态向量：
[
\begin{bmatrix} F(n) \ F(n-1) \ F(n-2) \end{bmatrix}
]
我们需要用前一组状态 ( \begin{bmatrix} F(n-1) \ F(n-2) \ F(n-3) \end{bmatrix} ) 推导出当前状态，因此逐行确定矩阵元素：

1. 根据递推式，( F(n) = 0 \times F(n-1) + 1 \times F(n-2) + 1 \times F(n-3) )，对应矩阵第一行；
2. ( F(n-1) = 1 \times F(n-1) + 0 \times F(n-2) + 0 \times F(n-3) )，对应矩阵第二行；
3. ( F(n-2) = 0 \times F(n-1) + 1 \times F(n-2) + 0 \times F(n-3) )，对应矩阵第三行。

验证示例 #

用初始状态验证矩阵的正确性：

• 初始状态（n=2）：( \begin{bmatrix} F(2) \ F(1) \ F(0) \end{bmatrix} = \begin{bmatrix} 2 \ 1 \ 0 \end{bmatrix} )
• 乘以变换矩阵后得到：( \begin{bmatrix} 0×2 + 1×1 + 1×0 \ 1×2 + 0×1 + 0×0 \ 0×2 + 1×1 + 0×0 \end{bmatrix} = \begin{bmatrix} 1 \ 2 \ 1 \end{bmatrix} )，对应 ( \begin{bmatrix} F(3) \ F(2) \ F(1) \end{bmatrix} )，而根据递推式计算 ( F(3)=F(0)+F(1)=0+1=1 )，结果完全一致。

内容的提问来源于stack exchange，提问作者Sujan Ahmed