дп

Сначала все \(N\) коров (\(2\le N\le 10^5\)) стоят в ряд, корова \(i\) стоит на позиции \(i\). Последовательность перемещений в танце задаётся \(K\) (\(1\le K\le 2\cdot 10^5\)) парами позиций \((a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})\). В каждую минуту \(i = 1 \ldots K\) танца, коровы в позициях \(a_i\) и \(b_i\) меняются позициями. Аналогичные \(K\) обменов произойдут в минуты \(K+1 \ldots 2K\), затем в минуты \(2K+1 \ldots 3K\), и т.д. до истечения \(M\) минут (\(1\le M\le 10^{18}\)) Другими словами

• В минуту \(1\), коровы в позициях \(a_1\) и \(b_1\) меняются позициями.
• В минуту \(2\), коровы в позициях \(a_2\) и \(b_2\) меняются позициями.
• ...
• В минуту \(K\), коровы в позициях \(a_{K}\) и \(b_{K}\) меняются позициями.
• В минуту \(K+1\), коровы в позициях \(a_{1}\) и \(b_{1}\) меняются позициями.
• В минуту \(K+2\), коровы в позициях \(a_{2}\) и \(b_{2}\) меняются позициями.
• и т.д. ...

Для каждой коровы определите количество уникальных позиций, которые она занимала во время танца.

Замечание: время на тест удвоено.

По сигналу Фермера Джона некоторые из коров образуют пары так, что

• Каждая пара состоит из коров пород Holstein \(h\) и Guernsey \(g\) чьи положения не более чем на \(K\) друг от друга (\(1\le K\le 10^9\)); то есть, \(|x_h-x_g|\le K\).
• Каждая корова или часть какой то пары, или не входит ни в какую пару.
• Разбиение на пары является максимальным если никакие из оставшихся коров не могут образовать пару.

Определите диапазон возможных сумм весов коров не попавших в пары, а именно

• Если \(T=1\), вычислите минимально возможную сумму весов неспаренных коров.
• Если \(T=2\), вычислите максимально возможную сумму весов неспаренных коров.

Эльза старается угадать это число. Она может задавать вопросы вида \(i\) больше или меньше?" для некоторого \(i\) от \(1\) до \(N\) включительно. Беси отвечает "HI!" если \(i\) больше чем \(x+0.5\), и "LO!", если \(i\) меньше чем \(x+0.5\).

Эльза работает в соответствии со следующей стратегией. Она создала список из \(N\) чисел, где каждое число от \(1\) до \(N\) встречается ровно один раз (другими словами, этот список является перестановкой размера \(N\).). Затем она идёт по этому списку называя числа для угадывания из него по порядку. Однако она пропускает все бесполезные запросы. Так если Эльза должна спросить число \(i\) а ранее она спрашивала число \(j < i\) такое, что Беси ответила "HI!", Эльза не спрашивает \(i\), а переходит к следующему числу в списке. Аналогично, если она ранее спрашивала про число \(j > i\), на которое Беси ответила "LO!", Эльза также пропускает это число \(i\) и переходит к следующему в списке. Можно доказать, что используя эту стратегию, Эльзая всегда уникально определит \(x\) вне зависимости от перестановки, которую она создаст.

Если мы сконкатенируем все ответы Беси "HI" или "LO" в одну строку \(S\), количество раз которое Беси ответит "HILO" есть количество подстрок длины \(4\) в строке \(S\), которые равны "HILO".

Беси знает, что Эльза использует эту стратегию и даже уже выбрала число \(x\), однако она не знает, какую перестановку использует Эльза. Ваша задача - вычислить сумму количеств раз, которые Беси скажет "HILO" для всех перестановок, которые Эльза может использовать - по модулю \(10^9+7\).

Разбрызгиватель для пшеницы в квадрате \((I,J)\) разбрызгивает на все квадраты ниже и слева: то есть, квадраты \((i,j)\) с \(I \le i\) и \(j \le J\).

