Бонусные лекции

1. Формула включения-исключения
1. Посчитать кол-во чисел от 1 до 10⁹
1. Которые не делятся ни на одно из p₁, p₂, ... p_n
2. Которые не делятся ни на одно из a₁, a₂, ... a_n
3. Взаимнопросты с m
2. Посчитать число путей из (1,1) в (n,n) вправо-вверх (n ≤ 10⁹), не проходящих ни через одну из заданных клеток (x_i,y_i)
3. Заданы числа n ≤ 10¹² и k ≤ 100, сколько множеств из k чисел имеют lcm = n? neerc
4. Мёбиус: количество подпоследовательностей с НОД=1 cf
5. Суммы в подмножествах
1. Как посчитать для каждого подмножества сумму по всем его подмножествам? (ДП)
2. Обратная задача: как по суммам в подмножествах посчитать исходных значения? (ФВИ, или чуть поменять ДП)
6. Количество беспорядков (перестановок без p_i = i)
7. Цэшки: количество матриц 250*250, в которых в каждой строке/столбце min=1 cf
2. NP-трудное
1. Покраска за 2ⁿ без восстановления ответа
2. Количество гамильтоновых путей за 2ⁿnm и полином памяти
3. Бонус: число неприводимых многочленов степени n над F_p (мёбиус)