Мысленно положим левые носки в ряд так, что все носки лежат непрерывным и занумеруем их в таком порядке.
По сути мы хотим найти число таких перестановок правых носков, что ни для одной позиции цевого и правого носка не совпадают.
Пусть 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).