битмаски

Фермер Джон старается описать свой любимый USACO-контест Эльзе, но она не понимает почему ФД его так любит. ФД отвечает, моя любимая часть контеста - это когда Беси говорит сейчас время мычать и мычит весь контест.

Эльза всё равно не поняла, поэтому ФД выгрузил контест как текстовый файл и старается объяснить, что он значит. Контест определяется как массив из \(N\) (\(1\le N\le 10^6\)) целых чисел \(a_1, a_2, \dots, a_N\) (\(1\le a_i\le N\)). ФД определяет "МУУ" как массив из трёх целых чисел, из которых второе равно третьему, но не равно первому. Говорят, что МУУ случился во время контеста, если возможно удалить целые числа из массива так, что останется только МУУ.

Поскольку якобы Беси "мычала весь контест", помогите Эльзе посчитать количество различных МУУ, которые случились во время контеста. Два МУУ считаются различными, если они не состоят из одних и тех же чисел, идущих в одном и то же порядке.

Фермер Джон старается описать свой любимый USACO-контест Эльзе, но она не понимает почему ФД его так любит. ФД отвечает, моя любимая часть контеста - это когда Беси говорит сейчас время мычать и мычит весь контест.

Эльза всё равно не поняла, поэтому ФД выгрузил контест как текстовый файл и старается объяснить, что он значит. Контест определяется как массив из \(N\) (\(1\le N\le 10^6\)) целых чисел \(a_1, a_2, \dots, a_N\) (\(1\le a_i\le N\)). ФД определяет "МУУ" как массив из трёх целых чисел, из которых второе равно третьему, но не равно первому. Говорят, что МУУ случился во время контеста, если возможно удалить целые числа из массива так, что останется только МУУ.

Поскольку якобы Беси "мычала весь контест", помогите Эльзе посчитать количество различных МУУ, которые случились во время контеста. Два МУУ считаются различными, если они не состоят из одних и тех же чисел, идущих в одном и то же порядке.

У Фермера Джона есть \(N\) коров, помеченных числами от \(1\) до \(N\) (\(2\le N\le 16\)). Отношение дружбы между этими коровами может быть смоделировано ненаправленным графом с \(M\) (\(0\le M\le N(N-1)/2\)) ребрами. Две коровы являются друзьями, если и только если между ними есть ребро в этом графе.

За одну операцию Вы можете добавить или удалить одно ребро в этом графе. Посчитайте минимальное количество операций, которое требуется выполнить, чтобы обеспечить следующее свойство в этом графе: Если коровы \(a\) и \(b\) - друзья, тогда для любой другой коровы \(c\) по крайней мере одна из коров \(a\) и \(b\) является другом коровы \(c\).

Замечание: время на тест 2.5 сек, по умолчанию 1.25.

Замечание: необходимо использовать 64-битные типы данных (например "long long" в C/C++).

Фермер Джон тренирует своих коров стрельбе из лука следующим упражнением на координатной плоскости.

Всего имеется \(N (1 \leq N \leq 4 \cdot 10^4)\) прямоугольных мишеней со сторонами параллельными осям координат и \(4N\) коров. Каждая корова должна быть назначена различной вершине прямоугольника. В момент \(i\), для \(1 \leq i \leq N\):

1. Цель \(i\) появляется.
2. \(4\) коров, назначенные своим вершинам, стреляют по ним.
3. Если выстрел коровы попадает во внутренность мишени, прежде чем он попадёт в назначенную вершину или пройдёт мимо, корова не выполнила упражнение.
4. Мишень исчезает, чтобы освободить место для следующей мишени.

Каждая корова расположена на \(y\)-оси \((x = 0)\), и каждая мишень - это прямоугольник, где мишень \(i\) имеет нижний левый угол в точке \((X_1, y_1^{(i)})\) и правый верхний угол в точке \((x_2^{(i)}, y_2^{(i)})\). Эти координаты также удовлетворяют условиям \(1 \leq X_1 < x_2^{(i)}\leq 10^9\) и \(1 \leq y_1^{(i)} < y_2^{(i)} \leq 10^9\) (Замечание: \(X_1\) одно и то же для каждой мишени).

