Universal Paperclips — инкрементальная игра, целью которой является изготовление скрепок. В вашем распоряжении есть оборудование, производящее скрепки по нажатию кнопки.
В упрощенной версии игры для этой задачи будем считать, что игроку доступны два вида действий:
Изначально у игрока ноль скрепок, а каждое нажатие на кнопку добавляет одну скрепку. На каждое улучшение тратится $$$x$$$ скрепок. Во всех входных данных гарантируется, что перед каждым улучшением в наличии есть хотя бы $$$x$$$ скрепок.
Бенни решил написать бота для этой игры. Он закодировал в бота последовательность из $$$n$$$ действий $$$S$$$, которую бот выполняет по циклу. Каждую секунду бот совершает очередное действие: на 1-й секунде бот применяет $$$S_1$$$, на второй — $$$S_2$$$, ..., на $$$n$$$-й — $$$S_n$$$, на $$$n+1$$$-й — снова $$$S_1$$$, и далее по циклу.
Сколько скрепок будет у Бенни после $$$t$$$ секунд работы его бота?
В первой строке содержатся три числа $$$n$$$, $$$t$$$ и $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le t \le 10^9$$$; $$$0 \le x \lt n$$$). Во второй строке содержится строка $$$S$$$ длины $$$n$$$ из символов «C» и «U».
Выведите одно число — число скрепок через $$$t$$$ секунд.
| Подзадача | Баллы | Ограничения |
| 1 | 33 | $$$t \le 10^5$$$ |
| 2 | 67 | Без дополнительных ограничений |
10 15 2 CCCCCUUCCU
25
3 10 0 UUU
0
9 150 1 CCUCCCCUC
2023
Рассмотрим первый пример. Первые пять операций приносят по одной скрепке каждая. Следующие две операции используют по две скрепки, после чего остается одна скрепка, однако, следующие два нажатия производят по три скрепки. Далее, улучшение снова отбирает две. Последние пять нажатий приносят по 4 скрепки каждое.
Итоговое число скрепок равно $$$1 + 1 + 1 + 1 + 1 - 2 - 2 + 3 + 3 - 2 + 4 + 4 + 4 + 4 + 4 = 25$$$.
Вам дан массив целых чисел. Вы должны ровно один раз применить к этому массиву операцию сортировки подотрезка, то есть выбрать какой-то непустой подотрезок массива и переупорядочить элементы этого подотрезка в неубывающем порядке.
Сколько различных массивов вы можете получить в результате такой операции? Подотрезком массива называются несколько подряд идущих элементов массива.
Первая строка содержит число $$$n$$$ — размер массива ($$$1 \le n \le 200\,000$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ — элементы массива ($$$1 \le a_i \le 10^9$$$).
Выведите количество различных массивов, которое можно получить после применения одной операции сортировки подотрезка.
| Подзадача | Баллы | Ограничения |
| 1 | 13 | $$$n \le 50$$$ |
| 2 | 26 | $$$n \le 3\,000$$$ |
| 3 | 22 | $$$1 \le a_i \le 2$$$ |
| 4 | 39 | Без дополнительных ограничений |
7 3 1 4 1 5 9 2
8
4 1 2 3 4
1
Ниже перечислены все возможные различные массивы, которые можно получить в первом примере, и один из способов получить каждый из них. Сортируемые подотрезки отмечены квадратными скобками.
Рассмотрим последовательность целых неотрицательных чисел от $$$L$$$ до $$$R$$$ включительно. Разобьем такую последовательность на $$$n$$$ непустых отрезков и посчитаем побитовое «или» чисел в каждом отрезке. Результат для $$$i$$$-го отрезка назовем $$$f_i$$$.
Решите обратную задачу: по числам $$$f_1, f_2, \ldots, f_n$$$ найдите количество способов выбрать $$$L$$$ и $$$R$$$, а затем разбить все числа от $$$L$$$ до $$$R$$$ на $$$n$$$ непустых отрезков так, чтобы результаты вычисления побитового «или» в каждом отрезке были равны $$$f_1, f_2, \ldots, f_n$$$ соответственно.
Побитовое «или» (or) двух целых неотрицательных чисел вычисляется следующим образом: запишем оба числа в двоичной системе счисления, $$$i$$$-й двоичный разряд результата равен $$$1$$$, если у хотя бы одного из аргументов он равен $$$1$$$. Например, $$$(17 \mathbin{|} 13) = (10001_2 \mathbin{|} 01101_2) = 11101_2 = 29$$$.
В первой строке содержится число $$$n$$$ ($$$1 \le n \le 200\,000$$$). В следующей строке содержатся $$$n$$$ чисел $$$f_i$$$ ($$$0 \le f_i \lt 2^{60}$$$).
Выведите одно число — количество способов выбрать последовательность из подряд идущих чисел и разбить ее на $$$n$$$ отрезков. Поскольку ответ может быть большим, выведите его по модулю $$$1\,000\,000\,007$$$.
| Подзадача | Баллы | Ограничения | |
| 1 | 16 | $$$n = 1$$$ | |
| 2 | 12 | $$$n \le 16$$$, $$$0 \le f_i | lt; 16$$$ |
| 3 | 13 | $$$n \le 256$$$, $$$0 \le f_i | lt; 256$$$ |
| 4 | 18 | $$$n \le 1024$$$, $$$0 \le f_i | lt; 1024$$$ |
| 5 | 24 | $$$n \le 30\,000$$$, $$$0 \le f_i | lt; 2^{30}$$$ |
| 6 | 17 | Без дополнительных ограничений |
3 0 7 7
4
1 11
6
2 4 6
0
В первом примере существует четыре способа разбить массив подряд идущих чисел на три части, так, чтобы побитовые «или» в них были равны $$$0$$$, $$$7$$$ и $$$7$$$ соответственно:
Дана перестановка. За одну операцию в ней можно поменять местами два соседних элемента, значения которых отличаются больше чем на один.
Рассмотрим все перестановки, которые можно получить из данной этими операциями. Назовем расстоянием между двумя перестановки минимальное число таких операций, необходимых для того, чтобы превратить первую перестановку во вторую.
Найдите их количество, а также сумму расстояний от начальной перестановки до всех достижимых.
В первой строке содержится число $$$n$$$ ($$$1 \le n \le 100$$$) — число элементов перестановки. Вторая строка содержит $$$n$$$ различных чисел $$$a_i$$$ ($$$1 \le a_i \le n$$$) — начальную перестановку.
Выведите два числа — количество перестановок, которые можно получить, а также сумму расстояний от начальной до всех достижимых. Выведите оба числа по модулю $$$1\,000\,000\,007$$$.
| Подзадача | Баллы | Ограничения |
| 1 | 15 | $$$n \le 8$$$ |
| 2 | 20 | $$$n \le 15$$$ |
| 3 | 30 | $$$n \le 30$$$ |
| 4 | 20 | $$$n \le 50$$$ |
| 5 | 15 | Без дополнительных ограничений |
4 3 1 4 2
5 5
5 1 2 3 4 5
1 0
6 5 3 1 2 4 6
61 218
В первом примере из начальной перестановки можно получить следующие:
Всего пять перестановок, сумма расстояний до них также равна пяти.
Во втором примере никакие два элемента нельзя поменять местами, поэтому достижима только одна перестановка с расстоянием 0.