algorithm - 计算线性循环序列

Question

我有一系列数字 A。有一个索引 - k，它将作为参数传递给程序。该级数是等差数列 (d=1)，直到第 k 个元素。例如:

A₀ = 0, A₁ = 1 [...] A_k-1 = k-1.

从那时起，每个元素都是最后k个元素的总和。例如:

A_k+3 = A₂ + A₃ + [...] + A_k+2.

用户输入一个数字n(和k，如前所述)。该程序需要计算并返回所述系列 A 的第 n 个元素。

例子:k = 5, n = 8

A₀ = 0, A₁ = 1, A₂ = 2, A₃ = 3, A₄ = 4, A₅ = 10, A₇ = 20, A₇ = 39, A₈ = 76

A = [0,1,2,3,4,10,20,39,76]

A_n = 76

有什么想法吗？在过去的几天里，这一直困扰着我，但数学从来都不是我的事，所以我想这是找到一个聪明方法的大问题(当然除了有一个循环 - 这听起来并不聪明)。另外，如果我犯了任何错误，抱歉，英语不是我的主要语言。

Answer 1

稍微扩展 Oli Charlesworth 的回答，考虑向量

A_n = [ A_n, A_n-1 ... A_{n -k+1} ]

你知道的

A_n = A_n-1 + ... + A_n-k

所以你可以用 A_n-1 表示 A_n 为

A_n = B A_n-1

其中 B 是 k x k 矩阵，其中第一行为 1，主对角线下方为 1，其他位置为零.例如，对于 k= 4 你有

    1   1   1   1
B = 1   0   0   0
    0   1   0   0
    0   0   1   0

现在解决复现问题

A_n = B^n-k+1 A_>k-1

与

A_k-1 = [k-1, k-2, k-3 ... 2, 1, 0]

使用快速矩阵求幂算法，您需要进行 log(n - k + 1) 次矩阵乘法才能得出答案，近似为 log(< em>n) 对于 n>> k。矩阵乘法的成本是 k³ 所以总复杂度是 k³ log(n )