ПерестановочкИ#12854

ПерестановочкИ (Розбір)

Помітимо спершу, що задача, по суті, просить порахувати нас кількість таких відрізків , що p_i та p_j це максимальний та мінімальний елемент серед чисел p_i, p_{i+1}, \ldots, p_j (в якомусь порядку). Дійсно: у всіх таких відрізків пари різні, а для відрізку , для якого умова вище не виконується, пара співпадає з парою (i_1, j_1), де i_1, j_1 — позиції мінімуму та максимуму на цьому відрізку.

Далі зауважимо, що достатньо порахувати математичне очікування по всім перестановкам, і помножити його на .

Знайдемо для кожної пари імовірність того, що p_i та p_j це максимальний та мінімальний елемент серед чисел p_i, p_{i+1}, \ldots, p_j (в якомусь порядку). Для i = j ця імовірність рівна , тому ми додаємо до математичного очікування n. Для i<j ця імовірність рівна \frac{2}{(j-i+1)(j-i)}, адже це просто ймовірність того, що мінімальний елемент з цього відрізку потрапив в один з його кінців (\frac{2}{j-i+1}), а потім максимальний потрапив в інший кінець (\frac{1}{j-i}).

Таким чином, тепер для кожного відрізка довжини потрібно додати до відповіді \frac{2}{len(len-1)}. Отже, математичне очікування рівне

n + \sum_{2\le len \le n} (n+1-len)\frac{2}{len(len-1)}

. Щоб отримати відповідь, достатньо помножити це на .