[Phú Thọ - PreTS10 - 2026] Bài 4: Đếm tập con
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
An có một bộ sưu tập đồ chơi gồm ~A~ món. Mỗi món đồ chơi thuộc về một trong ~T~ loại, các loại đồ chơi được đánh số từ 1 đến ~T~. An nhận ra rằng có thể tạo ra nhiều nhóm đồ chơi khác nhau bằng cách chọn một số món (có thể từ cùng một loại hoặc nhiều loại). Mỗi nhóm là một tập hợp không phân biệt thứ tự, nghĩa là hai nhóm được coi là khác nhau nếu tồn tại một loại đồ chơi có số lượng khác nhau trong hai nhóm.
Yêu cầu: Đếm số nhóm đồ chơi An có thể tạo ra có số lượng món không nhỏ hơn ~S~ và không lớn hơn ~B~. Trong một nhóm, số lượng đồ chơi của một loại nào đó không được lớn hơn số lượng thực tế An có. Kết quả lấy số dư trong phép chia cho 1,000,000.
Input
- Dòng đầu chứa 4 số nguyên: ~T, A, S, B~ — số loại đồ chơi, tổng số đồ chơi, giới hạn nhỏ nhất và lớn nhất số món trong một nhóm (~1 \le T \le 1000; 1 \le S \le B \le A~).
- ~A~ dòng tiếp theo, mỗi dòng chứa một số nguyên từ 1 đến ~T~ — biểu thị loại của từng món đồ chơi.
Output
Một dòng duy nhất là số nhóm đồ chơi có kích thước từ ~S~ đến ~B~, chia dư cho 1,000,000.
Sample Input 1
3 5 2 3
1
2
2
1
3
Sample Output 1
10
Subtasks
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 20% | ~A \le 20~ |
| 2 | 30% | ~A \le 100~ |
| 3 | 50% | Không có ràng buộc bổ sung |
Bình luận
giới hạn của A là gì vậy ạ?