Блог пользователя SkyHawk

Подскажите задачи на лемму Бернсайда / теорему Пойа
Автор SkyHawk, 13 лет назад, По-русски

Собственно, сабж. 


Может ли кто-нибудь подсказать задач на эту тему? 

Также буду благодарен за любые другие интересные/необычные задачи по программированию на комбинаторику.
  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
http://acm.timus.ru/problem.aspx?space=1&num=1661
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
http://khcup.qbit.org.ua/dots/problems?id=1183
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Возможно я торможу, но меня не пускает на этот сайт...
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      На день рождения Ульяма его родители решили украсить его комнату квадратными флажками. Каждый флажок сшивается из девяти одинаковых по размеру квадратных лоскутков, причём каждый из лоскутков может быть одного из K цветов. Напишите программу, которая посчитает количество различных с точностью до поворотов и переворотов флажков, которые можно подарить на день рождения Уильяма.

      Входные данные

      В единственной строке входного файла записано одно число K (1<=K<=100)

      Выходные данные

      В выходной файл выведите единственное число – количество различных с точностью до поворотов и переворотов флажков, которые можно подарить на день рождения Уильяма.

      Copyright © 2005-2011 МНО Q-Bit, dotS Team;
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А еще там, наверное, можно зарегаться;)
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
http://codeforces.com/problemset/problem/98/A
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасибо, решил на контесте и уже запамятовал про эту задачу.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
http://acm.sgu.ru/problem.php?contest=0&problem=208
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
http://acm.timus.ru/problem.aspx?space=1&num=1015 вот еще простая, наверное тоже тем же решается?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    а разве это комбинаторика? или вы имеете ввиду как вариант решения?

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, воспользоваться леммой как одним из вариантов решения.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Вот более сложная:
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Там сползло оформление. Насколько я помню, ограничение на P: N < P <= 10^9
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А как там эти перестановки получить, динамикой что ли как-то?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну я решал комбинаторикой.
        Всего N! перестановок вершин, для применения леммы Бернсайда нужно посчитать, сколько графов не меняет каждая перестановка. Конечно, 53! это очень много, но реально там важны не сами перестановки, а размеры групп (циклов), которых столько же, сколько и разбиений N на слагаемые которых всего около 300,000.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем большое спасибо за задачи! (Прошу прощения, что апнул тему)
→ Ответить