Vitebsk Open 2025, день 1
Statement is not available in English language
1. Задача A. Начало
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вещи собраны, такси вызвано, и вот Александр уже на вокзале в ожидании своих друзей. Совсем скоро они поедут в Могилев на свою последнюю респу. Подходя к своему поезду, они проходили мимо других поездов, на каждом из которых был свой номер. И вдруг с Александром решил поспорить его так себе друг Егор. Егор сказал, что Александр не сможет из номера поезда вычислить абсолютный номер.

Номер поезда представляет из себя массив натуральных чисел $$$a$$$ размера $$$n$$$.

Абсолютный номер поезда — это количество подпоследовательностей по модулю $$$10^9+7$$$, которые являются перестановками.

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

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка теста содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Затем следуют описания наборов.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$)  — длина массива, который представляет номер поезда соответственно.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), разделенных пробелами — номер поезда.

Пусть $$$S$$$ — это сумма $$$n$$$ по всем наборам входных данных.

Тогда гарантируется, что $$$S$$$ не превосходит $$$2\cdot10^6$$$.

Выходные данные

Для каждого набора входных данных выведите абсолютный номер поезда.

Система оценки
№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$S \le 18$$$$$$7$$$
$$$2$$$$$$a_i \leq a_{i+1}-1$$$$$$11$$$
$$$3$$$$$$a_i \neq a_j$$$ для $$$i \neq j$$$$$$4$$$$$$2$$$
$$$4$$$$$$a_i \le 10$$$$$$18$$$
$$$5$$$$$$S \le 5000$$$$$$8$$$$$$1$$$
$$$6$$$Нет дополнительных ограничений$$$52$$$$$$1$$$ — $$$5$$$
Пример
Входные данные
2
3
1 2 1
3
1 2 3
Выходные данные
4
3
Примечание

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

Перестановка — это последовательность длины $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, в которой все числа встречаются ровно по одному разу. Например, $$$[1]$$$, $$$[4, 3, 5, 1, 2]$$$, $$$[3, 2, 1]$$$ — перестановки, а $$$[1, 1]$$$, $$$[4, 3, 1]$$$, $$$[2, 3, 4]$$$ — нет.

Statement is not available in English language
2. Задача B. Ванные процедуры
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Оставалась одна ночь до первого тура респы. Михаил немного нервничал, ведь боялся, что не войдет в топ $$$3$$$ респы, поэтому он решил принять душ перед сном. Придя в ванну, он увидел, что на каждой плитке одной из стен было написано какое-то целое число. Посчитав, что граффити это не самое худшее в этом общежитии, Михаил спокойно пошел мыться.

Выйдя из душа, Михаил дернул ручку двери, но она не открывалась. Походя туда-сюда, наш герой зацепился ушами за лампочку на проводе, откуда выпала записка и маркер. На записке было написано, что он должен написать на каждой плитке пола какое-то целое число по особому правилу — и дверь откроется.

Стену можно представить в виде таблицы $$$a$$$ из $$$n$$$ строк и $$$m$$$ столбцов. Плитку стены — как ячейку в $$$i$$$-й строке и $$$j$$$-м столбце, а целое число на плитке — как $$$a_{i, j}$$$.

Аналогично, пол можно представить в виде таблицы $$$b$$$ из $$$n+2$$$ строк и $$$m+2$$$ столбцов.

Особое правило гласило, что Михаил должен в каждую ячейку $$$b_{i, j}$$$ записать целое число, чтобы выполнялось: $$$a_{i, j} =$$$ $$$b_{i+1, j+1}$$$ $$$xor$$$ $$$b_{i, j+1}$$$ $$$xor$$$ $$$b_{i+1, j}$$$ $$$xor$$$ $$$b_{i+2, j+1}$$$ $$$xor$$$ $$$b_{i+1, j+2}$$$ — для $$$1 \le i \le n$$$ и $$$1 \le j \le m$$$. В данном случае $$$xor$$$ — обозначает операцию побитового исключающего ИЛИ.

Помогите Михаилу найти такую таблицу $$$b$$$, иначе он нормально не выспится и плохо напишет первый тур.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^3$$$) — количество строк и столбцов в таблице $$$a$$$.

В следующих $$$n$$$ строках заданы ячейки в соответствующей строке $$$a_{i, 1}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 2^{30}-1$$$).

Выходные данные

Выведите таблицу $$$b$$$ из $$$n+2$$$ строк и $$$m+2$$$ столбцов, для которой выполняется особое правило.

То есть, в первых $$$n+2$$$ строках выведите ячейки в соответствующей строке $$$b_{i, 1}, \dots, b_{i, m}$$$ ($$$0 \le b_{i, j} \le 2^{30}-1$$$).

Система оценки
№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$(n+2)\cdot(m+2) \le 18$$$$$$7$$$
$$$2$$$$$$n = 1$$$$$$16$$$
$$$3$$$Все $$$a_{i, j}$$$ равны$$$12$$$
$$$4$$$$$$a_{i, j} \le 1$$$$$$17$$$
$$$5$$$$$$n, m \le 10^3$$$$$$21$$$$$$1, 2$$$
$$$6$$$Нет дополнительных ограничений$$$27$$$$$$1$$$ — $$$5$$$
Пример
Входные данные
2 2
2 0
4 3
Выходные данные
0 0 0 0 
2 0 0 0 
4 0 0 3 
0 0 0 0 