Разбрызгиватель для люцерны в квадрате \((I,J)\) разбрызгивает на все квадраты вверху и справа: то есть, квадраты \((i,j)\) с \(i \le I\) b \(J \le j\).

На квадрате до которого достаёт один или более разбрызгиватель для пшеницы может расти пшеница, на квадрате до которого достаёт один или более разбрызгиватель для люцерны может расти люцерна. На квадрате, до которого достают оба типа разбрызгивателей (или ни одного типа разбрызгивателей) не может расти ничего.

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

Некоторые квадраты уже занят коровами, это не запрещает квадрату быть фертильным, но в них не могут быть установлены разбрызгиватели.

\(N\) коров (\(1\le N\le 7500\)) фермера Джона стоят в ряд. \(i\)-ая слева корова имеет метку \(i\) для всех \(1\le i\le N\). ФД говорит им повторять следующий шаг до тех по пока коровы не вернутся в исходное положение.

• По заданной перестановке \(A\) длины \(N\), коровы изменяют свой порядок \(i\)-ая корова слева до изменений становится \(A_i\)-ой коровой слева после изменения.

Например, если \(A=(1,2,3,4,5)\) тогда коровы выполнят один шаг и сразу вернутся в исходное положение. If \(A=(2,3,1,5,4)\), то коровы выполнят 6 шагов прежде чем вернутся в исходное положение. Порядок коров слева направо после каждого шага будет таким:

• 0 шаг: \((1,2,3,4,5)\)
• 1 шаг: \((3,1,2,5,4)\)
• 2 шаг: \((2,3,1,4,5)\)
• 3 шаг: \((1,2,3,5,4)\)
• 4 шаг: \((3,1,2,4,5)\)
• 5 шаг: \((2,3,1,5,4)\)
• 6 шаг: \((1,2,3,4,5)\)

Вычислите произведение количеств шагов, которые требуются для всех возможных \(N!\) перестановок \(A\) длины \(N\).

Поскольку этот ответ может быть очень большим, выведите ответ по модулю \(M\) (\(10^8\le M\le 10^9+7\), \(M\) - простое).

Контестанты, использующие C++, могут найти полезным следующий код KACTL Известный как Barrett reduction, он позволяет Вам вычислить \(a \% b\) в несколько раз быстрее, чем обычно. где \(b>1\) постоянная величина, но не известная во время компиляции. (К несчастью, мы не позаботились о такой оптимизации для Java).

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __uint128t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod F(2);

int main() {
	int M = 1000000007; F = FastMod(M);
	ull x = 10ULL*M+3; 
	cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}

\(N\) коров (\(1\le N\le 10^4\)) стоят в ряд. \(i\)-ая корова слева имеет метку \(i\) для каждого \(1\le i\le N\). ФД говорит коровам повторять следующие действия до тех пор, пока коровы не вернуться к тому же порядку, с которого начинали:

• По заданной перестановке \(A\) длины \(N\), коровы изменяют их порядок так, что \(i\)-ая корова слева до изменения становится \(A_i\) коровой слева после изменения

Например, если \(A=(1,2,3,4,5)\) тогда коровы выполнят один шаг. Если \(A=(2,3,1,5,4)\), тогда коровы выполнят 6 шагов. Порядок коров слева направо после каждого из шагов будет таким:

• 0 шаг: \((1,2,3,4,5)\)
• 1 шаг: \((3,1,2,5,4)\)
• 2 шаг: \((2,3,1,4,5)\)
• 3 шаг: \((1,2,3,5,4)\)
• 4 шаг: \((3,1,2,4,5)\)
• 5 шаг: \((2,3,1,5,4)\)
• 6 шаг: \((1,2,3,4,5)\)

Определите сумму всех положительных целых чисел \(K\) таких, что существует перестановка длины \(N\), которая требует от коров выполнить ровно \(K\) шагов.

