如何将递推关系转化为矩阵比如说F[x+2]=Af[x+1]+Bf[x]+C那么如何构造矩阵使用快速幂加速为LOG(N)呢

如何将递推关系转化为矩阵
比如说F[x+2]=Af[x+1]+Bf[x]+C
那么如何构造矩阵使用快速幂加速为LOG(N)呢?
zcan 1年前 已收到1个回答 举报

qiyue_123 幼苗

共回答了18个问题采纳率:88.9% 举报

令G[x] = (f[x+2],f[x+1],f[x])^T
那么可以写出一阶递推关系
G[x+1] = M G[x]
其中
M =
A B C
1 0 0
0 1 0
然后G[n] = M^n G[0],M^n只需要O(logn)的计算量

1年前 追问

1
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.029 s. - webmaster@yulucn.com