레이팅 미적용소 베시가 외계인에게 납치되어 외계 우주선 안에 갇히고 말았다! 우주선에는 \(1\ldots N\)으로 번호가 매겨진 \(N\)개\((1\le N\le 60)\)의 방이 있고, 일부 방 쌍 사이에는 일방통행 문이 연결되어 있다(기묘한 외계 기술 때문에 문이 어떤 방에서 그 방 자신으로 이어지는 것도 가능하다!). 다만 시작 방과 끝 방이 모두 같은 문은 두 개 존재하지 않는다. 또한 베시는 \(1\ldots K@@RISE_MATH_BLOCK_0@@(1 \le s, t \le N)\), 그리고 두 수 \(b_s\)와 \(b_t@@RISE_MATH_BLOCK_1@@(1\le Q\le 60)\)개의 질의 각각에 대해, 베시가 풀려나게 되는 방과 버튼 누름의 수열의 개수를 알고 싶어 한다. 답이 매우 클 수 있으므로 \(10^9 + 7\)로 나눈 나머지를 출력한다.
문제 제공: Benjamin Qi
배점
- 테스트 케이스 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
첫째 줄에 \(N,K,Q\)가 주어진다.
다음 \(N\)개의 줄 각각에는 \(N\)개의 비트(각각 0 또는 1)가 주어진다. \(i\)번째 줄의 \(j\)번째 값이 1이면 방 \(i\)에서 방 \(j\)로 가는 문이 존재하고, 0이면 그러한 문이 존재하지 않는다.
이어서 \(Q\)개의 줄이 주어지며, 각 줄에는 네 정수 \(b_s\), \(s\), \(b_t\), \(t\)가 주어진다. 이는 각각 시작 버튼, 시작 방, 마지막 버튼, 마지막 방을 나타낸다.
\(Q\)개의 질의 각각에 대해 수열의 개수를 \(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 61
0
1
3
2
2
0
5The 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)\)
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 226
49
29
27
18
22This test case satisfies the constraints for all subtasks aside from the first.
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 4713313311
716721076
782223918
335511486
539247783Make sure to output the answers modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > December > Platinum