이면체 군

면접 대비

시간 제한1초메모리 제한2048 MB

요약

원형으로 놓인 라벨 d를 회전하거나 뒤집었을 때 수열 t가 연속으로 나타나는지 판별합니다.

난이도: 보통10점 중 5점
유형: 문자열 매칭, 배열
정답자: 아직 제출이 없습니다

문제

수학에서 이면체 군 $D_n$ 은 정 $n$ 각형의 대칭들로 이루어진 군이다. 회전과 반사는 $D_n$ 의 원소이며, 사실 이면체 군의 모든 원소는 회전과 반사의 열로 표현할 수 있다. $D_n$ 의 원소는 꼭짓점을 치환하여 $n$ 각형에 작용한다. 예를 들어, 위에서 시작해 시계 방향으로 꼭짓점에 $1$ , $3$ , $5$ , $4$ , $2$ 가 처음에 적혀 있는 정오각형을 생각하자:

위의 세 가지 이면체 작용(회전, 반사, 그리고 다시 회전)을 오각형에 차례로 적용하면 꼭짓점의 번호가 다음과 같이 바뀐다:

$1, 3, 5, 4, 2 \rightarrow 2, 1, 3, 5, 4 \rightarrow 2, 4, 5, 3, 1 \rightarrow 1, 2, 4, 5, 3.$

입력

첫 줄에는 두 정수 $n$ 과 $m$ 이 주어진다 ( $1 \leq m \leq n \leq 5 \cdot 10^{4}$ ). $n$ 은 다각형의 꼭짓점 개수이고, $m$ 은 검사할 수열의 길이이다.

다음 줄에는 공백으로 구분된 정수 $n$ 개 $d$ ( $1 \le d \le n$ )가 주어진다. 다각형 꼭짓점의 초기 번호이다. $1$ 부터 $n$ 까지의 정수가 각각 정확히 한 번씩 나타난다고 보장된다.

다음 줄에는 공백으로 구분된 정수 $m$ 개 $t$ ( $1 \le t \le n$ )가 주어진다. 검사할 수열이다.

출력

검사할 수열이 이면체 작용을 여러 번 적용한 뒤의 다각형에서 시계 방향으로 연속된 꼭짓점 번호로 나타날 수 있으면 $1$ 을, 그렇지 않으면 $0$ 을 정수 하나로 출력한다.

예제5

예제 1
입력
```
3 3
1 2 3
1 3 2
```
예상 출력
```
1
```
예제 2
입력
```
3 1
1 2 3
1
```
예상 출력
```
1
```
예제 3
입력
```
4 2
1 2 3 4
1 3
```
예상 출력
```
0
```
예제 4
입력
```
4 4
1 2 3 4
2 3 4 1
```
예상 출력
```
1
```
예제 5
입력
```
4 4
1 2 3 4
3 2 1 4
```
예상 출력
```
1
```