В дополнение, каждая корова имеет свой "фокусный угол", где она может работать. Поэтому корова поворачивается на этот специфический угол, когда стреляет. Полагая, что их стрела летит по прямой от их позиции к назначенной вершине траектория стрелы \(i\)'-ой коровы может быть описана \(s_i\) \((0 < |s_i| < 10^9)\), наклоном траектории.

ФД хочет минимизировать расстояние между самыми дальними коровами. Если ФД оптимально назначит каждой корове её целевую вершину и оптимально разместит их на оси \(y\), вычислите минимальное расстояние между самыми дальними коровами или коровы всегда не выполнят упражнение.

Каждый тест содержит \(T\) (\(1 \leq T \leq 10\)) независимых подтестов. Гарантируется, что сумма всех \(N\) по всем подтестам не превысит \(4\cdot 10^4\).

**Замечание: Ограничение по памяти для этой задачи 512MB, в два раза больше чем по умолчанию.**

Каждой из \(N\) (\(1\le N\le 5\cdot 10^5\)) коров Фермера Джона назначена ненулевая битовая строка длиной \(K\) (\(1\le K\le 20\)). Различным коровам может быть назначена одинаковая битовая строка.

Сходство Жаккара двух битовых строк определяется как количество (?единичных) битов в их пересечении, делённое на количество (?единичных) битов в их объединении. Например, сходство Жаккара битовых строк \(\texttt{11001}\) и \(\texttt{11010}\) равно \(2/4\).

Для каждой коровы выведите сумму сходств Жаккара её с битовыми строками всех других коров, включая её саму, по модулю \(10^9+7\). Точнее если сумма равна рациональному числу \(a/b\), где \(a\) и \(b\) целые числа, не имеющие общих делителей, выведите уникальное целое число \(x\) в интервале \([0,10^9+7)\) такое, что \(bx-a\) делится на \(10^9+7\).

**Примечание. Ограничение по времени для решения этой задачи в Python – 15 секунд. Для других языков ограничение по времени по умолчанию составляет 2 секунды.**

Каждый из \(N\) амбаров фермера Джона (\(2\le N\le 10^5\)) выбрал команду из \(C\) коров (\(1\le C\le 18\)) для участия в дне поля. Порода каждой коровы либо Guernsey либо Holstein.

Разница между двумя командами определяется как количество позиций \(i\) (\(1 \leq i \leq C\)), при котором породы коров на \(i\)-х позициях отличаются. Для каждой команды \(t\) из \(1 \ldots N\) вычислите максимальную разницу между командой \(t\) и любой другой командой.

**Замечание: Время на тест в этой задаче 4s, в два раза больше обычного.**

Беси хочет пойти спать, ей нужно выключить все лампы. Как это сделать?

У Беси есть две битовые строки длиной \(N\) (\(2\le N\le 20\)), представляющие последовательность лампочек и переключателей, соответственно. Каждая лампочка включена(1) или выключена(0). Каждый переключатель активен(1) или неактивен(0).

Один *шаг* состоит из следующей последовательности операций:

1. Переключить ровно один переключатель (сделать активным, если он неактивный или наоборот).
2. Для каждого активного переключателя переключить состояние соответствующей лампочки (выключить, если она была включена или наоборот).
3. Циклически сдвинуть переключатели вправо на один. А именно, если битовая строка соответствующая переключателям была изначально \(s_0s_1\dots s_{N-1}\) она превратится в строку \(s_{N-1}s_0s_1\dots s_{N-2}\).

Для каждого из \(T\) (\(1\le T\le 2\cdot 10^5\)) примеров описанной выше проблемы посчитайте минимальное количество ходов выключить все лампочки.

Очень жаркое лето. Фермер Дон решил купить некоторое количество кондиционеров.

