Возникли трудности в решении одной задачи. Далее попытаюсь популярно сформулировать подзадачу, для которой не получается придумать решение. Пусть есть некоторый набор рюкзаков. Для каждого рюкзака задана вместимость. Суммарная вместимость всех рюкзаков — N. Кроме того, есть N предметов, каждый из которых окрашен в один из N цветов (цвета разных предметов могут совпадать). Необходимо найти, сколькими способами можно разложить предметы по рюкзакам так, чтобы внутри одного рюкзака все предметы были одного цвета.
Ограничения небольшие, N <= 30.
Если вместимость каждого рюкзака 1, то, на сколько я понимаю, ответ — это просто число перестановок с повторениями. А в общем случае посчитать пока как-то не получается.
Все-таки неправильно.
Извините, но я не понял, что вы хотели сказать.
Я в предыдущей правке написал ссылку. Потом понял, что не умею читать и неправильно понял условие. В общем, не обращайте внимания)
Разбиваем предметы на K кучек одинакового цвета. Теперь для каждой вместимости i=1 to N посмотрим, если кол-во рюкзаков вместимости i не равно кол-ву кучек размером i, то ответ на задачу 0. Иначе кол-во способов расставить кучки в рюкзаки (всё той же размерности i) равно факториалу их кол-ва. После чего посчитанные факториалы для каждой из вместимостей перемножаем, это и есть ответ.
Спасибо! Вроде по времени должно влезть, затрудняюсь с ходу оценить асимптотику
Я допустил ошибку: при одной кучке предметов и большом кол-ве малых рюкзаков ответ, согласно моей идее, будет 0. Т.е. нужно перебрать все разбиения на K кучек, но я не знаю, как сделать это быстро.
Количество упорядоченных разбиений числа n на k целых неотрицательных — это C(k+n,k). UPD: извиняюсь, C(k+n-1,k-1) конечно.
Дело в том, что для каждого разбиения свой ответ считать надо.
Ещё один факт, который несколько уточняет задачу. На самом деле "рюкзаки" — это циклы, на которые разбиваются инвариантные перестановки из леммы Бернсайда. И необходимо найти, сколькими способами можно раскрасить перестановку, чтобы все циклы были одного цвета. Так вот, эти циклы получаются длиной не больше 5и.