计算：f(n) = f(n - 1) + f(n - 2) + f(n - 3) + n * n * (n + 1)

Question

对于递归关系：

f(0) = p
f(1) = q
f(2) = r
For n > 2,
f(n) = a * f(n - 1) + b * f(n - 2) + c * f(n - 3) + n * n * (n + 1)

给定一些 n <= 10 ^ 18，我想找出 f(n) 使用在 O(log n) 次。

如果 f(n) = f(n - 1) + f(n - 2) + f(n - 3)，我们可以使用矩阵求幂在 O(Log n) 时间内求解。但是 n * n * (n + 1) 项使问题复杂化。

Answer 1

那个矩阵方程还是可以成立的，但是还需要n的一些次方：

|F(n-0)|   | a, b, c, 1, 1, 0, 0 |   |F(n-1)|
|F(n-1)|   | 1, 0, 0, 0, 0, 0, 0 |   |F(n-2)|
|F(n-2)|   | 0, 1, 0, 0, 0, 0, 0 |   |F(n-3)|
|(n+1)³| = | 0, 0, 0, 1, 3, 3, 1 | * | n³   |
|(n+1)²|   | 0, 0, 0, 0, 1, 2, 1 |   | n²   |
| n+1  |   | 0, 0, 0, 0, 0, 1, 1 |   | n    |
| 1    |   | 0, 0, 0, 0, 0, 0, 1 |   | 1    |

然后通过平方求幂，最后将得到的矩阵乘以这个向量：

[r, q, p, 27, 9, 3, 1].T

像往常一样，如果要求最终答案取模 M，这一切都可以通过模运算来完成，否则对于 n 接近 10[= 的值可能太大了21=]18.

计算：f(n) = f(n - 1) + f(n - 2) + f(n - 3) + n * n * (n + 1)

Compute: f(n) = f(n - 1) + f(n - 2) + f(n - 3) + n * n * (n + 1)

algorithm

recurrence