дп

Разбрызгиватель для пшеницы в квадрате \((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). Помогите ему определить наивысший коэффициент отношения таланта к весу для любой из его команд.

Чтобы использовать штамп, он должен занять ровно \(K\) соседних единиц холста. Штамп не может выходить за концы холста, и не может покрывать часть единицы. Однажды размещённый, штамп закрашивает \(K\) покрытых единиц своим цветом. Любой штамп может быть использован множество раз, один раз или даже не использован ни разу. Но к моменту завершения работы Беси, каждая единица холста должна быть закрашена как минимум один раз.

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

Как минимум в 75% тестов, \(N,K \leq 10^3\).

Количество заработанных денег зависит от того, где она спрыгнет с бревна. Бревно имеет позиции, помеченные \(0, 1, \ldots, N+1\) слева направо. Если Беси достигнет точки \(0\) или \(N+1\), она упадёт с бревна и не получит деньги.

Если Беси находится в позиции \(k\), она может сделать что-то из следующего:

1. Бросить монету. Если она увидит хвост("орёл"), она идёт в позицию \(k-1\), а если она увидит голову("решка"), она идёт в позицию \(k + 1\) (т.е с вероятностью \(\frac{1}{2}\) в обоих случаях).

2. Спрыгнуть с бревна и получить плату \(f(k)\) \((0 \leq f(k) \leq 10^9)\).

Беси поняла, что она не может гарантировать конкретный доход, поскольку её движение управляется случайным выбрасыванием монеты. Однако, основываясь на позиции, где она начинает, она хочет определить какой будет её ожидаемая выплата, если она сделает оптимальную последовательность решений ("оптимальную" означает, что решения приведут к наибольшей возможной ожидаемой выплате.) Например, её стратегия заработать выплату \(10\) с вероятностью \(1/2\), \(8\) с вероятностью \(1/4\), или \(0\) с вероятностью \(1/4\) приведёт к тому что её ожидаемая выплата будет взвешенной средней величиной \(10(1/2) + 8(1/4) + 0(1/4) = 7\).

ABCD

BXZX

CDXB

WCBA

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

Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.