c++ - 在 C++ 中查找序列中的第 N 项

Question

我发现了一个问题，你得到了这种类型的序列：

你有

  the first K terms : a1, a2, ... , ak; 
           K coefficients : b1, b2, ... , bk

和复发：

S(i) = b1*S(i-K) + b2*S(i-K+1) + ... + bk*S(i-1). 

我必须找出第 N 项。

我相信这个问题可以通过快速矩阵求幂来解决，但我很难发现我必须使用的矩阵。我正在尝试用 C++ 编写问题。谁能给我一些关于我应该如何处理这类问题的提示？

Answer 1

作为一个无耻的自我推销，我编写了一个程序来使用矩阵乘法来解决线性递归。文件顶部的注释描述了您想要形成的矩阵是什么，以及如何使用重复平方算法来有效地计算递归的第 n 项。

希望这可以帮助！