역순열 하강 개수

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

요약

크기 N인 순열에서 첫 원소를 F로 고정하고 그 역순열이 정확히 K개의 하강을 갖는 경우의 수를 구합니다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

길이 N인 순열 A = (A_0, A_1, ..., A_{N-1})은 0부터 N-1까지의 정수를 한 번씩 포함한다. 순열 B = (B_0, B_1, ..., B_{N-1})를 B_{A_i} = i를 만족하는 A의 역순열이라고 하자. 예를 들어 A = (2, 0, 3, 1, 4)이면 B = (1, 3, 0, 2, 4)이다.

역순열 B에서 B_i > B_{i+1}를 만족하는 인덱스 i의 개수가 정확히 K개이면, A를 K개의 역순열 하강을 가진 순열이라고 하자.

N, K, F가 주어진다. A_0 = F이면서 역순열 하강이 정확히 K개인 순열 A의 개수를 구하라.

입력

첫째 줄에 N, 둘째 줄에 K, 셋째 줄에 F가 주어진다.

출력

조건을 만족하는 순열의 개수를 출력한다.

제한

1 <= N <= 20
0 <= K <= N-1
0 <= F <= N-1

예제4

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