NKD 수열의 개수

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

요약

합이 N이고 인접한 항의 차가 D 이하이며 첫 항이 D 이하인 길이 K의 엄격히 증가하는 수열의 개수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

세 정수 $N$ , $K$ , $D$ 가 주어진다. 크기가 $K$ 인 자연수 수열 $A_1, A_2, \dots, A_K$ 중에서 다음 조건을 모두 만족하는 수열의 개수를 구하자.

$A_1 + A_2 + \dots + A_K = N$
$A_1 < A_2 < \dots < A_K$
모든 $1 \le i < K$ 에 대해 $A_{i+1} - A_i \le D$
$A_1 \le D$

입력

첫째 줄에 세 정수 $N$ , $K$ , $D$ 가 공백으로 구분되어 주어진다.

출력

조건을 만족하는 수열의 개수를 $10^9 + 7$ 로 나눈 나머지를 출력한다.

제한

$1 \le N, K, D \le 10^5$

예제1

예제 1
입력
```
10 4 1
```
예상 출력
```
1
```

Loading...