Spaceship

题目描述

奶牛 Bessie 被外星人绑架了，现在被困在一艘外星飞船里！飞船有 $N$ 个房间 $(1\le N\le 60)$，编号为 $1\ldots N$，一些房间对之间通过单向门连接（由于奇怪的外星科技，甚至可能存在从一个房间通向它自身的门！）。不过，任意两扇门不会拥有相同的起点与终点房间。 此外，Bessie 还有一个遥控器，上面有编号为 $1\ldots K$ 的按钮 $(1 \le K \le 60)$。

外星人会在 Bessie 完成一项奇怪的任务后放她走。首先，他们会选择两个房间 $s$ 和 $t$ $(1 \le s, t \le N)$，以及两个数字 $b_s$ 和 $b_t$ $(1 \le b_s, b_t \le K)$。他们会让 Bessie 从房间 $s$ 开始，并立刻让她按下按钮 $b_s$。随后 Bessie 将在飞船中移动并按按钮。Bessie 的行动规则如下： 在每个房间中，在恰好按下一个按钮之后，她必须选择要么通过一扇门前往另一个（可能是同一个）房间，要么停止。 一旦 Bessie 按下某个按钮，除非在两次使用之间她按过一个编号更大的按钮，否则她再次按下同一个按钮就是非法的。 换句话说，按下编号为 $x$ 的按钮会使其在之后不可用，而所有编号 $<x$ 的按钮会被重置并重新变为可用。 如果 Bessie 按下了非法按钮，她会立刻失败，外星人将继续关押她。 只有当 Bessie 停在房间 $t$、最后一次按下的按钮是 $b_t$，并且过程中从未按下任何非法按钮时，她才会被释放。

Bessie 担心自己可能无法完成任务。对于 $Q$ 个查询 $(1\le Q\le 60)$，每个查询给出 Bessie 认为外星人可能选择的一组 $s, t, b_s, b_t$，Bessie 想知道有多少种“房间序列与按钮按下序列”能够使她被释放。由于答案可能很大，请输出对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含 $N,K,Q$。 接下来 $N$ 行每行包含 $N$ 个比特（0 或 1）。第 $i$ 行的第 $j$ 个字符为 1 表示存在一扇从房间 $i$ 通向房间 $j$ 的门；为 0 表示不存在。 之后有 $Q$ 行，每行包含四个整数 $b_s$, $s$, $b_t$, $t$，分别表示起始按钮、起始房间、最终按钮、最终房间。

输出格式

对每个查询，输出能够使 Bessie 被释放的序列数量对 $10^9+7$ 取模后的值，每个答案一行。

6 3 8
010000
001000
000100
000010
000000
000001
1 1 1 1
3 3 1 1
1 1 3 3
1 1 1 5
2 1 1 5
1 1 2 5
3 1 3 5
2 6 2 6

1
0
1
3
2
2
0
5

6 4 6
001100
001110
101101
010111
110111
000111
3 2 4 3
3 1 4 4
3 4 4 1
3 3 4 3
3 6 4 3
3 1 4 2

26
49
29
27
18
22

6 10 5
110101
011001
001111
101111
111010
000001
2 5 2 5
6 1 5 2
3 4 8 3
9 3 3 5
5 1 3 4

713313311
716721076
782223918
335511486
539247783

提示

门连接了房间 $1\to 2$, $2 \to 3$, $3\to 4$, $4\to 5$, 以及 $6\to 6$。 对于第一个查询，Bessie 必须在按下第一个按钮后立刻停止。 对于第二个查询，答案显然是 0，因为无法从房间 3 到达房间 1。 对于第三个查询，Bessie 唯一的选择是从房间 1 到房间 2 再到房间 3，同时按下按钮 1、2、3。 对于第四个查询，Bessie 的移动模式是固定的，她有三种可能的按钮按下序列： $(1,2,3,2,1)$ $(1,2,1,3,1)$ $(1,3,1,2,1)$ 对于最后一个查询，Bessie 有五种可能的按钮按下序列： $(2)$ $(2,3,2)$ $(2,3,1,2)$ $(2,1,3,2)$ $(2,1,3,1,2)$

该测试用例满足除第一个子任务之外的所有子任务限制。

请确保输出对 $10^9+7$ 取模后的答案。

评分（SCORING）： 在测试点 4-7 中，$K\le 5$ 且所有查询的 $(b_s,s)$ 相同。 在测试点 8-11 中，每个查询都有 $b_s=K-1$ 且 $b_t=K$。 在测试点 12-15 中，$N,K,Q\le 20$。 在测试点 16-23 中，没有额外限制。

题目署名：Benjamin Qi

标签: USACO|2020|Platinum

来源

USACO|2020|Platinum