| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 83 | 38 | 25 | 37.879% |
도시와 의식이 자리를 잡은 후, 사람들은 빛의 흐름 속에서 더 깊은 질서를 찾고자 했다.
그들은 빛을 따라 형상을 새기고 무늬를 관찰하며 그 안에 담긴 조화의 규칙을 헤아리려 했다.
그러나 얼마 지나지 않아, 그들은 모든 무늬가 조화를 이룰 수 있는 것은 아니라는 사실을 깨달았다. 일부 배열은 균형을 잃고 무너졌고, 사람들은 조화를 이루는 형상을 찾기 위해 고민을 거듭했다.
그들이 남긴 배열을 되짚고, 조화로운 빛의 무늬를 다시 그려보아라.
사람들은 $N\times N$ 크기의 격자 위에 빛을 하나씩 배치하며, 안정적인 무늬를 이루는 방법을 연구했다. 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 격자칸을 $(r,c)$로 표기한다.
다음 조건을 만족하는 배치를 안정적인 구조라 부른다.
예를 들어, 아래 그림에서 왼쪽은 안정적인 구조이다. 하지만 오른쪽은 세 칸 $(1,5),ドル $(2,2),ドル $(3,1)$이 불안정한 배열을 이루므로, 안정적인 구조가 아니다.
사람들은 더 정교한 구조를 탐구하기 위해 다음과 같은 형태의 조건들을 제시했다.
사람들은 이러한 형태의 조건을 추가하거나 제거하며 안정적인 구조의 수가 어떻게 달라지는지 살펴보고자 한다.
첫 줄에 격자의 크기를 나타내는 정수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.
이후 $Q$개의 줄에 걸쳐, 그중 $i$번째 줄에는 다음과 같은 형태 중 하나의 쿼리가 주어진다.
쿼리가 들어오기 전에는 조건이 하나도 없다.
3ドル$번 종류의 쿼리가 들어올 때마다, 현재 존재하는 조건을 모두 만족하는 안정적인 구조의 개수를 10ドル^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.
아래 제한에서 $t_i$는 $i$번 쿼리의 종류를 의미한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $N = 3, Q \le 400$ |
| 2 | 7 | $N \le 8, Q \le 400$ |
| 3 | 10 | $Q = 1$ |
| 4 | 23 | $N \le 400, Q \le 400$ |
| 5 | 25 | $N \le 2000, Q \le 2000$ |
| 6 | 13 | $Q \le 2$ |
| 7 | 18 | 추가 제한 조건이 없다. |
3 8 3 1 1 1 3 2 2 1 3 1 3 1 1 3 3
5 2 1 0
5 11 1 4 3 1 5 2 3 2 2 3 1 3 1 1 3 2 1 5 5 3 2 6 3
0 18 2 6
20 1 3
564120378
20 2 1 15 10 3
936990054
Contest > BOJ User Contest > BCF > BCF 2025 IV번