Комбинаторика и множества на Python: как решать + 4 задач с проверкой

Комбинаторика и множества — это про «сколько всего» и «сколько подходит под условия», когда перебор слишком дорогой. На олимпиадах это встречается в задачах про окрашенные кубики (как в CubeCraft), сломанные сегменты на табло, круговые турниры (сколько матчей, пар, расписаний), пути по клетчатому полю с запретами и ловушками.

Как распознать, что нужна комбинаторика:

• в условии просят количество объектов/способов, а не сами объекты;
• размеры большие (например, n до 1e6), и симуляция типа «пройти все кубики/все клетки» не проходит;
• есть слова «ровно k», «не менее», «хотя бы», «все внешние», «разные», «пересечение условий»;
• ответ удобно разбивается по типам: внутренние/граничные, углы/рёбра/грани, работающие/сломанные сегменты.

Суть приёма: мы описываем множество всех вариантов и считаем его размер через разбиение на непересекающиеся случаи или через операции над множествами (объединение, пересечение, дополнение). Часто помогает принцип включения-исключения: сначала складываем «подходят условию A» и «подходят условию B», затем вычитаем те, кто посчитался дважды, и так далее. Это ускоряет решение, потому что вместо перебора получаем формулу и считаем за O(1) или O(log n).

С чего начать учиться:

• тренируй разбиение на случаи: «углы/рёбра/грани/внутри», «ровно k совпадений»;
• учись считать дополнение: «все минус плохие»;
• выписывай множества и их пересечения в маленьких примерах, проверяй на n=1,2,3;
• следи за переполнением: часто нужен 64-битный ответ;
• собирай типовые формулы для решёток, турниров, размещений/сочетаний.

Ниже — задачи с автопроверкой и разбором подхода.