#винтик_и_шпунтик — Public Fediverse posts

Винтик и Шпунтик, часть 3: лемма Бернсайда и генерация орбит

Это третья часть моих наработок по решению задачи Винтика и Шпунтика в рамках челленджа @vvvphoenix . В прошлой части мы хорошо так свернули формулу включений-исключений для ускорения вычисления ответа. В этой части мы дополнительно ускорим вычисление формулы, разбив слагаемые формулы на классы эквивалентности, где в каждом классе слагаемые одинаковые и их надо будет вычислять только один раз. В этом нам поможет комбинаторная теория групп и её применение в задачах о раскрасках. По большей части эта статья содержит общую теорию решения подобных задач, так что эта информация может быть полезна и вне контекста задачи про Винтика и Шпунтика.

https://habr.com/ru/articles/919712/

#винтик_и_шпунтик #комбинаторика #теория_групп #лемма_бернсайда