Сегодня немножко математики.
Я думаю, что многие, кто занимался олимпиадами по информатике/спортивным программированием про это знают. Но когда-то мне очень сильно понравилась тема с ускорением подсчёта некоторых дп, если они являются линейной комбинацией прошлых вычисленных значений.
Предположим у нас есть следующее дп (не будем расписывать в общем виде):
dp[i] = 2dp[i-1] + 3dp[i-2] - dp[i-3]с какой-то базой. Например
dp[0, 1, 2] = {1, 2, 3}Предположим, мы хотим вычислить несколько конкретных значений (
dp[10^3], dp[10^15], то есть значения с очень большими номером), а не все (обычно так и бывает). Давайте посмотрим на это в виде матриц. Базовая матрица у нас имеет вид (это не определитель, я просто скобки не умею нормально рисовать):
| 1 |
a = | 2 |
| 3 |где
a_i это соответственно dp_i, i \in [0; 2]. Если мы перемножим матрицу ниже на столбец выше
| 0 1 0|
M = | 0 0 1|
|-1 3 2|мы получим вектор
| 2 |
| 3 |
| 11 |в котором мы по факту получили сдвиг в нашей дп-шной последовательности на 1 вперёд (то есть вычислили
dp[2], dp[3] и dp[4]). А теперь предположим, мы хотим найти
dp[n]. Конечно, эту последовательность умножений можно повторять раз за разом n - 3 раза, пока мы не получим нужный элемент. Но в чём тогда был смысл подобных движений? Давайте сначала нашу матрицу перехода бинарно возведём в (n-3)-ю степень и только потом умножим вектор a. Чтобы получить ответ, достаточно будет взять последний элемент получившегося столбца:ans = (bin_pow(M, n - 3) * a)[2];То есть по факту вы можете считать любую подобную “линейную” последовательность быстро для любого адекватного значения
n. Я когда-то, например, писал нахождение n-ого числа Фибоначчи на компиляции. Тут правда надо быть аккуратным с глубиной рекурсии и возможно подкрутить флаг -ftemplate-depth.