RiseOJ – 라우팅 스킴

설명

$1\ldots N$ 으로 번호가 붙은 $$N$$ ( $2\le N\le 100$ )개의 노드로 이루어진 네트워크를 생각하자. 각 노드는 송신자, 수신자, 또는 둘 다 아닌 것으로 지정된다. 송신자의 수 $$S$$ 는 수신자의 수와 같다 ( $S\ge 1$ ).

이 네트워크에서 노드 간 연결은 $i\to j$ 형태의 방향 간선들의 목록으로 나타낼 수 있으며, 이는 노드 $$i$$ 가 노드 $$j$$ 로 라우팅할 수 있음을 의미한다. 흥미롭게도, $$i>j$$ 를 만족하는 $$K$$ ( $0\le K\le 2$ )개의 간선을 제외한 모든 간선은 $$i를 만족한다. 자기 자신으로 향하는 간선(\(i\to i$ 형태)은 없다.$

"라우팅 스킴"이란 송신자에서 수신자로 향하는 $$S$$ 개의 방향 경로들의 집합으로, 어떤 두 경로도 끝점을 공유하지 않는 것을 말한다. 즉, 경로들은 서로 다른 송신자와 서로 다른 수신자를 연결한다. 송신자 $$s$$ 에서 수신자 $$r$$ 로 가는 경로는 노드들의 수열
$s=v_0\to v_1 \to v_2\to \cdots \to v_e=r$
로 나타낼 수 있으며, 모든 $$0\le i에 대해 방향 간선 \(v_i\to v_{i+1}$이 존재해야 한다. 한 노드가 같은 경로 안에서 여러 번 등장할 수 있다.$

모든 방향 간선이 정확히 한 번씩 사용되는 서로 다른 라우팅 스킴의 개수를 세시오. 답이 매우 클 수 있으므로 $$10^9+7$$ 로 나눈 나머지를 출력한다. 이 제약을 만족하는 라우팅 스킴이 적어도 하나 존재함이 보장된다.

각 입력은 독립적으로 풀어야 하는 $$T$$ ( $1\le T\le 20$ )개의 테스트 케이스를 포함한다. 모든 테스트 케이스에 대한 $$N^2$$ 의 합이 $2\cdot 10^4$ 를 넘지 않음이 보장된다.

출제자: Benjamin Qi

제약

채점 방식

테스트 케이스 4-5는 $N\le 6$ 을 만족한다.
테스트 케이스 6-7은 $$K=0$$ 을 만족한다.
테스트 케이스 8-12는 $$K=1$$ 을 만족한다.
테스트 케이스 13-24는 $$K=2$$ 를 만족한다.

출제자: Benjamin Qi

입력 형식

입력의 첫째 줄에 테스트 케이스의 수 $$T$$ 가 주어진다.

각 테스트 케이스의 첫째 줄에 정수 $$N$$ 과 $$K$$ 가 주어진다. $$S$$ 는 입력에 명시적으로 주어지지 않음에 유의한다.

각 테스트 케이스의 둘째 줄에 길이 $$N$$ 의 문자열이 주어진다. 문자열의 $$i$$ 번째 문자는 $$i$$ 번째 노드가 송신자이면 S, 수신자이면 R, 둘 다 아니면 .이다. 이 문자열에서 R의 개수는 S의 개수와 같고, S가 적어도 하나 존재한다.

각 테스트 케이스의 다음 $$N$$ 개의 줄에 각각 $$N$$ 개의 0과 1로 이루어진 비트 문자열이 주어진다. $$i$$ 번째 줄의 $$j$$ 번째 비트는 노드 $$i$$ 에서 노드 $$j$$ 로 향하는 방향 간선이 존재하면 $$1$$ , 그렇지 않으면 $$0$$ 이다. 자기 자신으로 향하는 간선이 없으므로 행렬의 주대각선은 모두 0이다. 또한 주대각선 아래에는 정확히 $$K$$ 개의 1이 있다.

연속된 테스트 케이스 사이에는 가독성을 위해 빈 줄이 있다.

출력 형식

각 테스트 케이스에 대해, 모든 간선이 정확히 한 번씩 사용되는 라우팅 스킴의 개수를 $$10^9+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

설명

For the first test case, the edges are
$1\to 3, 2\to 3, 3\to 4, 3\to 5, 4\to 6, 5\to 6, 6\to 7, 6\to 8$ .

There are four possible routing schemes:

$1\to 3\to 4\to 6\to 7, 2\to 3\to 5\to 6\to 8$
$1\to 3\to 5\to 6\to 7, 2\to 3\to 4\to 6\to 8$
$1\to 3\to 4\to 6\to 8, 2\to 3\to 5\to 6\to 7$
$1\to 3\to 5\to 6\to 8, 2\to 3\to 4\to 6\to 7$

For the second test case, the edges are
$1\to 4, 2\to 4, 3\to 4, 4\to 5,4\to 6,4\to 7, 8\to 10, 9\to 10, 10\to 11, 10\to 12$ .

One possible routing scheme consists of the following paths:

$1\to 4\to 5$
$2\to 4\to 7$
$3\to 4\to 6$
$8\to 10\to 12$
$9\to 10\to 11$

In general, senders $\{1,2,3\}$ can route to some permutation of receivers
$\{5,6,7\}$ and senders $\{8,9\}$ can route to some permutation of receivers
$\{11,12\}$ , giving an answer of $6\cdot 2=12$ .

예제 2

입력

출력

3
1

설명

For the first test case, the edges are $1\to 3, 1\to 5, 2\to 3, 3\to 1, 3\to 4$ .

There are three possible routing schemes:

$1\to 3\to 1\to 5$ , $2\to 3\to 4$
$1\to 3\to 4$ , $2\to 3\to 1\to 5$
$1\to 5$ , $2\to 3\to 1\to 3\to 4$

For the second test case, the edges are
$1\to 3, 2\to 4, 3\to 2,3\to 6, 4\to 5, 5\to 3$ .

There is only one possible routing scheme:
$1\to 3\to 2\to 4\to 5\to 3\to 6$ .

예제 3

입력

출력

설명

Some additional small test cases.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > US Open > Platinum

올림피아드 > USACO > 2020-2021 > US Open > Platinum

태그

JudgeUSACO

라우팅 스킴

평가 및 의견

풀이 제출