USACO 2021 US Open, Platinum
Problem 2. Routing Schemes
Contest has ended.
Log in to allow submissions in analysis mode
The connections between the nodes in this network can be described by a list of directed edges each of the form $i\to j$, meaning that node $i$ may route to node $j$. Interestingly, all of these edges satisfy the property that $i<j$, aside from $K$ that satisfy $i>j$ ($0\le K\le 2$). There are no self-loops (edges of the form $i\to i$).
The description of a "routing scheme" consists of a set of $S$ directed paths from senders to receivers such that no two of these paths share an endpoint. That is, the paths connect distinct senders to distinct receivers. A path from a sender $s$ to a receiver $r$ can be described as a sequence of nodes
Count the number of distinct routing schemes such that every directed edge is traversed exactly once. Since the answer may be very large, report it modulo $10^9+7$. It is guaranteed that there is at least one routing scheme satisfying these constraints.
Each input contains $T$ ($1\le T\le 20$) test cases that should be solved independently. It is guaranteed that the sum of $N^2$ over all test cases does not exceed $2\cdot 10^4$.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of the input contains $T$, the number of test cases.The first line of each test case contains the integers $N$ and $K$. Note that $S$ is not explicitly given within the input.
The second line of each test case contains a string of length $N$. The $i$-th character of the string is equal to S if the $i$-th node is a sender, R if the $i$-th node is a receiver, or . if the $i$-th node is neither. The number of Rs in this string is equal to the number of Ss, and there is at least one S.
The next $N$ lines of each test case each contain a bit string of $N$ zeros and ones. The $j$-th bit of the $i$-th line is equal to $1$ if there exists a directed edge from node $i$ to node $j$, and $0$ otherwise. As there are no self-loops, the main diagonal of the matrix consists solely of zeros. Furthermore, there are exactly $K$ ones below the main diagonal.
Consecutive test cases are separated by newlines for readability.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, the number of routing schemes such that every edge is traversed exactly once, modulo $10^9+7$. It is guaranteed that there is at least one valid routing scheme for each test case.SAMPLE INPUT:
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
SAMPLE OUTPUT:
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$.
SAMPLE INPUT:
2 5 1 SS.RR 00101 00100 10010 00000 00000 6 2 S....R 001000 000100 010001 000010 001000 000000
SAMPLE OUTPUT:
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$.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
2 1 2 6 24
Some additional small test cases.
SCORING:
- Test cases 4-5 satisfy $N\le 6$.
- Test cases 6-7 satisfy $K=0$.
- Test cases 8-12 satisfy $K=1$.
- Test cases 13-24 satisfy $K=2$.
Problem credits: Benjamin Qi