Формула включения-исключения (2024/25 учебный год)

1. Разминка: посчитать кол-во чисел от 1 до 10⁹
   1. Которые не делятся ни на одно из p₁, p₂, ... p_n
   2. Которые не делятся ни на одно из a₁, a₂, ... a_n
   3. Взаимнопросты с m
   
   
2. Задачи
   1. Посчитать число путей из (1,1) в (n,n) вправо-вверх (n ≤ 10⁹), не проходящих ни через одну из заданных клеток (x_i,y_i)
   2. Заданы числа n ≤ 10¹² и k ≤ 100, сколько множеств из k чисел имеют lcm = n? neerc (D)
   3. Мёбиус: количество подпоследовательностей с НОД=1 cf
   4. Количество беспорядков (перестановок без p_i = i)
   5. Цэшки: количество матриц 250*250, в которых в каждой строке/столбце min=1 cf
   
   
3. Суммы в подмножествах
   1. Как посчитать для каждого подмножества сумму по всем его подмножествам? (ДП за 2ⁿn)
   2. Обратная задача: как по суммам в подмножествах посчитать исходных значения? (ФВИ, или чуть поменять ДП)
   3. Количество гамильтоновых путей за 2ⁿnm и полином памяти
   4. Количество вершинных покрасок за 2ⁿn без восстановления ответа, OR-свёртка
   
   
4. Свёртки
   1. OR-свёртка (было выше)
   2. disjoint-OR-свёртка (FFT, size-trick)
   3. XOR-свёртка, (Адамар) , (wiki)
      1. AND, XOR : дистрибутивность
      2. AND, XOR : аналогичный трюк с OR-свёрткой : (-1)^{popcount(i and a)}
      3. Аналог FFT для преобразования Адамара (сразу пишем нерекурсивно)
   
   
5. [skipped] Бонус
   1. [skipped] число неприводимых многочленов степени n над F_p (мёбиус)