TLEoj Cup Final Day 2 - Cầu thang

Điểm: 1700 (thành phần)

Thời gian: 1.75s

Bộ nhớ: 256M

Input: STAIR.inp

Output: STAIR.out

Tác giả:

Sunlight

Dạng bài

khanhphucscratch và moi_hoc_code đang đứng ở hai đầu của một cầu thang gồm $m$ bậc, trong đó có $n$ bậc bị hỏng. khanhphucscratch đang ở bậc thang thứ nhất và muốn leo lên bậc thang thứ $m$ . Trong mỗi bước, khanhphucscratch có thể leo lên không quá $k$ bậc (từ bậc $i$ có thể leo đến các bậc không quá $i + k$ ). Bạn hãy giúp khanhphucscratch đếm số cách leo đến bậc thứ $m$ nhé.

Input, Output và Subtask

Input (STAIR.inp)

Dòng đầu tiên gồm ba số nguyên dương $n, m, k$ $(0 \le n \le 2000, \min(n, 1) \le m \le 10^{18}, 2 \le k \le 10)$
Dòng tiếp theo gồm $n$ số nguyên dương phân biệt $a_i$ $(1 < a_i < m)$ là thứ tự các bậc thang bị hỏng.

Output (STAIR.out)

In ra số cách khanhphucscratch có thể leo cầu thang, sau khi chia lấy dư cho $10^9 + 7$ .

Subtask

$20\%$ số điểm có $m \le 10^6$ .
$20\%$ số điểm khác có $n = 0$ và $k = 2$ .
$20\%$ số điểm khác có $n = 1$ và $k = 2$ .
$20\%$ số điểm khác có $n = 0$ .
$20\%$ số điểm khác không có giới hạn gì thêm.

Sample 1

Input (STAIR.inp)

1 6 2
3

Output (STAIR.out)

Notes

Phúc có hai cách leo cầu thang, đó là $1 \rightarrow 2 \rightarrow 4 \rightarrow 6$ hoặc $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$ .

Bình luận đầu tiên

Bình luận

Không có bình luận nào.