Ограничение времени | 2 секунды |
Ограничение памяти | 256 Мб |
Ввод | стандартный ввод |
Вывод | стандартный вывод |
В этой задаче на проверку необходимо сдать исходный код программы.
Давным-давно в далекой галактике существовала планетная система, состоящая из планет. Каждую планету этой системы можно представить как точку с целыми неотрицательными координатами в -мерном пространстве, таким образом, каждая планета имеет координат.
Обозначим за - -ю координату -й планеты.
Известно, что для каждой планеты выполнено неравенство по всем . Иными словами, -я координата любой планеты строго меньше некоторого значения .
Так же известно, что в системе не существует планет с совпадающими координатами.
Находясь на планете , можно совершить прямой перелет на другую планету , если и только если каждая координата планеты не превосходит соответствующей координаты планеты . Более формально, с планеты можно совершить прямой перелет на планету , если для всех от 1 до выполнено неравенство: .
В системе есть обитаемых планет, имеющих номера , все остальные планеты считаются необитаемыми.
Назовем последовательность планет путем, если для каждого можно напрямую перелететь с планеты на планету . Два пути будем считать различными, если последовательности планет в них отличаются.
Император галактики просит вас для каждой планеты от до посчитать количество различных путей, начинающихся в этой планете и заканчивающихся в некоторой обитаемой планете по модулю .
В первой строке вводится число - количество планетных систем, для которых нужно найти ответ.
Описание каждой планетной системы начинается с трех чисел , разделенных пробелом.
В следующей строке содержатся числа - ограничения на координаты планет.
Гарантируется, что во всех тестах данной задачи .
Далее следуют строк, описывающих координаты планет.
-я из следующих строк описывает координаты -й планеты и содержит целые числа .
Далее следует строка, содержащая различных чисел - номера обитаемых планет .
Для каждой из планетных систем для каждой планеты в системе выведите количество искомых путей по модулю .
Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
За каждую планетную систему, для которой был найден правильный ответ, начисляется 2 балла.
В первом тесте 3 планетных системы, в каждой из них не более 20 планет.
Во втором тесте 5 планетных систем, в каждой из них не более 2000 планет.
В третьем тесте 2 планетные системы, в каждой из них .
В четвертом тесте 5 планетных систем, в каждой из них .
В пятом тесте 10 планетных систем, дополнительных ограничений нет.
Ввод | Вывод |
---|---|
2 2 2 1 2 2 0 0 0 1 2 3 2 2 2 2 0 0 0 1 1 0 1 2 | 0 1 1 2 1 |
В первой планетной системе две планеты, первая планета имеет координаты , вторая планета имеет координаты , планета 2 является единственной обитаемой планетой. Первая планета необитаема, и с нее нельзя никуда перелететь, поэтому количество путей, начинающихся в этой планете и заканчивающихся в обитаемой планете, равно . Вторая планета обитаема, поэтому путь, состоящий лишь из нее, нам подходит, в то же время путь оканчивается в необитаемой планете, следовательно, нам не подходит. Таким образом, ответ для второй планеты равен 1.
Во второй планетной системе три планеты, первая имеет координаты , вторая планета имеет координаты , третья планета имеет координаты . Планеты и являются обитаемыми. Из первой планеты перелететь никуда нельзя, но можно остаться на ней и получить путь, состоящий лишь из первой планеты, которая является обитаемой, следовательно, этот путь подходит нам. Для второй планеты существуют пути , так как планета обитаема, а так же путь, состоящий лишь из второй планеты, поэтому ответ для этой планеты . Для третьей планеты существует лишь один путь , заканчивающийся в первой планете, которая является обитаемой, следовательно, ответ для третьей планеты .