Tập số

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

23-24 DHBB K10

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Trên tập số ${1, 2, . . ., n}$ , Alice tiến hành xóa đi $k$ ( $k < n$ ) số $a_{1}, a_{2}, . . ., a_{k}$ để nhận được tập $S$ . Một cách chọn các số trên tập $S$ được gọi là cách chọn tối ưu bậc $d$ nếu:

Hiệu hai số bất kì được chọn có giá trị tuyệt đối lớn hơn $d$ ;
Số lượng số được chọn là lớn nhất.

Ví dụ, trên tập số ${1, 2, 3, 4, 5, 6, 7, 8}$ , xóa đi ba số $2, 3, 8$ được tập $S = {1, 4, 5, 6, 7}$ , ba tập ${1, 4, 6}$ , ${1, 4, 7}$ và ${1, 5, 7}$ đều là cách chọn tối ưu bậc $1$ .

Cho $n, k, d$ và dãy $a_{1}, a_{2}, . . ., a_{k}$ , hãy giúp Alice tính số lượng số chọn được trong cách chọn tối ưu bậc $d$ và số cách chọn tối ưu. Chú ý, hai cách chọn được gọi là khác nhau nếu tồn tại một số của $S$ thuộc trong cách chọn này nhưng không thuộc trong cách chọn kia.

Dữ liệu vào

Dòng đầu chứa ba số nguyên dương $n, k, d$ ( $k < n \leq 10^{7}$ ; $k \leq 10^{5}$ ; $d \leq n$ );
Dòng thứ hai chứa $k$ số nguyên dương phân biệt $a_{1}, a_{2}, . . ., a_{k}$ ( $a_{i} \leq n$ , $1 \leq i \leq k$ );

Dữ liệu ra

Hai dòng, dòng thứ nhất là số lượng số chọn được trong cách chọn tối ưu, dòng thứ hai là số cách chọn tối ưu chia dư cho ( $10^{9} + 7$ ).

Ràng buộc

$k < n \leq 10^{7}$
$k \leq 10^{5}$
$d \leq n$
Subtask 1 (20 điểm): $n - k \leq 20$
Subtask 2 (25 điểm): $n - k \leq 200$
Subtask 3 (25 điểm): $n - k \leq 2 \times 10^{5}$
Subtask 4 (30 điểm): Không có ràng buộc gì thêm.

Ví dụ

Input	Output	Giải thích
8 3 1 2 3 8	3 3	$S = {1, 4, 5, 6, 7}$ . Chọn tối đa $3$ số có hiệu đôi một $> 1$ . Có $3$ cách: ${1, 4, 6}$ , ${1, 4, 7}$ , ${1, 5, 7}$ .

Bình luận

Không có bình luận tại thời điểm này.