|
Темы:
Комбинаторика
В государстве Чудаков N городов ( 2 <=N <= 16 ), обозначаемых заглавными латинскими буквами, начиная с A, по порядку. Между некоторыми из них проложены дороги, которые могут быть как односторонними, так и двусторонними, причем не обязательно, что из каждого города можно проехать в любой другой.
В государстве всего один маршрут автобуса – 'Ч', который совершает только один рейс каждый день. Выходя из некоторого города, он совершает ровно N переездов между городами так, чтобы вернуться в тот, из которого выехал. Других ограничений на его маршрут нет. В течение дня автобус может несколько раз проезжать один и тот же город или дорогу. В каждом городе существуют автобусные парки, из которых могут выезжать автобусы маршрута 'Ч'. Так что, хотя автобус каждый день возвращается в город, из которого стартовал в этот день, на следующий день начало маршрута 'Ч' может быть из любого другого города. Но рейс каждый день только один.
Маршрут обозначается N буквами, начиная с города, из которого происходит выезд. Например, BCDCE – допустимый маршрут для государства из 5 городов ссоответствующими дорогами: выехать из B, проехать в C, затем в D, вернуться в C, проехать в E и вернуться в изначальный город B (последний пункт маршрута, совпадающий с первым, в маршруте не указывается).
Маршрут автобуса меняется каждый день так, что список маршрутов по дням расположен в словарном порядке и содержит все возможные маршруты. Когда список кончается, его обход начинается сначала. В первый день введения маршрута 'Ч' автобус шёл по первому по порядку маршруту. Выведите его маршрут на день K работы маршрута. Пример: В государстве четыре города: A, B, C, D. Наличие дорог между ними задано матрицей, где элемент равен 1, если из города, соответствующего строке, в город, соответствующий столбцу, есть дорога, и 0 – иначе (на главной диагонали нули – дорог, ведущих назад в тот же город, не бывает).
| откуда/куда |
A |
B |
C |
D |
| A |
0 |
0 |
1 |
1 |
| B |
1 |
0 |
1 |
1 |
| C |
0 |
1 |
0 |
0 |
| D |
0 |
1 |
1 |
0 |
Полное расписание маршрутов в таком государстве выглядит так:
ADCB
BADC
BCBC
BCBD
BDBC
BDBD
CBAD
CBCB
CBDB
DBCB
DBDB
DCBA
Таким образом, например, маршрут на день 30 – это BDBD.
Формат входных данных
В первой строке указывается количество городов N ( 2<= N <= 16 ). Далее следует N строк по N элементов (цифр), разделенных пробелом, содержащих матрицу, задающую дороги между городами. Далее следует строка содержащая целое число D – номер дня, маршрут которого требуется определить ( 1<= D <= 264 ).
Формат выходных данных
В единственной строке указывается маршрут, т.е. порядок посещения городов, например BDBD (см. предыдущий пример).
| Ввод |
Вывод |
3
0 1 1
1 0 1
1 1 0
4 |
BCA |
| |
![]()
|
|
Темы:
Комбинаторика
Вывод формулы
Структуры данных
Для последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и целого числа \(x\) обозначим через \(f(a, x)\) количество таких целых \(i\) от \(1\) до \(n\), что \(a_i \le x\).
Для пары последовательностей целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\) обозначим через \(g(a, b, c)\) сумму значений \(|f(a, x)-f(b, x)|\) по всем целым \(x\), лежащим в отрезке \([0, c]\). Более формально, \(g(a, b, c) = \sum_{x=0}^c |f(a, x)-f(b, x)|\).
Вам даны два целых числа \(n\) и \(c\), а также две последовательности целых чисел \(a_1, a_2, \ldots, a_n\) и \(b_1, b_2, \ldots, b_n\), все элементы которых лежат в отрезке \([-1, c]\). Известно, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).
Скажем, что пара последовательностей целых чисел \(a_1', a_2', \ldots, a_n'\) и \(b_1', b_2', \ldots, b_n'\), все элементы которых лежат в отрезке \([0, c]\), соответствует шаблону \((a, b)\), если выполняются следующие условия:
-
Для всех \(i\) (\(1 \le i \le n\)), таких, что \(a_i \ne -1\), выполняется \(a_i'=a_i\).
-
Для всех \(i\) (\(1 \le i \le n\)), таких, что \(b_i \ne -1\), выполняется \(b_i'=b_i\).
-
Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(a_i' \le a_{i+1}'\).
-
Для всех \(i\) (\(1 \le i \le n-1\)) выполняется \(b_i' \le b_{i+1}'\).
Обозначим через \(h(a, b, c)\) сумму значений \(g(a', b', c)\) по всем парам последовательностей \((a', b')\), соответствующих шаблону \((a, b)\). Вы должны посчитать \(h(a, b, c)\). Также вы должны обработать \(q\) запросов изменения последовательностей \(a\) и \(b\) и посчитать \(h(a, b, c)\) после каждого изменения. Обратите внимание, что ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\), ни до всех запросов, ни после какого-либо запроса.
Формат входных данных
Первая строка содержит три целых числа \(n\), \(c\) и \(q\) (\(1 \le n \le 100\,000\), \(0 \le c \le 10^9\), \(0 \le q \le 100\,000\)) — длина последовательностей \(a\) и \(b\), ограничение на значения элементов \(a\) и \(b\) и количество запросов, соответственно.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \le a_i \le c\)) — последовательность \(a\).
Третья строка содержит \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) (\(-1 \le b_i \le c\)) — последовательность \(b\).
В следующих \(q\) строках заданы запросы изменения. Каждый запрос задается тройкой целых чисел \(t\), \(p\), \(x\) (\(1 \le t \le 2\), \(1 \le p \le n\), \(-1 \le x \le c\)). Если \(t=1\), то данный запрос меняет \(a_p\) на \(x\). Если \(t=2\), то данный запрос меняет \(b_p\) на \(x\).
Гарантируется, что до всех изменений и после каждого изменения ни в \(a\), ни в \(b\) нет двух подряд идущих элементов, равных \(-1\).
Формат выходных данных
Выведите \((q+1)\) строку. В \((i+1)\)-й строке (\(0 \le i \le q\)) выведите одно целое число — значение \(h(a, b, c)\) по модулю \(10^9+7\) после применения первых \(i\) запросов изменения.
Примечание
Рассмотрим первый тест из примера. В нем \(n=3\), \(c=4\), \(q=3\). До всех запросов \(a=[-1, 1, 3]\), \(b=[1, -1, 2]\). Шаблону \((a, b)\) соответствуют следующие пары последовательностей:
-
\(a'=[0, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=2\).
-
\(a'=[0, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=3\).
-
\(a'=[1, 1, 3], b'=[1, 1, 2]\), \(g(a, b, 4)=1\).
-
\(a'=[1, 1, 3], b'=[1, 2, 2]\), \(g(a, b, 4)=2\).
Таким образом, ответ на задачу до всех запросов равен \(h(a, b, 4)=2+3+1+2=8\).
В первом запросе \(t=1\), \(p=1\), \(x=2\). Этот запрос меняет \(a_1\) с \(-1\) на \(2\). Таким образом, после этого запроса \(a=[2, 1, 3]\), \(b=[1, -1, 2]\). В последовательности \(a\) нет \(-1\), поэтому в любой паре последовательностей \((a', b')\), соответствующей шаблону \((a, b)\), последовательность \(a'\) должна совпадать с \(a\). В последовательности \(a\) не выполняется условие \(a_1 \le a_2\), поэтому не существует ни одной пары последовательностей, соответствующей шаблону, а тогда \(h(a, b, 4)=0\) после первого запроса.
| |
![]()
|