InfOpen 2025 2026 Финал Первый день Задача С Задача Toyota. Задачи от Саши примеры

В этом видео мы разбираем задачу про многоэтажный дом и распределение задач между жильцами. Нужно посчитать количество способов позвать жильцов на решение задач с учётом ограничений на этажи и предпочтения жильцов не подниматься по лестницам. Задача сводится к подсчёту числа допустимых назначений с помощью динамического программирования по дереву. Условие задачи Саша написал пересказ в многоэтажный дом. Всего в доме есть n этажей, пронумерованных числами от 1 до n. На каждом этаже дома живёт ровно один жилец. Между этажами есть лестница, то есть жильцы на этажах i и i+1 являются соседями. Изначально для каждого жильца, кроме первого, есть ровно одна лестница, ведущая на более низкий этаж. Для каждого жильца, кроме последнего, есть ровно одна лестница, ведущая на более высокий этаж. Жильцы могут ходить друг к другу в гости, но не могут проходить через этажи, которые не являются их соседями. Саша собирается выбрать k задач, пронумерованных от 1 до k. Для каждой задачи с номером i Саша выбирает, что оптимальнее его решать на этаже с номером x_i. Так как задачи отличаются между собой, то все значения x_i различны. Решать задачу одномоментно, поэтому для каждой задачи Саша хочет найти хотя бы одного жильца, чтобы решать её вместе. Однако жильцы дома очень ленивые и не любят подниматься по лестницам, поэтому они согласны решать задачу только на том этаже, на котором живут, или на этаже, который находится в гостях у другого жильца. Поэтому Саша может позвать жильца с этажа y решать задачу i только если y = x_i или y является соседом x_i (то есть y = x_i - 1 или y = x_i + 1). Также образуется, жилец с этажа y может решать задачу i только если y = x_i или y = x_i - 1 или y = x_i + 1. Жильцы очень не любят лишний раз спускаться по лестнице. Поэтому если Саша может позвать несколько жильцов решать задачу, она будет готовить решать задачу только на самом высоком этаже, то есть который он может спуститься. Например, если есть задача с этажом 3, то Саша может позвать жильцов с этажами 3 и 2 решать задачу на этаже 3, так как это самый высокий этаж, на который они могут спуститься. Саша не любит оставлять нерешёнными задачи, поэтому с каждого жильца Саша может позвать решать задачу не более одного раза. При этом с некоторого этажа Саша может позвать решать задачу только одного жильца. У Саши есть одна любимая задача, которую он не оставляет нерешённой ни на один день, и он хочет посчитать, каким образом она может быть решена. Но если у Саши есть несколько любимых задач, то он хочет посчитать количество различных способов позвать жильцов на решение задач, чтобы все задачи были решены. Два способа считаются различными, если хотя бы одна задача решается разными жильцами. Формат входных данных Первая строка содержит два целых числа n и k (n не меньше 1 и не больше 10^6, k не меньше 1 и не больше min(n, 2000)) — количество этажей и количество задач. Вторая строка содержит k целых чисел x_1, x_2, ..., x_k (каждое x_i не меньше 1 и не больше n) — этажи, на которых Саша будет решать задачи. Гарантируется, что все x_i различны. Третья строка содержит n - 1 целое число p_2, p_3, ..., p_n (каждое p_i не меньше 1 и меньше i), где p_i описывает номер этажа, на который ведёт лестница с i-го этажа. Формат выходных данных Выведите одно число — количество различных способов позвать жильцов дома решать задачи вместе с Сашей по модулю 998244353. Примеры Пример 1 Ввод: 3 1 1 1 1 Вывод: 5 Пример 2 Ввод: 6 2 2 5 1 2 3 4 5 Вывод: 12 Пример 3 Ввод: 7 3 2 7 1 1 2 2 3 3 Вывод: 62 Пояснение В первом примере у Саши есть пять способов позвать решать задачи жильцов дома: только с жильцом на этаже 1; с жильцами на этажах 1 и 2; с жильцами на этажах 1 и 3; с жильцами на этажах 1, 2 и 3; с жильцами на этажах 2 и 3. Позвать решать задачу только жильца с этажа 2 Саша не может, так как тогда самым высоким этажом, на котором смогут собраться все жильцы, желающие решать задачу, будет этаж 2, а Саша хочет решать задачу на этаже 1. Во втором примере двумя различными подходящими способами позвать жильцов решать задачи могут быть следующие: Позвать жильцов с этажей 2 и 6 решать первую задачу, а жильца с этажа 5 решать вторую задачу. Позвать жильцов с этажа 2 решать первую задачу, а жильцов с этажей 5 и 6 решать вторую задачу.