Duyên hải Bắc Bộ 2024 - 10 - Tập số

Xem dạng PDF

Gửi bài giải

Điểm: 20,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Trên tập số ~\{1, 2, \dots, n\}~, Alice tiến hành xóa đi ~k~ (~k < n~) số ~a_1, a_2, \dots, 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~.

Yêu cầu: Cho ~n, k, d~ và dãy ~a_1, a_2, \dots, 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.

Input

  • Dòng đầu chứa ba số nguyên dương ~n, k, d~ (~k < n \le 10^7~; ~k \le 10^5~; ~d \le n~);

  • Dòng thứ hai chứa ~k~ số nguyên dương phân biệt ~a_1, a_2, \dots, a_k~ (~a_i \le n~, ~1 \le i \le k~);

Output

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)~.

Scoring

Subtask Điểm Ràng buộc
1 ~20\%~ ~n-k \le 20~
2 ~25\%~ ~n-k \le 200~
3 ~25\%~ ~n-k \le 2 \times 10^5~
4 ~30\%~ Không có ràng buộc gì thêm.

Sample Input 1

8 3 1
2 3 8

Sample Output 1

3
3

Bình luận

Hãy đọc nội quy trước khi bình luận.


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