#PU1069. USACO 2020 December Contest, Platinum — Problem 2. Spaceship

USACO 2020 December Contest, Platinum — Problem 2. Spaceship

USACO 2020 December Contest, Platinum — Problem 2. Spaceship

题目描述

Bessie the cow has been abducted by aliens and is now trapped inside an alien spaceship! The spaceship has NN (1≤N≤60)(1\le N\le 60) rooms labeled 1…N1\ldots N, with one-way doors connecting between some pairs of rooms (due to the strange alien technology at play, it is even possible for a door to lead from a room back to itself!). However, no two doors share the same starting and end room. Additionally, Bessie has a remote with buttons numbered 1…K1\ldots K (1≤K≤60)(1 \le K \le 60). The aliens will release Bessie if she can complete a strange task. First, they will choose two rooms, ss and tt (1≤s,t≤N)(1 \le s, t \le N), and two numbers, bsb_s and btb_t (1≤bs,bt≤K)(1 \le b_s, b_t \le K). They will start Bessie in room ss and immediately have her press button bsb_s. Bessie will then proceed to navigate the ship while pressing buttons. There are a few rules for what Bessie can do: In each room, after pressing exactly one button, she must choose to either exit through a door to another (possibly the same) room or stop. Once Bessie presses a button, it is invalid for her to press the same button again unless, in the time between uses, she has pressed a button with a higher number. In other words, pressing button number xx will make it unavailable for use, while all buttons with numbers <x<x will be reset and again available for use. If Bessie presses an invalid button, she automatically fails and the aliens will keep her. Bessie is released only if she stops in room tt, the last button she pressed was btb_t, and no invalid buttons were ever pressed. Bessie is worried that she may not be able to complete the task. For QQ (1≤Q≤60)(1\le Q\le 60) queries, each consisting of what Bessie considers a likely choice of s,t,bss, t, b_s, and btb_t, Bessie wants to know the number of sequences of rooms and button presses that would lead to her release. Report your answers modulo 109+710^9 + 7 as they may be very large.

输入格式

The first line contains N,K,QN,K,Q. The next NN lines each contain NN bits (each 0 or 1). The jj-th entry of the ii-th line is 1 if there exists a door from room ii to room jj, and 0 if no such door exists. This is followed by QQ lines, each containing four integers bsb_s, ss, btb_t, tt, denoting the starting button, starting room, final button, and final room respectively.

输出格式

The number of sequences for each of the QQ queries modulo 109+710^9+7 on separate lines.

数据范围

In test cases 4-7, K≤5K\le 5 and (bs,s)(b_s,s) is the same for all queries. In test cases 8-11, bs=K−1b_s=K-1 and bt=Kb_t=K for each query. In test cases 12-15, N,K,Q≤20N,K,Q\le 20. In test cases 16-23, there are no additional constraints. Problem credits: Benjamin Qi

样例

样例 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
0
1
3
2
2
0
5
The doors connect rooms $1\to 2$, $2 \to 3$, $3\to 4$, $4\to 5$, and $6\to 6$.
For the first query, Bessie must stop immediately after pressing the first
button.
For the second query, the answer is clearly zero because there is no way to get
to room 1 from room 3.
For the third query, Bessie's only option is to move from room 1 to room 2 to
room 3 while pressing buttons 1, 2, and 3.
For the fourth query, Bessie's pattern of movement is fixed, and she has three
possible sequences of button presses:
$(1,2,3,2,1)$
$(1,2,1,3,1)$
$(1,3,1,2,1)$
For the last query, Bessie has five possible sequences of button presses:
$(2)$
$(2,3,2)$
$(2,3,1,2)$
$(2,1,3,2)$
$(2,1,3,1,2)$

样例 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
26
49
29
27
18
22
This test case satisfies the constraints for all subtasks aside from the first.

样例 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
713313311
716721076
782223918
335511486
539247783
Make sure to output the answers modulo $10^9+7$.