У ФД имеется \(N\) коров (\(1 \leq N \leq 20\)), которые живут в амбаре, содержащем последовательность стойл, пронумерованные \(1 \ldots 100\). Корова \(i\) занимает диапазон стойл, начиная с \(s_i\) и заканчивая в \(t_i\). Диапазоны стойл, занимаемые коровами, не пересекаются. У коров различные требования к охлаждению. Корова \(i\) должна быть охлаждена на количество \(c_i\). Это значает, что для всех стойл, занимаемых коровой \(i\) температура должна быть уменьшена на \(c_i\) единиц.

Амбар содержит \(M\) кондиционеров, помеченных \(1 \ldots M\) (\(1 \leq M \leq 10\)). \(i\)-ый кондиционер стоит \(m_i\) единиц денег, если работает и охлаждает воздух (уменьшает температуру) в стойлах начиная в \(a_i\) и заканчивая в \(b_i\). Если работает, \(i\)-ый кондиционер уменьшает температуру во всех стойлах этого диапазона на величину \(p_i\) (\(1 \leq p_i \leq 10^6\)). Диапазоны стойл кондиционеров могут перекрываться.

Определите минимальное количество денег, которое ФД должен потратить, чтобы сделать температуру комфортабельной для всех коров во всех стойлах. Гарантируется, что это возможно сделать.

123
456
789

Беси может нажимать одну клавишу, две клавиши одновременно (имеющие общую сторону, всего 12 комбинаций), 4 клавиши одновременно, которые формируют квадрат (1245, 2356, 4578, or 5689).

Например, если телефонный номер 123659874, она может сэкономить время следующим образом:

1. Нажать 1 и 2 одновременно.
2. Нажать 3.
3. Нажать 6, 5, 9, 8 одноврменно.
4. Нажать 7 и 4 одновременно.

Однако при нажатии нескольких клавиш одновременно, цифры могут могут записаться в произвольном порядке. Например, после последнего нажатия (7 и 4 одновременно) может получиться 123596847 или 213659874

По заданной последовательности цифр, вычислите количество телефонных номеров, которые она может набрать, по модулю \(10^9+7\).

**Замечание: Время на тест для этой задачи 4s, в два раза больше чем обычно..**

ФД по лени просто назначил корове \(i\) подарок \(i\) для всех \(i\). Теперь коровы собрались и решили переназначить подарки так, чтобы у каждой коровы либо остался изначальный подарок, либо он был заменён на более предпочитаемый подарок.

Имеется также дополнительное ограничение: подарок может быть переназначен корове, если он изначально был назначен корове такого же типа (Holstein или Guernsey)). Задано \(Q\) (\(1\le Q\le \min(10^5,2^N)\))длин \(N\) строк пород для каждой из них вычислите количество переназначений, соответствующих ей.

Замечание: Здесь, \(a\oplus b\) обозначает побитовое исключающее ИЛИ неотрицательных целых чисел \(a\) и \(b\). Эта операция эквивалентна сложению соответствующих пар битов по модулю 2 и игнорированию переноса. Например

У Беси есть \(N\) (\(1\le N\le 2\cdot 10^4\)) ящиков с компонентами. \(i\)-ый ящик содержит компоненты с номерами от \(l_i\) до \(r_i\) включительно \((0\le l_i \le r_i \le 10^9)\). Никакие два ящика не содержат одинаковые компоненты. Беси хочет узнать, сколько уникальных микстур из трёх различных компонент она может создать. Две микстуры рассматриваются как различные, если хотя бы одна компонента есть в одной микстуре и отсутствует в другой. Ответ выводите по модулю \(10^9 + 7\).

SCORING

• В тестах 3-4 \(\max(K,r_N)\le 10^4\).
• В тестах 5-6 \(K=2^k-1\) для некоторого целого \(k\ge 1\).
• В тестах 7-11 \(\max(K,r_N)\le 10^6\).
• В тестах 12-16 \(N\le 20\).
• В тестах 17-21 нет дополнительных ограничений.