时间戳

首页 > 解决方案 > 计算：f(n) = f(n - 1) + f(n - 2) + f(n - 3) + n * n * (n + 1)

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

问题描述

对于递归关系：

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，我想使用在O(log n)时间内运行的方法找出f(n) 。

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

标签： algorithmrecurrence

解决方案

该矩阵方程仍然可以建立，但也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

像往常一样，如果最终答案是模数，这一切都可以通过模运算来完成，否则可能会因为接近 10 18M的值变得太大。n

推荐阅读