[USACO20DEC] Spaceship P
题目描述
奶牛 Bessie 外星人绑架了,现在被关在了一艘外星人的飞船里!飞船有 $N$($1≤N≤60$)间房间,编号为 $1…N$,其中某些房间之间由单向通过的门所连接(由于使用了奇怪的外星技术,一扇门甚至可能从一间房间通回这间房间本身!)。然而,没有两扇门具有完全相同的出发和到达房间。此外,Bessie 有一个遥控器,上有编号为 $1…K$ ($1≤K≤60$)的按钮。
如果 Bessie 能够完成一个怪异的任务,外星人就会释放她。首先,他们会选择两间房间 $s$ 和 $t$($1≤s,t≤N$),以及两个整数 $b_s$ 和 $b_t$($1≤b_s,b_t≤K$)。他们会将 Bessie 放在房间 $s$ 内,并令她立刻按下按钮 $b_s$。然后 Bessie 需要继续在飞船内穿梭,同时按下按钮。有一些 Bessie 的行动需要遵守的规则:
- 在每间房间内,在按下恰好一个按钮后,她必须选择从某扇门离开去往另一间房间(可能会回到同一间房间)或停止行动。
- 一旦 Bessie 按下某个按钮,她再次按下这个按钮即为非法,除非在此之间她按下过编号更大的按钮。换句话说,按下编号为 x 的按钮会使得这个按钮变为非法,同时所有编号 $<x$ 的按钮会被重置为合法。
- 如果 Bessie 按下非法的按钮,任务即失败,外星人就会把她关起来。
仅当 Bessie 停止行动时位于房间 $t$,她最后按下的按钮是 $b_t$,并且没有按下过非法按钮时,Bessie 才会被释放。
Bessie 担心她可能无法完成这一任务。对于 $Q$
($1≤Q≤60$)个询问,每个询问包含一组 Bessie 认为可能的 $s,t,b_s$ 以及 $b_t$,Bessie 想要知道可以使她得到释放的通过房间与按键序列的数量。由于答案可能非常大,输出对 $10^9+7$ 取模的结果。
输入输出格式
输入格式
输入的第一行包含 $N,K,Q$。
以下 $N$ 行每行包含 $N$ 个二进制位($0$ 或 $1$)。如果从房间 $i$ 到房间 $j$ 存在一扇门,则第 $i$ 行的第 $j$ 位为 1,如果没有这样的门则为 0。
以下 $Q$ 行,每行包含四个整数 $b_s$、$s$、$b_t$、$t$,分别表示起始按钮、起始房间、结束按钮、结束房间。
输出格式
对 $Q$ 个询问的每一个,在一行内输出操作序列的数量模 $10^9+7$ 的结果。
输入输出样例
输入样例 #1
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
1
0
1
3
2
2
0
5
输入样例 #2
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
输出样例 #2
26
49
29
27
18
22
输入样例 #3
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
输出样例 #3
713313311
716721076
782223918
335511486
539247783
说明
门连接了房间 $1→2$、$2→3$、$3→4$、$4→5$ 以及 $6→6$。
对于第一个询问,Bessie 必须在按下第一个按钮后立刻停止行动。
对于第二个询问,答案显然为零,因为无法从房间 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)
### 测试点性质:
- 测试点 4-7 中,$K≤5$ 且 $(b_s,s)$ 在所有询问中均相同。
- 测试点 8-11 中,对所有询问有 $b_s=K−1$ 以及 $b_t=K$。
- 测试点 12-15 中,$N,K,Q≤20$。
- 测试点 16-23 没有额外限制。
供题:Benjamin Qi