Kẹo nhiều màu
Đề bài
Mô tả
Bạn có một hũ kẹo ma thuật rất lớn gồm màu khác nhau. Các màu được đánh số từ đến , và ban đầu màu thứ có viên kẹo.
Chừng nào các viên kẹo trong hũ chưa cùng một màu, bạn thực hiện thao tác sau:
- Chọn hai viên kẹo khác màu, ngẫu nhiên đều trong tất cả các cặp kẹo như vậy.
- Sau đó, chọn một trong hai viên kẹo này, ngẫu nhiên đều, và đổi màu của nó thành màu của viên kẹo còn lại.
Hãy tìm kỳ vọng số thao tác được thực hiện cho đến khi tất cả các viên kẹo trong hũ có cùng một màu.
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu chứa số nguyên (), số màu.
Dòng thứ hai chứa số nguyên (), số viên kẹo của mỗi màu.
Dữ liệu đảm bảo tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra đáp án như sau:
- Nếu kỳ vọng số thao tác là vô hạn, in ra .
- Ngược lại, đặt . Có thể chứng minh rằng khi đó kỳ vọng số thao tác biểu diễn được dưới dạng phân số tối giản , trong đó , là các số nguyên và . In ra số nguyên bằng . Nói cách khác, in ra số nguyên sao cho và .
Ràng buộc
- .
- ; .
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 1 1 2 2 1 1 5 |
1 2 0 |
Bộ thứ nhất: có hai viên kẹo khác màu, sau một thao tác cả hai cùng màu, đáp án là . Bộ thứ hai: có hai viên màu 1 và một viên màu 2. Ở thao tác đầu tiên, cặp được chọn gồm viên màu 2 và một viên màu 1. Với xác suất , viên màu 2 đổi thành màu 1 và mọi viên kẹo cùng màu. Với xác suất , viên màu 1 đổi thành màu 2: khi đó có một viên màu 1 và hai viên màu 2, giống tình huống ban đầu với hai màu đổi chỗ. Vậy số thao tác tuân theo phân phối hình học với xác suất thành công , kỳ vọng là . Bộ thứ ba: mọi viên kẹo đã cùng màu nên không có thao tác nào. |
| 2 3 1 2 3 2 1000000000 1000000000 |
11 49 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: kỳ vọng số thao tác là . Bộ thứ hai: kỳ vọng là , phần dư khi chia cho là . |
Bình luận