Изменения

# Заданы три строки из цифр и знаков вопроса $a$, $b$ и $c$. Сколько существует троек чисел $x$, $y$ и $z$, таких, что $x$ получается из $a$ заменой знаков вопроса на цифры, $y$ из $b$ и $z$ из $c$ аналогичным способом, и $x+y=z$ за время $O(\log(\max(|a|, |b|, |c|))$.

# Петя проводит $n$ независимых экспериментов, известны вероятности $p_i$ успешности $i$-го эксперимента. Посчитайте матожидание квадрата числа успешных событий за время $O(n^2)$.

# Есть $n$ монеток на прямой, координата $i$-й $x_i$ (все $x_i$ различны). У каждой монетки есть вес $w_i$. Монетки можно двигать в сторону уменьшения координаты по прямой, несколько монеток может быть в одной точке. Подвинуть монетку $i$ на единицу влево стоит $w_i$ денег. Задано число $k$ ($k < n$), нужно за минимальное количество денег подвигать монетки так, чтобы осталось ровно $k$ точек, в которых есть хотя бы одна монетка. Найдите это минимальное число денег за $O(nk \log{n})$.

# $f_0 = 1$, $f_1 = 2$, $f_i = f_{i-1} + f_{i-2} + i$. Вычислите $f_n$ за $O(\log{n})$ арифметических операций.

# Кузнечик прыгает по прямой в положительном направлении и всегда находится только в целых точках. Изначально он стоит в точке с координатой 1. Если кузнечик стоит в точке $x$, то он может прыгнуть в точки $x+1, x+2, \ldots, x+k$, где $k$ {{---}} максимальное число такое, что $x$ делится на $2^{k-1}$. Вам задано число $n$. Найдите число способов кузнечику добраться до точки $n$ за $O(\log^\alpha{n})$ для некоторого $\alpha$.

</wikitex>