Statement is not available in English language
3. Задача C. НОДовый двигатель
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Роман очень любит спать и опаздывать. Из-за таких качеств он проснулся только в $$$9$$$:$$$42$$$. Понимая, что он явно немного опаздывает и все уже уехали без него, он решил вызвать такси.

Выйдя из общежития, Роман увидел таксиста, который уже заждался его. И вот они уже собирались поехать, но машина не заводилась. К счастью, Роман разбирается в машинах и сразу понял, что кто-то слил все топливо из бака.

Но оказалось, что у машины был НОДовый двигатель, представляющий из себя массив натуральных чисел $$$a$$$ размером $$$n$$$. А его топливом были верные ответы на $$$q$$$ запросов вида:

  • $$$\; l \; r \; k$$$ — найти НОД всех $$$a_i$$$ ($$$l \le i \le r$$$), которые нацело делятся на $$$k$$$. Если нет таких $$$a_i$$$, которые делятся нацело на $$$k$$$, то ответом на запрос будет $$$0$$$.
Надо как можно быстрее ответить на все запросы, иначе Роман не успеет на тур.
Входные данные

В первой строке заданы два целых положительных числа $$$n$$$ и $$$q$$$ ($$$1 \leq n,q \leq 5 \cdot 10^5$$$).

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^5$$$), разделенных пробелами — описание массива $$$a$$$.

Последние $$$q$$$ строк содержат три целых числа $$$l, r$$$ и $$$k$$$ ($$$1 \leq l \le r \leq n$$$, $$$1 \le k \le 5 \cdot 10^5$$$) — описание запросов.

Выходные данные

Для каждого запроса выведите в отдельной строке ответ на него.

Система оценки
№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$n, q \le 10^3$$$$$$3$$$
$$$2$$$$$$a_i \le 10$$$$$$8$$$
$$$3$$$Все $$$k_i$$$ равны$$$11$$$
$$$4$$$Все $$$a_i$$$ различны$$$12$$$
$$$5$$$Все $$$k_i$$$ различны$$$16$$$
$$$6$$$$$$l_i = 1$$$$$$9$$$
$$$7$$$$$$n, a_i \le 3 \cdot 10^4$$$$$$20$$$
$$$8$$$Нет дополнительных ограничений$$$21$$$$$$1$$$ — $$$7$$$
Пример
Входные данные
5 3
2 4 3 16 8
3 5 4
1 5 2
1 3 1
Выходные данные
8
2
1

Statement is not available in English language
4. Задача D. Настолка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Нашим друзьям стало скучно ждать второго тура, и они решили порыскать по шкафчикам, которые находились в комнате. В одном из шкафчиков Максим нашел бордово-белую коробку, на которой было написано "BOBR".

Это оказалась настольная игра. Игра проходила на карте, которая представляла собой связный граф без циклов из $$$n$$$ вершин и $$$n-1$$$ ребер, то есть представляло дерево с корнем в вершине $$$1$$$. На каждой вершине $$$i$$$ изначально записано целое неотрицательное число $$$a_i$$$.

Пусть $$$pr_{v, 0}$$$ — сама вершина $$$v$$$, $$$pr_{v, 1}$$$ — прямой предок вершины $$$v$$$, тогда $$$pr_{v, k}$$$ — $$$k$$$-ый предок вершины $$$v$$$.

Не вникая сильно в правила игры, игрок может делать $$$2$$$ типа операций с этим деревом:

  • $$$\; ? \; v$$$ — вывести значение в $$$v$$$-ой вершине.
  • $$$\; + \; v\; k\; x$$$ — прибавить $$$x$$$ к значениям вершин $$$pr_{v, 0}$$$, $$$pr_{v, k}$$$, $$$pr_{v, 2 \cdot k}$$$ и т.д. .

Поскольку друзья устали после первого тура, выполните за них $$$q$$$ операций.

Входные данные

Первая строка содержит два целых числа $$$n$$$, $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^5$$$) — количество вершин в дереве и количество операций соответственно.

Каждая из следующих $$$n-1$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$, обозначающие две вершины, соединённые ребром ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$). Гарантируется, что данные рёбра образуют дерево.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$0 \leq a_i \leq 5 \cdot 10^3$$$), разделенных пробелами — описание изначальных значений вершин.

Далее следуют $$$q$$$ строк, задающих запросы. Каждая строка задается одним из следующих форматов:

  • $$$\; ? \; v$$$ — обозначает, что очередной запрос первого типа — ($$$1 \le v \le n$$$).
  • $$$\; + \; v\; k\; x$$$ — обозначает, что очередной запрос второго типа — ($$$1 \le v \le n$$$, $$$1 \le k \le n$$$, $$$0 \le x \le 5 \cdot 10^3$$$).
Выходные данные

На каждый запрос второго типа выведите одно целое число — значение в вершине $$$v$$$.

Система оценки
№Дополнительные ограниченияБаллы за подзадачуНеобходимые подзадачи
$$$1$$$$$$n, q \le 10^3$$$$$$4$$$
$$$2$$$$$$u_i = i, v_i = i+1$$$$$$22$$$
$$$3$$$$$$k = 1$$$$$$10$$$
$$$4$$$Все запросы $$$1$$$ типа идут после запросов $$$2$$$$$$24$$$
$$$5$$$$$$n \le 10^5$$$$$$11$$$$$$1$$$
$$$6$$$Нет дополнительных ограничений$$$29$$$$$$1$$$ — $$$5$$$
Пример
Входные данные
5 5
1 2
2 3
3 4
1 5
1 2 4 8 11
+ 3 2 5
? 1
? 2
+ 5 1 7
? 1
Выходные данные
6
2
13