Решение задачи Разбиения с Codeforces
С пояснением   Просмотров: 1849
Посчитайте суммарный вес всех различных разбиений данного множества на k непустых подмножеств по модулю 109 + 7. Два разбиения считаются различными, если существуют два объекта x и y, такие, что в одном разбиении они принадлежат разным множествам, а в другом — одному и тому же.
Пояснение к задаче
Для того, чтобы эффективно решать данную задачу, заметим следующие факты. Во-первых, результирующий ответ будет состоять из суммы весов объектов w i, взятых с некоторыми коэффициентами cf i, и, следовательно, задачу можно свести к подсчету этих коэффициентов.
Тогда cf i можно посчитать перебрав размер подмножества, в который попадет объект i, а именно: , где f(n, k, size) — количество разбиений множества из n на k подмножеств, где одно из них имеет размер size, и в нем находится i.
Данный способ не очень эффективен, поэтому заметим следующий факт: каждый элемент j, попав в одно подмножество с элементом i увеличит размер данного подмножества на 1, и, соответственно, коэффициент при w i. Тогда для i-го объекта достаточно перебрать объект j, который попадет с ним в одно подмножество, т.е . g(n, k, i, j) — количество способов разбить множество из n элементов на k подмножеств так, чтобы i-й и j-й находились в одном подмножестве.
Для подсчета g(n, k, i, j) воспользуемся числами Стирлинга второго рода: — кол-во способов разбить множество из n элементов на k непустых подмножеств. Если i = j, то , иначе просто объединим i и j в один объект и .
Финальная формула примет следующий вид: . Ответ в таком случае равен .
Для подсчета чисел Стирлинга можно воспользоваться формулой включения-исключения, которую несложно вывести либо найти в Википедии: .
Результирующая асимптотика — O(nlog(n)).
Автор: Администратор