Duyên hải Bắc Bộ 2024 - 10 - Tập số
Xem dạng PDFTrong 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