Включение-исключение (продвинутый)
Многие сложные задачи И-И выглядят невозможными, потому что есть подмножеств.
Трюк такой:
Если
то
Это самый важный трюк упрощения.
Когда вы получаете пугающую формулу, спросите:
Посчитать строки длины над символами так, чтобы каждый символ встретился хотя бы один раз.
Пусть = «символ отсутствует».
Тогда:
Пересечение зависит только от того, сколько символов запрещено:
Так что группируем по размеру:
Больше нет цикла по подмножествам — только один цикл по .
Посчитать перестановки без неподвижных точек.
Пусть = «позиция фиксирована».
Тогда:
Если , фиксация этих позиций оставляет перестановок.
Значит:
Снова, пугающее И-И по подмножествам превращается в одну сумму.
Посчитать решения
Пусть = «».
Для выбранного множества нарушенных переменных подставим:
Тогда общая сумма уменьшается на .
Число неотрицательных решений становится:
Зависит только от , значит:
(Некорректные слагаемые равны .)
Посчитать числа в , делящиеся хотя бы на одно значение из .
Пусть = «число делится на ».
Тогда:
Если — различные простые, то НОК — просто произведение.
Не каждое И-И нужно «сворачивать». Иногда оптимизация — это доказать, что мало.