Câu đố tủ khóa II
Đề bài
Mô tả
Bài này là phiên bản ngẫu nhiên của bài Câu đố tủ khóa I, có nội dung như sau.
Một căn phòng có chiếc tủ khóa, được đánh số từ đến . Mỗi tủ đang ở trạng thái mở hoặc đóng. Một nhóm gồm người thừa kế phải giải một câu đố với các tủ này trước khi được nhận tài sản thừa kế.
Những người thừa kế cũng được đánh số từ đến . Ở mỗi bước, bạn được chọn một người thừa kế để thực hiện một thao tác. Khi người thừa kế thứ được chọn, người đó đảo trạng thái của mọi tủ có chỉ số là bội của . Cụ thể hơn, với mọi số nguyên dương sao cho , trạng thái của tủ thứ được đổi từ mở thành đóng hoặc ngược lại. Một người thừa kế có thể được chọn nhiều lần.
Câu đố được giải khi cả tủ đều đóng.
Hãy tìm một dãy thao tác đóng được tất cả các tủ, hoặc cho biết không tồn tại dãy như vậy.
Bối cảnh và luật chơi giống hệt Câu đố tủ khóa I, chỉ khác là bạn không còn được chọn người thừa kế thực hiện mỗi thao tác. Ở mỗi bước, đúng một người thừa kế được chọn ngẫu nhiên: người thừa kế thứ được chọn với xác suất . Các lựa chọn ở các bước khác nhau là độc lập. Quá trình dừng ngay khi tất cả các tủ đều đóng; nếu ban đầu mọi tủ đã đóng thì không có thao tác nào được thực hiện.
Hãy tính kỳ vọng số thao tác được thực hiện, tính cả thao tác làm cho mọi tủ đóng lại.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên (): số bộ dữ liệu.
Mỗi bộ dữ liệu gồm:
- Dòng đầu tiên chứa hai số nguyên và (, ): số tủ khóa và tổng tất cả các trọng số xác suất.
- Dòng thứ hai chứa số nguyên (): trạng thái ban đầu của các tủ, trong đó nghĩa là tủ thứ đang mở và nghĩa là tủ đó đang đóng.
- Dòng thứ ba chứa số nguyên (, ): ở mỗi bước, người thừa kế thứ được chọn với xác suất .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra kỳ vọng số thao tác theo modulo như định nghĩa dưới đây.
Có thể chứng minh rằng kỳ vọng số thao tác luôn là một số hữu tỉ. Hơn nữa, với các ràng buộc của bài, có thể chứng minh rằng nếu biểu diễn số hữu tỉ này dưới dạng phân số tối giản thì . Do đó tồn tại duy nhất số nguyên sao cho và . Hãy in ra .
Ràng buộc
- .
- , .
- .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 3 3 0 0 0 1 1 1 3 3 0 0 1 1 1 1 3 3 0 1 0 1 1 1 3 3 0 1 1 1 1 1 3 3 1 0 0 1 1 1 3 3 1 0 1 1 1 1 3 3 1 1 0 1 1 1 3 3 1 1 1 1 1 1 |
0 7 7 9 10 9 9 7 |
Ở bộ dữ liệu thứ nhất mọi tủ đã đóng nên quá trình dừng ngay và đáp án là . Ở bộ dữ liệu thứ hai chỉ có tủ đang mở. Nếu người thừa kế được chọn đầu tiên (xác suất ) thì câu đố được giải sau một thao tác; các lựa chọn khác mở thêm tủ và cần thêm thao tác. Xét mọi dãy lựa chọn ngẫu nhiên, kỳ vọng số thao tác là . |
| 3 7 67 1 0 0 0 0 1 1 6 7 6 7 6 7 28 11 12 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1 1 1 1 1 1 1 1 15 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 |
482862219 84701850 32767 |
Ở bộ dữ liệu thứ nhất, kỳ vọng số thao tác là . |
Bình luận