Изменения

# Заданы $n$ строк из цифр. Петя в случайном порядке эти строки склеивает, выбирая, каждую из перестановок равновероятно. Задано число $k$. С какой вероятностью Петино число делится на $k$, посчитать за время $O(2^n \cdot n)$.

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

</wikitex>