IOI 2008 - Fish
Xem PDFScheherazade kể rằng ở một nơi xa xôi giữa sa mạc có một hồ nước. Ban đầu, hồ có \(F\) con cá. Người ta chọn ra \(K\) loại đá quý trong số những loại quý giá nhất trên Trái Đất và cho mỗi con cá nuốt đúng một viên đá quý. Vì \(K\) có thể nhỏ hơn \(F\), hai hoặc nhiều con cá có thể nuốt đá quý cùng loại.
Theo thời gian, một số con cá đã ăn những con cá khác. Một con cá có thể ăn một con khác khi và chỉ khi chiều dài của nó ít nhất gấp đôi chiều dài con kia: cá \(A\) có thể ăn cá \(B\) khi và chỉ khi \(L_A \ge 2L_B\). Không có quy định về thời điểm cá quyết định ăn. Một con cá có thể lần lượt ăn nhiều con cá nhỏ hơn, trong khi một số con có thể không ăn con nào dù có khả năng ăn. Khi một con cá ăn một con nhỏ hơn, chiều dài của nó không thay đổi, nhưng tất cả đá quý trong bụng con cá nhỏ hơn được chuyển nguyên vẹn vào bụng nó.
Scheherazade nói rằng nếu tìm được hồ, bạn sẽ được bắt đúng một con cá và giữ lại tất cả đá quý trong bụng nó. Bạn muốn thử vận may, nhưng trước khi lên đường, bạn muốn biết có bao nhiêu tổ hợp đá quý khác nhau có thể thu được khi bắt một con cá.
Cho chiều dài mỗi con cá và loại đá quý mà nó nuốt ban đầu, hãy tính số tổ hợp đá quý khác nhau có thể xuất hiện trong bụng một con cá bất kỳ, lấy phần dư khi chia cho số nguyên \(M\) đã cho. Một tổ hợp chỉ được xác định bởi số lượng đá quý thuộc từng loại trong \(K\) loại. Thứ tự các viên đá không có ý nghĩa, và hai viên đá cùng loại không thể phân biệt với nhau.
Dữ liệu vào
Đọc từ đầu vào chuẩn:
- Dòng thứ nhất chứa số nguyên \(F\), là số cá ban đầu trong hồ.
- Dòng thứ hai chứa số nguyên \(K\), là số loại đá quý. Các loại đá quý được đánh số từ \(1\) đến \(K\).
- Dòng thứ ba chứa số nguyên \(M\).
- Mỗi dòng trong \(F\) dòng tiếp theo mô tả một con cá bằng hai số nguyên cách nhau bởi một dấu cách: chiều dài của con cá, tiếp theo là loại đá quý mà nó nuốt ban đầu.
Dữ liệu bảo đảm ban đầu có ít nhất một viên đá quý thuộc mỗi loại trong \(K\) loại.
Dữ liệu ra
Ghi ra đầu ra chuẩn một dòng chứa một số nguyên trong đoạn \([0,M-1]\): phần dư khi chia số tổ hợp đá quý khác nhau có thể thu được cho \(M\).
Giá trị \(M\) chỉ được dùng để đơn giản hóa việc tính toán bằng cách lấy phần dư; nó không ảnh hưởng đến những tổ hợp nào có thể thu được.
Ràng buộc
- \(1 \le F \le 500\,000\).
- \(1 \le K \le F\).
- \(2 \le M \le 30\,000\).
- \(1 \le L_X \le 1\,000\,000\,000\) với mỗi con cá \(X\).
- Loại đá quý ban đầu của mỗi con cá thuộc đoạn \([1,K]\), và mỗi loại xuất hiện ít nhất một lần.
Chấm điểm trên hệ thống
Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.
Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.
Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.
| Nhãn nhóm | Điểm | Tệp dữ liệu vào gốc |
|---|---|---|
| 1 | 5 | fsh/fsh1apf.in |
| 2 | 5 | fsh/fsh2a.in |
| 3 | 5 | fsh/fsh3a.in |
| 4 | 5 | fsh/fsh4a.in |
| 5 | 5 | fsh/fsh5a.in, fsh/fsh5b.in |
| 6 | 5 | fsh/fsh6apf.in, fsh/fsh6bpf.in |
| 7 | 5 | fsh/fsh7a.in |
| 8 | 5 | fsh/fsh8a.in |
| 9 | 6 | fsh/fsh9a.in, fsh/fsh9b.in |
| 10 | 6 | fsh/fsh10a.in, fsh/fsh10b.in, fsh/fsh10c.in |
| 11 | 6 | fsh/fsh11apf.in, fsh/fsh11bpf.in, fsh/fsh11cpf.in |
| 12 | 6 | fsh/fsh12a.in, fsh/fsh12b.in |
| 13 | 6 | fsh/fsh13a.in, fsh/fsh13b.in |
| 14 | 5 | fsh/fsh14a.in |
| 15 | 5 | fsh/fsh15a.in |
| 16 | 5 | fsh/fsh16a.in, fsh/fsh16b.in |
| 17 | 5 | fsh/fsh17apf.in, fsh/fsh17bpf.in |
| 18 | 5 | fsh/fsh18a.in, fsh/fsh18b.in, fsh/fsh18c.in, fsh/fsh18d.in |
| 19 | 5 | fsh/fsh19a.in, fsh/fsh19b.in, fsh/fsh19c.in, fsh/fsh19d.in |
Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.
Tệp ví dụ gốc: fsh/fsh0.in.
Ví dụ
Ví dụ 1
Input
5
3
7
2 2
5 1
8 3
4 1
2 3Output
4Note
Có \(11\) tổ hợp có thể thu được, nên cần in \(11 \bmod 7=4\).
Các tổ hợp đó là \([1]\), \([1,2]\), \([1,2,3]\), \([1,2,3,3]\), \([1,3]\), \([1,3,3]\), \([2]\), \([2,3]\), \([2,3,3]\), \([3]\) và \([3,3]\).
Với mỗi tổ hợp, danh sách ghi các loại đá quý có trong tổ hợp đó. Chẳng hạn, \([2,3,3]\) gồm một viên đá loại \(2\) và hai viên đá loại \(3\).
Đánh số các con cá theo thứ tự xuất hiện trong dữ liệu vào. Có thể thu được các tổ hợp trên như sau:
- \([1]\): bắt con cá thứ hai hoặc thứ tư trước khi nó ăn bất kỳ con cá nào khác.
- \([1,2]\): con cá thứ hai ăn con thứ nhất. Khi đó nó có một viên đá loại \(1\) đã nuốt ban đầu và một viên đá loại \(2\) lấy từ bụng con thứ nhất; bắt con thứ hai.
- \([1,2,3]\): con thứ tư ăn con thứ nhất, rồi con thứ ba ăn con thứ tư. Bắt con thứ ba, trong bụng nó sẽ có một viên đá thuộc mỗi loại.
- \([1,2,3,3]\): con thứ tư ăn con thứ nhất, con thứ ba ăn con thứ tư, rồi con thứ ba ăn con thứ năm; bắt con thứ ba.
- \([1,3]\): con thứ ba ăn con thứ tư; bắt con thứ ba.
- \([1,3,3]\): con thứ ba ăn con thứ năm, rồi ăn con thứ tư; bắt con thứ ba.
- \([2]\): bắt con thứ nhất.
- \([2,3]\): con thứ ba ăn con thứ nhất; bắt con thứ ba.
- \([2,3,3]\): con thứ ba ăn con thứ nhất, rồi ăn con thứ năm; bắt con thứ ba.
- \([3]\): bắt con thứ ba.
- \([3,3]\): con thứ ba ăn con thứ năm; bắt con thứ ba.
Nguồn
Kỳ thi:
- IOI 2008 - Ngày 1 (18 Tháng 8., 2008)
Bình luận