Решение рекуррентных соотношений возведением матрицы в степень
Пусть дано рекуррентное соотношение $f_{j}=a_{1} f_{j-1}+\cdots+a_{k} f_{j-k}+b$, а также начальные значения $f_{0}, \ldots, f_{k-1}$; необходимо найти $f_{n}$.
Простой способ - применить метод динамического программирования: вычислить все значения $f_{j}$ по очереди за $O(n k)$. Для того, чтобы получить более быстрое решение, выпишем рекуррентное соотношение в матричном виде:
$$ \left(\begin{array}{c} f_{j} \\ f_{j-1} \\ f_{j-2} \\ \vdots \\ f_{j-k+1} \\ 1 \end{array}\right)=\left(\begin{array}{cccccc} a_{1} & a_{2} & \cdots & a_{k-1} & a_{k} & b \\ 1 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 & 0 \\ 0 & 0 & \cdots & 0 & 0 & 1 \end{array}\right) \cdot\left(\begin{array}{c} f_{j-1} \\ f_{j-2} \\ f_{j-3} \\ \vdots \\ f_{j-k} \\ 1 \end{array}\right) . $$Тогда
$$ \left(\begin{array}{c} f_{n} \\ f_{n-1} \\ f_{n-2} \\ \vdots \\ f_{n-k+1} \\ 1 \end{array}\right)=\left(\begin{array}{cccccc} a_{1} & a_{2} & \cdots & a_{k-1} & a_{k} & b \\ 1 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 & 0 \\ 0 & 0 & \cdots & 0 & 0 & 1 \end{array}\right)^{n-k+1} \quad \cdot\left(\begin{array}{c} f_{k-1} \\ f_{k-2} \\ f_{k-3} \\ \vdots \\ f_{0} \\ 1 \end{array}\right) . $$Для вычисления матрицы применим ту же идею, с помощью которой мы быстро вычисляли степень числа по модулю: с её помощью $(n-k+1)$-ю степень матрицы $(k+1) \times(k+1)$ можно вычислить за $O\left(k^{3} \log n\right)$. После этого найти $f_{n}$ можно за $O(k)$ (здесь мы для простоты считаем, что все операции с числами можно осуществлять за $O(1)$ ).
Пример: числа Фибоначчи
Применим этот метод к числам Фибоначчи. Поскольку рекуррентное соотношение для чисел Фибоначчи не содержит свободного члена, можно обойтись без последних строки и столбца матрицы.
$$ \binom{f_{n}}{f_{n-1}}=\left(\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right)^{n-1} \cdot\binom{1}{1} . $$С учётом того, что $f_{n}$ имеет длину $\Theta(n)$, получаем рекуррентное соотношение на время работы алгоритма $T(n)=T(n / 2)+M(n)$, где $M(n)$ - сложность умножения двух чисел длины $n$. Если воспользоваться алгоритмом Карацубы, получаем соотношение $T(n)=T(n / 2)+O\left(n^{\log _{2} 3}\right)$, откуда по основной теореме о рекуррентных соотношениях $T(n)=O\left(n^{\log _{2} 3}\right)$.