Absolutely Inadequate Operations#12850

Absolutely Inadequate Operations (Editorial)

Розглянемо префіксні суми pref_1, pref_2, \ldots, pref_n (pref_i = a_1 + a_2 + \ldots + a_i). Легко помітити, що коли ми робимо операцію з позицією , то префіксні суми та pref_i міняються місцями, а інші не змінюються.

Зрозуміло, що є однозначна відповідність між різними масивами префіксних сум та різними масивами, отже досить порахувати кількість різних масивів префіксних сум. Наша операція дозволяє поміняти місцями довільні дві сусідні з перших n-1 сум, а отже ми можемо отримати будь-яку перестановку цих сум.

Кількість конфігурацій тоді рівна \frac{(n-1)!}{\prod_x cnt_x!}, де cnt_x позначає скільки разів дане зустрічається серед перших n-1 префіксних сум.