查找C++中的序列

Question

我發現在你被賦予此型序列的問題的第N項：

你有

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

作爲一個無恥的自我推銷，我編碼了a program to solve linear recurrences using matrix multiplication。文件頂部的註釋描述了你想要形成的矩陣，以及如何使用重複平方算法來有效地計算遞歸的第n項。

希望這會有所幫助！