Вычислить: 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, я хочу выяснить <strong>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 ¹⁸ .