Восьма лекція п’ятого сезону відбудеться 5 грудня о 18 годині у 265 аудиторії головного корпусу університету імені Івана Франка.
Лекція містить матеріал підвищеної складності.
Лекцію веде: Jarlax.
Тема: Теорема Пойа.
На порядку денному:
- Лема Бернсайда.
- Задача про намисто.
- Задача про розфарбування кубика.
- Теорема Пойа.
Задачі по лекції:
Знайти кількість різних розфарбувань кубика в n кольорів, так, щоб кубик був розфарбований рівно в k кольорів.
Аналогічно з намистом – нехай намисто складається з n намистинок, які можуть бути фіолетовими і рожевими. Знайти кількість різних намист, які складаються з k фіолетових намистин.
А також:
http://acm.timus.ru/problem.aspx?space=1&num=1661
http://acm.timus.ru/problem.aspx?space=1&num=1015
http://codeforces.com/problemset/problem/98/A
По задачі з намистом, наскільки я розумію, розв’язок якийсь такий:
Переберемо перестановку (циклічний зсув), порахуємо кількість циклів (в i-ї перестановки буде GCD(i, N) циклів однакового розміру L = N/GCD(i, N)). Тепер, коли ми це знаємо, нам потрібно щоб рівно K намистин було фіолетовими. Оскільки нам потрібно, щоб в межах циклу колір був однаковим, то якщо K не ділиться на L, до результату нічого не додаємо, переходимо до наступного зсуву. Якщо ж K ділиться на L, то рівно K/L циклів повинні бути розфарбованими фіолетовим кольором. Тому, до результату потрібно додати C(GCD(i, N), K/L). В кінці все поділити на N.
І взагалі, наскільки я розумію, всередині цієї формули 1/N*SUM(…) можна використовувати різні формули для розфарбувань, навіть якісь динаміки, головне щоб в межах циклу колір залишався однаковим.
До списку додаю також ще одну задачу:
http://neerc.ifmo.ru/school/io/archive/20110226/problems-20110226-individual.pdf, задача Д.
Ну і, звісно, задача з Контестера:
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1153&