Московская олимпиада школьников 10-11 2025
6 апр 2025, 11:52:06
старт:
6 апр 2025, 10:30:22
финиш:
6 апр 2025, 14:30:22
до финиша:
02:38:14
начало:
6 апр 2025, 10:33:22
конец:
6 апр 2025, 11:00:00
длительность:
04:00:00
...

###### Оценка посылки и тестов

Вердикт ОК как при онлайн проверке теста, так и при оффлайн означает только, что формат выходных данных верный. При этом за тест может быть выставлено и 0 баллов. При онлайн проверке вы видите правильный общий балл. В зачет пойдет последний из них. При оффлаайн проверке будет проверена последняя посылка.

###### Зачет решений

Обратите внимание, что в зачет пойдет результат ПОСЛЕДНЕЙ посылки по любой задаче, даже с онлайн-проверкой. Будьте внимательны, особенно в конце тура.

# F2. Планетная система - 2

##

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».

Давным-давно в далекой галактике существовала планетная система, состоящая из n
n планет. Каждую планету этой системы можно представить как точку с целыми неотрицательными координатами в m
m-мерном пространстве, таким образом, каждая планета имеет m
m координат.

Обозначим за c i,j
c i,j​ - j
j -ю координату i
i -й планеты.

Известно, что для каждой планеты i(1≤i≤n)
i(1≤i≤n) выполнено неравенство 0≤c i,j<q j
0≤c i,j​<q j​ по всем j(1≤j≤m)
j(1≤j≤m). Иными словами, j
j-я координата любой планеты строго меньше некоторого значения q j
q j​.

Так же известно, что в системе не существует планет с совпадающими координатами.

Находясь на планете a
a, можно совершить прямой перелет на другую планету b
b, если и только если каждая координата планеты b
b не превосходит соответствующей координаты планеты a
a. Более формально, с планеты a
a можно совершить прямой перелет на планету b
b, если для всех j
j от 1 до m
m выполнено неравенство: c b,j≤c a,j
c b,j​≤c a,j​.

В системе есть k
k обитаемых планет, имеющих номера x 1,x 2,...,x k
x 1​,x 2​,...,x k​, все остальные планеты считаются необитаемыми.

Назовем последовательность планет y 1,y 2,...,y r
y 1​,y 2​,...,y r​ путем, если для каждого i(1≤i<r)
i(1≤i<r) можно напрямую перелететь с планеты y i
y i​ на планету y i+1
y i+1​. Два пути будем считать различными, если последовательности планет в них отличаются.

Император галактики просит вас для каждой планеты от 1
1 до n
n посчитать количество различных путей, начинающихся в этой планете и заканчивающихся в некоторой обитаемой планете по модулю 1 0 9+7
1 0 9+7.

## Формат ввода

В первой строке вводится число t
t - количество планетных систем, для которых нужно найти ответ.

Описание каждой планетной системы начинается с трех чисел n,m,k(1≤n≤1 0 5,1≤m≤16,0≤k≤n)
n,m,k(1≤n≤1 0 5,1≤m≤16,0≤k≤n), разделенных пробелом.

В следующей строке содержатся числа q 1,q 2,...,q m
q 1​,q 2​,...,q m​ - ограничения на координаты планет.

Гарантируется, что во всех тестах данной задачи ∏m j=1 q j≤1 0 5
∏j=1 m​q j​≤1 0 5.

Далее следуют n
n строк, описывающих координаты планет.

i
i-я из следующих n
n строк описывает координаты i
i-й планеты и содержит целые числа c i,1,c i,2,...,c i,m(0≤c i,j<q j)
c i,1​,c i,2​,...,c i,m​(0≤c i,j​<q j​)

Далее следует строка, содержащая k
k различных чисел - номера обитаемых планет x 1,x 2,...,x k(1≤x i≤n)
x 1​,x 2​,...,x k​(1≤x i​≤n).

## Формат вывода

Для каждой из t
t планетных систем для каждой планеты в системе выведите количество искомых путей по модулю 1 0 9+7
1 0 9+7.

## Система оценивания

Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).

За каждую планетную систему, для которой был найден правильный ответ, начисляется 2 балла.

Набрать здесь Отправить файл
1

    ​

Выбрать Файл не выбран
осталось 100 попыток
Посылок нет