A975. Spaceship--Platinum
编程题
NOI/NOI+/CTSC
知识点
题目描述
Bessie the cow has been abducted by aliens and is now trapped inside an alien
spaceship! The spaceship has $N$ $(1\le N\le 60)$ rooms labeled $1\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\ldots K$ $(1 \le K
\le 60)$.
The aliens will release Bessie if she can complete a strange task. First, they
will choose two rooms, $s$ and $t$ $(1 \le s, t \le N)$, and two numbers,
$b_s$ and $b_t$ $(1 \le b_s, b_t \le K)$. They will start Bessie in room $s$
and immediately have her press button $b_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 $x$ will make it unavailable for use, while all buttons with numbers $<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 $t$, the last button she pressed
was $b_t$, and no invalid buttons were ever pressed.
Bessie is worried that she may not be able to complete the task. For $Q$
$(1\le Q\le 60)$ queries, each consisting of what Bessie considers a likely
choice of $s, t, b_s$, and $b_t$, Bessie wants to know the number of sequences
of rooms and button presses that would lead to her release. Report your
answers modulo $10^9 + 7$ as they may be very large.
spaceship! The spaceship has $N$ $(1\le N\le 60)$ rooms labeled $1\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\ldots K$ $(1 \le K
\le 60)$.
The aliens will release Bessie if she can complete a strange task. First, they
will choose two rooms, $s$ and $t$ $(1 \le s, t \le N)$, and two numbers,
$b_s$ and $b_t$ $(1 \le b_s, b_t \le K)$. They will start Bessie in room $s$
and immediately have her press button $b_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 $x$ will make it unavailable for use, while all buttons with numbers $<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 $t$, the last button she pressed
was $b_t$, and no invalid buttons were ever pressed.
Bessie is worried that she may not be able to complete the task. For $Q$
$(1\le Q\le 60)$ queries, each consisting of what Bessie considers a likely
choice of $s, t, b_s$, and $b_t$, Bessie wants to know the number of sequences
of rooms and button presses that would lead to her release. Report your
answers modulo $10^9 + 7$ as they may be very large.
输入格式
The first line contains $N,K,Q$.
The next $N$ lines each contain $N$ bits (each 0 or 1). The $j$-th entry of
the $i$-th line is 1 if there exists a door from room $i$ to room $j$, and 0
if no such door exists.
This is followed by $Q$ lines, each containing four integers $b_s$, $s$,
$b_t$, $t$, denoting the starting button, starting room, final button, and
final room respectively.
The next $N$ lines each contain $N$ bits (each 0 or 1). The $j$-th entry of
the $i$-th line is 1 if there exists a door from room $i$ to room $j$, and 0
if no such door exists.
This is followed by $Q$ lines, each containing four integers $b_s$, $s$,
$b_t$, $t$, denoting the starting button, starting room, final button, and
final room respectively.
输出格式
The number of sequences for each of the $Q$ queries modulo $10^9+7$ on
separate lines.
separate lines.
输入输出样例
输入 #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
说明/提示
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)$
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)$