Поскольку это число может быть очень большим, выведите ответ по модулю \(M\) (\(10^8\le M\le 10^9+7\), \(M\) - простое).

Рассмотрим последовательность \(A_1,A_2,\ldots,A_N\) длины \(N\) \((1\le N\le 5\cdot 10^4)\), состоящую только из целых чисел в диапазоне \(1\ldots K\) \((1\le K\le 20).\) Вам даны \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов вида \([L_i,R_i]\) \((1\le L_i\le R_i\le N).\) Для каждого запроса вычислите количество неубывающих подпоследовательностей \(A_{L_i},A_{L_i+1}\ldots, A_{R_i}\) по модулю \(10^9+7\).

Неубывающая подпоследовательность of \(A_L,\ldots,A_R\) есть коллекция индексов \((j_1,j_2,\ldots, j_x)\) таких что \(L\le j_1<j_2<\cdots<j_x\le R\) и \(A_{j_1}\le A_{j_2}\le \cdots \le A_{j_x}.\) Не забудьте рассмотреть пустую последовательность!

Предположим, что квадрат \(a\) заполнен водой. Тогда если существует путь из квадрата \(a\) в квадрат \(b\) используя только пустые квадраты и квадраты с водой которые не выше чем \(a\), такой что каждые два соседних квадрата имеют общую сторону, тогда квадрат \(b\) тоже заполнен водой.

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

Перемещение между двумя городами по дороге занимает один день. Во время путешествия приходиться тратиться. Чтобы путешествовать \(T\) дней требуется потратить \(C\cdot T^2\) денег, где (\(1\le C\le 1000\)).

Какое максимальное количество денег Беси может заработать в одном путешествии? Заметим, что для Беси может оказаться оптимальным не посещать никакой город кроме первого и в этом случае ответ будет 0.

Чтобы проверить алгоритм ФД, Беси подготовила массив \(A\) из \(N\) целых чисел (\(1 \leq N \leq 5000\)). Беси также спросит \(Q\) раз (\(1 \leq Q \leq 10^5\)), пару индексов \(1 \leq a_i \leq b_i \leq N\). Для каждого такого вопроса ФД должен решить проблему 3SUM на подмассиве \(A[a_i \dots b_i]\).

ФД просит Вас пройти тест Беси.

Определите объединение множества отрезков, то есть такое множество все \(x\) которые содержатся как минимум в одном отрезке. Определите сложность множества отрезков как количество связных регионов, представленных в этом объединении, возведённую в степень \(K\) (\(2\le K\le 10\)).

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

Помогите Беси!

Инопланетяне отпустят Беси, если она сможет выполнить странное задание. Сначала они выбирают две комнаты, \(s\) и \(t\) \((1 \le s, t \le N)\), и два числа \(b_s\) и \(b_t\) \((1 \le b_s, b_t \le K)\). Они помещают Беси в комнату \(s\) и сразу нажимают клавишу \(b_s\). Затем Беси продолжает навигацию по кораблю, нажимая клавиши на пульте. Имеется несколько правил, которым Беси должна следовать:

• В каждой комнате после нажатия ровно одной клавиши, она должна выбрать или выйти через дверь в другую комнату (возможно ту же самую) или остановиться.
• Когда Беси нажимает клавишу, она больше не может нажать ту же клавишу опять, пока не нажмёт клавишу с бОльшим номером. Другими словами, нажатие клавиши с номером \(x\) делает эту клавишу недоступной для использования, пока все клавиши с номерами \(<x\) будут сброшены и опять доступны для использования.
• Если Беси нажмёт неверно клавишу, она останется у инопланетян.

Беси догадалась, что только если она остановится в комнате \(t\), последняя клавиша, которую она нажала, была \(b_t\) и она не нажала неверных клавиш.

Беси беспокоится, что не сможет выполнить задание. Для \(Q\) \((1\le Q\le 60)\) запросов, каждый из которых состоит из выбора Беси \(s, t, b_s\), \(b_t\), Беси хочет узнать количество последовательностей комнат и нажатых клавиш, которые приведут к её освобождению. Выведите свой ответ по модулю \(10^9 + 7\).

