📖 문제 개요

문제

길이 $N$의 순열 $A=[A_0, A_1, \dots, A_{N-1}]$이 주어진다. 길이 $N$의 순열이란, $0$부터 $N-1$까지의 모든 정수가 정확히 한 번씩 등장하는 수열이다.

양의 정수 $K$가 주어질 때, 다음과 같은 연산을 원하는 만큼 수행할 수 있다.

• 임의의 $i$ ($0 \leq i < N$)에 대해 $A_i$와 $A_{(i+K) \bmod N}$의 값을 바꾼다.

주어진 연산을 통해 순열 $A$를 오름차순으로 정렬할 수 있는지 확인해 보자.

$\bmod$ 연산에 대한 설명은 노트를 참고하라.

입력

첫 번째 줄에 순열의 길이 $N$과 양의 정수 $K$가 공백으로 구분되어 주어진다. $\left(1 \leq K \leq N \leq 10^{6}\right)$

두 번째 줄에 순열 $A$의 원소 $A_0, A_1, \dots, A_{N-1}$이 공백으로 구분되어 주어진다. 순열은 $0$부터 $N-1$까지의 정수가 한 번씩 주어진다.

출력

주어진 연산을 원하는 만큼 반복하여 순열 $A$를 오름차순으로 정렬할 수 있다면 YES , 아니면 NO 를 출력한다.

예제 입력 1

6 2
2 3 4 1 0 5

예제 출력 1

YES

예제 입력 2

4 2
0 1 3 2

예제 출력 2

NO

노트

$\bmod$는 나머지 연산으로, $a \bmod b$는 $a$를 $b$로 나눈 나머지를 뜻한다. 예를 들어, $5 \bmod 3 = 2$이다.

✏️ 풀이

구현이 익숙하다면 쉽게 수학적 논리로 통타하는 게 가능하고, 그렇지 않다면 접근이 다소 어려운 특이한 형태의 문제.

일단 문제에서 제시한