Timus 1142

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Ссылка на задачу

Комментарии

Допустим, что N исходных объектов разделены на M групп, внутри каждой из которых все объекты равны. Установить отношения < между этими M группами (то есть упорядочить их) можно M! способами.

Следовательно, ответ для N равен ∑(K(N, M) × M!), где M = 1..N, а K(N, M) — количество способов разделить N объектов на M непустых групп (легко вычисляется динамическим программированием d[n][m]).