Каждую ночь коровы ищут амбар для ночевки. Корова \(i\) может спать в амбаре \(j\) если и только если, она помещается в амбар, то есть (\(s_i\le t_j\)). В каждом амбаре может ночевать только одна корова.

Мы говорим, что соответствие коров амбарам максимально если и только если корова, назначенная амбару, помещается в него, и каждая из не назначенных коров не помещается ни в один из оставшихся свободными амбаров.

Вычислите количество максимальных соответствий по модулю \(10^9 + 7\).

Обычно Беси наблюдает как едет поезд, отслеживая метки вагонов. Однако сегодня туман, и Беси не видит метки. К счастью, она приобрела скользящее окно минимумов последовательности меток. В частности, у неё есть положительное целое число \(K\), и \(N-K+1\) положительных целых чисел \(c_1,\dots,c_{N+1-K}\), где \(c_i\) - минимальная метка среди вагонов \(i, i+1, \dots, i+K-1\).

Помогите Беси вычислить количество способов назначить метку каждому вагону соответствующую показаниям "скользящего окна минимумов". Поскольку это число может быть очень большим, выведите ответ по модулю \(10^9 + 7\).

Гарантируется, что существует, как минимум, один способ так назначить метки.

Беси знает \(N\) (\(1 \leq N \leq 5000\)) слов и хочет организовать их в поэму. Она определила длину в слогах каждого слова, кроме того она распределила их в "классы рифм". Каждое слово рифмуется только с другими словами из этого же класса рифм.

Каждая из поэм Беси включает \(M\) строк (\(1 \leq M \leq 10^5\)) и каждая строка должна состоять из \(K\) (\(1 \leq K \leq 5000\)) слогов. Более того, поэм Беси должна соответствовать специфической схеме рифм.

Беси хочет узнать, сколько различных поэм она может написать, которые удовлетворяют указанным ограничениям.

Они решили скосить как можно больше травы. Травяное пастбище представляет из себя квадрат \(T \times T\). Левый нижний угол квадрата имеет координаты \((0,0)\), а правый верхний угол имеет координаты \((T,T)\). Поэтому квадрат содержит \((T+1)^2\) точек решётки. (точки с целочисленными координатами).

Элла и Белла обе планируют начать в точке \((0,0)\) и двигаться с постоянной единичной скоростью в точку \((T, T)\), каждая держит в руках очень острую проволоку. Трава в области, которую прошла эта проволока, будет срезана. Елла и Белла имеют разные пути, но они состоят из шагов вверх и вправо, от одной точки решётки к другой точке решётки.

Бесси беспокоится, что будет скошено слишком много травы, поэтому она придумала хитроумный план ограничить пути Эллы и Беллы. Имеется \(N\) вкуснейших цветков, \((1 \leq N \leq 2 \cdot 10^5\)) разбросанных по пастбищу, каждый размещён в различной точке решётки. Беси выбрала множество из \(S\) цветков, и потребовала от Беллы и Эллы, чтобы они обязательно посетили точки цветков. То есть, путь Эллы должен пройти через эти \(S\) точек, также как и путь Беллы. Бесси выбрала \(S\) как максимально возможное среди всех подмножеств цветков, которое можно посетить на пути из \((0,0)\) в \((T,T)\), двигаясь только вверх или вправо.

Элла и Белла стараются максимизировать количество травы, которую они выкосят, посетив указанные \(S\) цветков. Помогите Беси выбрать \(S\) таким, чтобы количество выкошенной травы было минимально возможным.

Чтобы сгенерировать это BST, ФД начинает с перестановки \(a=\{a_1,a_2,\ldots,a_N\}\) целых чисел \(1\ldots N\), где \(N\le 300\). Затем он выполняет следующий псевдокод с аргументами \(1\) and \(N\).

