Гарри и носки

Мысленно положим левые носки в ряд так, что все носки лежат непрерывным и занумеруем их в таком порядке.

По сути мы хотим найти число таких перестановок правых носков, что ни для одной позиции цевого и правого носка не совпадают.

Пусть A{x1, x2, ..., xk} - множество перестановок правых носков, про которые верно, что носки с номерами {x1, x2, ..., xk} будут иметь пару такого же цвета.

В таком случае ответом на задачу является . Научимся считать |A{x1, x2, ..., xk}|. Пусть в множестве xi p1 носков цвета 1, p2 носков цвета 2, ..., pm носков цвета m. Тогда мы выберем, какая будет пара для этих носков, а у остальных может быть любая пара. Способов так сделать: .

По формуле включений-исключений . Давайте для каждого k от 0 до n посчитаем сумму размеров множеств A с таким k. Для этого посчитаем dpcolor, used - число способов найти пару носкам первых color цветов так, чтобы used носков имели пару свокго цвета. Переход — это перебор числа носков, среди носков данного цвета, которые будут иметь пару своего цвета.

Более формально: , а ответ равен .

Суммарное время на подсчёт dpi, j — O(n2).