Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Динамическое программирование на графах

Условие задачи  
ID 38135: Схемы маршрутизации
Схемы маршрутизации
Темы: Динамическое программирование на графах    Деревья   

Рассмотрим сеть из N (2≤N≤100) вершин, помеченных 1…N. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме K которые удовлетворяют свойству i>j (0≤K≤2). Нет циклов (ребер вида i→i).

Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин

s=v0→v1→v2→?→ve=r
такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 109+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.

Каждый ввод содержит T (1≤T≤20) тестов, которые требуется решать независимо. Гарантируется, что сумма N2 всех тестов не превысит 2⋅104.


Входные данные: 
Первая строка содержит T, количество тестов.
Первая строка каждого теста содержит целые числа N и K. Заметим, что S не определяется явно во вводе.

Вторая строка каждого теста содержит строку длины N. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина - получатель, . - если i-ая вершина - ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.

Каждая из N последующих строк теста содержит битовую строку из N нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно K единиц ниже главной диагонали.

Последовательные тесты разделены пустыми строками для читабельности.

Выходные данные: 
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
 
Примеры
Входные данные Выходные данные Пояснение
1 2

8 0
SS....RR
00100000
00100000
00011000
00000100
00000100
00000011
00000000
00000000

13 0
SSS.RRRSS.RR.
0001000000000
0001000000000
0001000000000
0000111000000
0000000000000
0000000000000
0000000000000
0000000001000
0000000001000
0000000000110
0000000000000
0000000000000
0000000000000
4
12
Для первого теста ребра таковы 1→3,2→3,3→4,3→5,4→6,5→6,6→7,6→8.

Имеется четыре схемы маршрутизации:

1→3→4→6→7,2→3→5→6→8
1→3→5→6→7,2→3→4→6→8
1→3→4→6→8,2→3→5→6→7
1→3→5→6→8,2→3→4→6→7
Для второго теста 1→4,2→4,3→4,4→5,4→6,4→7,8→10,9→10,10→11,10→12.

Одна из возможных схем маршрутизации:

1→4→5
2→4→7
3→4→6
8→10→12
9→10→11
В общем случае посылатели {1,2,3} могут маршрутизироваться некоторой перестановкой получателей {5,6,7}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6 ⋅ 2=12.
 
2 2

5 1
SS.RR
00101
00100
10010
00000
00000

6 2
S....R
001000
000100
010001
000010
001000
000000
3
1
Для первого теста, ребра 1→3,1→5,2→3,3→1,3→4.

имеется три схемы маршрутизации:

1→3→1→5, 2→3→4
1→3→4, 2→3→1→5
1→5, 2→3→1→3→4
Для второго теста 1→3,2→4,3→2,3→6,4→5,5→3.

Имеется только одна схема мартшрутизации: 1→3→2→4→5→3→6.
3 5

3 2
RS.
010
101
100

4 2
.R.S
0100
0010
1000
0100

4 2
.SR.
0000
0011
0100
0010

5 2
.SSRR
01000
10101
01010
00000
00000

6 2
SS..RR
001010
000010
000010
000010
100101
000000
2
1
2
6
24