generate(l,r):
  if l > r, return empty subtree;
  x = argminl <= i <= r ai; // index of min ai in {al,...,ar}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

Например, перестановка \(\{3,2,5,1,4\}\) сгенерирует такое BST

    4
   / \
  2   5
 / \ 
1   3

Пусть \(d_i(a)\) обозначает глубину вершины \(i\) в дереве, соотвествующем \(a\), то есть количество вершин на пути из \(a_i\) к корню. В примере выше, \(d_4(a)=1, d_2(a)=d_5(a)=2,\) and \(d_1(a)=d_3(a)=3\).

Количество инверсий \(a\) равно количеству пар целых чисел \((i,j)\), таких что \(1\le i<j\le N\) и \(a_i>a_j\). Коровы знают, что \(a\), которую ФД использовал для генерации BST, имеет ровно \(K\) инверсий \((0\le K\le \frac{N(N-1)}{2})\). Среди всех перестановок \(a\), удовлетворяющих этому условию, вычислите Остаток, когда \(\sum_ad_i(a)\) поделено на \(M\) для каждого \(1\le i\le N\).

ФД может выбрать последовательность коров \(c_1,c_2,\ldots, c_K,\) после чего выбранные коровы будут кушать по очереди в указанном порядке. К несчастью, коровы не умеют делиться. Когда настаёт очередь кушать коровы \(c_i\), она съедает все куски, которыми она наслаждается, то есть все оставшиеся куски в интервале \([l_{c_i},r_{c_i}]\). ФД хочет избежать неловкой ситуации, когда наступает очередь кушать коровы, но все куски, которыми она наслаждается, уже съедены. Поэтому он хочет вычислить наибольший возможный суммарный вес (\(w_{c_1}+w_{c_2}+\ldots+w_{c_K}\)) последовательности \(c_1,c_2,\ldots, c_K\) для которой каждая корова съест хотя бы один кусок.

Игра использует \(M\) клавиш, помеченных первыми \(M\) маленькими латинскими буквами (\(1 \leq M \leq 26\)). Любимая комбинация ходов Беси в этой игре это строка \(S\) длиной \(N\) (\(1 \leq N \leq 10^5\)), описывающая нажатые клавиши. Однако в связи с обновлением игры каждая комбинация теперь должна состоять из серий "полос", где "полоса" определяется как серия нажатий одной и той же клавиши не менее \(K\) раз подряд (\(1 \leq K \leq N\)). Беси хочет модифицировать её любимую комбинацию такой же длины \(N\), на сделанную из полос клавиш, удовлетворяющих введённым правилам.

\(a_{ij}\) дней требуется Беси, чтобы научиться нажимать клавишу \(j\) вместо клавиши \(i\) в любом месте её комбинации (то есть это стоит \(a_{ij}\) - изменить один символ в строке \(S\) c \(i\) на \(j\)). Заметим, что может так оказаться, что выгоднее (меньше дней) переключиться на использование с \(i\) на промежуточную клавишу \(k\) и затем с \(k\) на \(j\), чем непосредственно переключаться с \(i\) на \(j\) (или, обобщая, может быть путь изменений, начинающийся с \(i\) и заканчивающийся в \(j\), который обеспечивает более выгодную стоимость (меньшее количество дней), чем непосредственное переключение с клавиши \(i\) на клавишу \(j\)).

Помогите Беси определить минимально возможное количество дней, которое требуется ей, чтобы создать комбинацию, удовлетворяющую новым ограничениям.

Сразу по прибытии ФД был удивлён новыми правилами соревнования:

(i) Должна участвовать группа коров весом не менее \(W\)

(ii) Группа с наибольшим коэффициентом отношения таланта к весу побеждает.

ФД заметил, что все его коровы вместе весят не менее \(W\), поэтому он легко удовлетворит условие (i). Помогите ему определить наивысший коэффициент отношения таланта к весу для любой из его команд.