뒤죽박죽 소 줄 세우기

면접 대비

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

요약

N개의 일련번호(최대 16개)를 나열할 때 이웃한 두 수의 차가 모두 K보다 큰 순열의 개수를 센다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 비트 연산, 조합론, 완전 탐색
정답자: 아직 제출이 없습니다

문제

농부 존의 소 $N$ 마리 ( $4 \le N \le 16$ )는 저마다 서로 다른 고유 번호 $S_i$ ( $1 \le S_i \le 25000$ )를 가지고 있다.

소들을 한 줄로 세워 젖을 짤 때, 줄에서 이웃한 두 소의 번호 차이가 항상 $K$ ( $1 \le K \le 3400$ )보다 크면 그 줄을 '뒤죽박죽(Mixed Up)' 줄이라고 부른다. 예를 들어 $N = 6$ , $K = 1$ 일 때 번호 순서가 $1, 3, 5, 2, 6, 4$ 인 줄은 '뒤죽박죽'이지만, $1, 3, 6, 5, 2, 4$ 인 줄은 이웃한 $5$ 와 $6$ 의 차이가 $1$ 이므로 '뒤죽박죽'이 아니다.

$N$ 마리의 소를 '뒤죽박죽'으로 세우는 서로 다른 방법의 수를 구하여라.

입력

첫째 줄: 두 정수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다.
둘째 줄부터 $N+1$ 째 줄까지: $i+1$ 째 줄에는 소 $i$ 의 고유 번호 $S_i$ 가 하나씩 주어진다.

출력

첫째 줄: $N$ 마리의 소를 '뒤죽박죽'으로 세우는 방법의 수를 출력한다. 답은 64비트 정수 범위 안에 들어감이 보장된다.

힌트

예제에서 가능한 '뒤죽박죽' 배열은 다음 $2$ 가지이며, 각 줄은 소들의 번호를 줄 세운 순서대로 나열한 것이다.

3 1 4 2
2 4 1 3

예제2

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