페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10440

오리, 오리, 거위들 20s 1024MB

문제

"Duck, Duck, Goose"(오리, 오리, 거위) 게임에서는 한 명을 제외한 모든 플레이어가 바닥에 앉아 원을 이룬다. 남은 한 명은 원을 따라 걸으며 각 플레이어를 "duck"이라고 부르다가, 앉아 있는 플레이어 중 한 명을 선택해 그 머리를 만지면서 그때만 "goose"라고 부른다. 그러면 거위가 선택한 플레이어를 쫓아가고, 우리의 흥미는 그 시점에 사라진다.

새 게임 "Duck, Duck, Geese"에서는 걷는 플레이어가 대신 앉아 있는 플레이어들 중 연속한 부분집합을 (최소 2명, 하지만 전원은 아님) "거위"로 지정한다! 게다가 앉아 있는 각 플레이어는 모자를 쓰고 있다. 각 모자는 가능한 \mathbf{C}가지 색 중 하나이며, 색은 1부터 \mathbf{C}까지 번호가 매겨져 있다.

Illustration of Sample Case #2. 5 children seated on a grey mat in a circle. In clockwise order (starting from the bottom-right child), the children have hats of colors yellow, blue, yellow, blue, and blue.

각 색 i에 대해, 선택된 거위들 중 색 i 모자를 쓴 사람의 수는 0이거나, \mathbf{A_i} 이상 \mathbf{B_i} 이하(양 끝 포함)여야 한다.

이 조건을 모두 만족하는 선택의 개수를 세는 일을 도와줄 수 있는가? 어떤 플레이어가 한 선택에는 포함되고 다른 선택에는 포함되지 않는다면, 두 선택은 서로 다르다고 본다.


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다. 각 테스트 케이스는 정수 두 개 \mathbf{N}, \mathbf{C}가 주어진 한 줄로 시작하며, 이는 각각 앉아 있는 플레이어의 수와 모자 색의 수이다. 그 다음 \mathbf{C}줄이 이어진다. 이 중 i번째 줄에는 정수 두 개 \mathbf{A_i}, \mathbf{B_i}가 주어지며, 위에서 설명한 값들이다. 각 테스트 케이스의 마지막 줄에는 \mathbf{N}개의 정수 \mathbf{P_1}, \mathbf{P_2}, \dots, \mathbf{P_N}가 주어진다. 이는 (임의의 한 사람을 시작점으로 잡았을 때) 시계 방향 순서로 j번째로 앉아 있는 플레이어가 색 \mathbf{P_j}의 모자를 쓰고 있음을 의미한다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 크기가 최소 2이고 최대 \mathbf{N}-1인 연속해서 앉아 있는 플레이어들의 집합 중에서, 모든 색 조건을 만족하는 집합의 개수이다.


예제 

3
3 2
1 1
1 1
1 1 2
5 2
1 1
1 2
1 2 1 2 2
3 3
1 2
1 2
2 2
1 1 3
Case #1: 2
Case #2: 9
Case #3: 1
샘플 케이스 #1에서는 거위로 선택된 플레이어 수가 2여야 한다. 2명을 고르는 방법은 세 가지뿐이며, 가능한 색 구성은 [1, 1], [1, 2], [2, 1]이다. 첫 번째는 색 1 모자를 쓴 플레이어가 두 명이라 유효하지 않고, 나머지 두 가지는 유효하다. 따라서 답은 2이다. 샘플 케이스 #2는 문제 설명에 그림으로 나온 경우이며, 색 1은 노랑, 색 2는 파랑이다. 이 경우 거위로 선택되는 플레이어 수는 2~3 사이여야 한다. 4명을 고르면 최소 한 색이 범위를 벗어나기 때문이다. 2명을 고르는 경우에는 색 1 모자를 쓴 거위를 두 명 모두 고르지만 않으면 된다. 그런 선택은 5가지 모두 유효하다. 3명을 고르는 경우 가능한 조합은 [1, 2, 1], [2, 1, 2], [1, 2, 2], [2, 2, 1], [2, 1, 2]이다. 첫 번째를 제외한 나머지가 유효하므로 추가로 4가지가 가능하고, 총 9가지다. 샘플 케이스 #3에서는 아무도 쓰지 않은 모자 색이 있을 수 있음을 유의하라. 이 경우 색 3 모자를 쓴 플레이어는 한 명뿐인데 1은 범위 밖이므로, 그 색의 플레이어를 0명 고르는 것만 유효하다.

출처

GCJ 2022r3 B

로그인해야 코드를 작성할 수 있어요.