Изменения
Нет описания правки
# Модифицируйте алгоритм возведения в степень, чтобы посчитать $\sum\limits_{i=1}^n A^i$, где $A$ матрица, не изменяя размер матрицы.
# Кузнечик прыгает по прямой в положительном направлении и всегда находится только в целых точках. Изначально он стоит в точке с координатой 1. Если кузнечик стоит в точке $x$, то он может прыгнуть в точки $x+1, x+2, \ldots, x+k$, где $k$ {{---}} максимальное число такое, что $x$ делится на $2^{k-1}$. Вам задано число $n$. Найдите число способов кузнечику добраться до точки $n$ за $O(\log^\alpha{n})$ для некоторого $\alpha$.
# Рассмотрим последовательность отрезков с целыми концами: $[l_1, r_2]$, $[l_2, r_2]$, $\ldots$, $[l_m, r_m]$ ($1 \le l_i \le r_i \le n$). Вам задан $x$ ($1 \le x \le n$), найдите число различных последовательностей отрезков, что никакой не вкладывается в другой и существует $i$, что $l_i=x$, за время $O((nm)^\frac{3}{2})$.
</wikitex>
