Індекс

У цій задачі розглядаються два розбиття числа $n$: \lambda = a_1 + a_2 + \dots + a_k та \mu = b_1 + b_2 + \dots + b_l. Кожне розбиття визначає певні ребра в графі з $n$ вершинами наступним чином:

Для першого розбиття вершини $1$ і a_1, $2$ і a_1-1, і так далі, з'єднуються. Якщо a_1 непарне, середня вершина залишається нез'єднаною. Для другого розбиття вершини a_1+1 і a_1+a_2, a_1+2 і a_1+a_2-1 і т.д. з'єднуються аналогічним чином. Ребра, відповідні другому розбиттю, додаються аналогічно (у графі можуть з'являтися кратні ребра).

Наприклад, якщо n = 10, \lambda = 3+4+2+1, а \mu = 3+5+2, то в отриманому графі будуть два ребра між вершинами $1$ і $3$, вершина $4$ буде з'єднана з $7$ і $8$, $5$ — з $6$ і $7$, $6$ — лише з $5$, $7$ — з $4$ і $5$, $8$ — з $4$ і $9$, $9$ — з $8$ і $10$, а $10$ — лише з $9$.

Вітю цікавить індекс пари розбиттів, який визначається як 2b + a, де $a$ — кількість ланцюгів у графі, а $b$ — кількість кілець. Ланцюгом є зв'язна компонента, для якої існує упорядкування вершин таке, що будь-які дві сусідні вершини з'єднані ребром і більше немає інших ребер. Кільцем є ланцюг з додатковим ребром, що з'єднує його кінцеві вершини. Зв'язна компонента — це зв'язний підграф, у який не можна додати жодної вершини, не втративши зв'язності. Ізольована вершина вважається ланцюгом.

У наведеному прикладі граф має одне кільце (з вершин $1$ і $3$) і два ланцюги: $(2)$ та (6, 5, 7, 4, 8, 9, 10). Отже, індекс цієї пари розбиттів дорівнює $4$.