Routing Schemes

题目描述

考虑一个由 $N$（$2\le N\le 100$）个节点组成的网络，节点编号为 $1\ldots N$。每个节点被指定为发送者、接收者，或两者都不是。发送者数量 $S$ 等于接收者数量（$S\ge 1$）。 网络中的连接可由一组有向边表示，每条边形如 $i\to j$，表示节点 $i$ 可以路由到节点 $j$。有趣的是，除去 $K$ 条满足 $i>j$ 的边（$0\le K\le 2$）以外，其余所有边都满足 $i<j$。不存在自环（形如 $i\to i$ 的边）。 所谓“路由方案”（routing scheme）的描述，是由 $S$ 条从发送者到接收者的有向路径组成的集合，且任意两条路径不共享端点。也就是说，这些路径将不同的发送者连接到不同的接收者。从发送者 $s$ 到接收者 $r$ 的一条路径可以表示为一个节点序列

其中对所有 $0\le i<e$，都有有向边 $v_i\to v_{i+1}$ 存在。同一条路径中允许某个节点出现多次。 请计算满足“每一条有向边都恰好被遍历一次”的不同路由方案数量。由于答案可能很大，请对 $10^9+7$ 取模输出。保证至少存在一个满足这些约束的路由方案。 每个输入包含 $T$（$1\le T\le 20$）个测试用例，需独立求解。保证所有测试用例的 $N^2$ 之和不超过 $2\cdot 10^4$。

输入格式

第一行包含整数 $T$，表示测试用例数量。 每个测试用例的第一行包含整数 $N$ 和 $K$。注意：输入中不会显式给出 $S$。 每个测试用例的第二行包含一个长度为 $N$ 的字符串。若第 $i$ 个字符为 S，则第 $i$ 个节点是发送者；为 R，则是接收者；为 .，则既不是发送者也不是接收者。该字符串中 R 的数量等于 S 的数量，且至少有一个 S。 接下来 $N$ 行中，每行包含一个长度为 $N$ 的由 0 和 1 组成的二进制串。第 $i$ 行第 $j$ 位为 $1$ 表示存在从节点 $i$ 到节点 $j$ 的有向边，否则为 $0$。由于不存在自环，矩阵主对角线全为 0。 此外，在主对角线下方恰好有 $K$ 个 1。 为便于阅读，相邻测试用例之间用空行分隔。

输出格式

对每个测试用例，输出满足“每条边恰好被遍历一次”的路由方案数量，并对 $10^9+7$ 取模。保证每个测试用例至少有一个合法路由方案。

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

2

5 1
SS.RR
00101
00100
10010
00000
00000

6 2
S....R
001000
000100
010001
000010
001000
000000

3
1

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

提示

对于第一个测试用例，边为 $1\to 3, 2\to 3, 3\to 4, 3\to 5, 4\to 6, 5\to 6, 6\to 7, 6\to 8$。 共有四种可能的路由方案： $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$ 对于第二个测试用例，边为 $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$。 一种可能的路由方案由以下路径组成： $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$ 一般而言，发送者 $\{1,2,3\}$ 可以路由到接收者 $\{5,6,7\}$ 的某个排列，而发送者 $\{8,9\}$ 可以路由到接收者 $\{11,12\}$ 的某个排列，因此答案为 $6\cdot 2=12$。 对于第一个测试用例，边为 $1\to 3, 1\to 5, 2\to 3, 3\to 1, 3\to 4$。 共有三种可能的路由方案： $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$ 对于第二个测试用例，边为 $1\to 3, 2\to 4, 3\to 2,3\to 6, 4\to 5, 5\to 3$。 只有一种可能的路由方案： $1\to 3\to 2\to 4\to 5\to 3\to 6$。 一些额外的小测试用例。 计分（SCORING）： 测试点 4-5 满足 $N\le 6$。 测试点 6-7 满足 $K=0$。 测试点 8-12 满足 $K=1$。 测试点 13-24 满足 $K=2$。 题目署名：Benjamin Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum