Mạch điện
Đề bài
Mô tả
Cho một mạch điện gồm một dãy vô hạn công tắc xếp thành một hàng, được đánh số từ trái sang phải bắt đầu từ .
Mỗi công tắc ở một trong hai trạng thái: BẬT (đóng) hoặc TẮT (mở). Ban đầu tất cả công tắc đều TẮT.
Quy tắc tương tác giữa các công tắc kề nhau như sau:
- Nếu một công tắc chuyển từ TẮT sang BẬT, nó không ảnh hưởng đến công tắc nào khác.
- Nếu một công tắc chuyển từ BẬT sang TẮT, nó làm công tắc ngay bên phải nó đảo trạng thái hiện tại (BẬT thành TẮT hoặc TẮT thành BẬT).
Bạn dự định thực hiện thao tác. Thao tác thứ đảo trạng thái của công tắc ():
- Nếu công tắc đang BẬT, nó trở thành TẮT (và có thể gây ra phản ứng dây chuyền sang phải theo quy tắc trên).
- Nếu công tắc đang TẮT, nó trở thành BẬT.
Chi phí của một thao tác là số công tắc bị thay đổi trạng thái (tính cả công tắc được đảo trực tiếp và các công tắc bên phải bị ảnh hưởng do lan truyền).
Tuy nhiên, mỗi thao tác chỉ được thực hiện với một xác suất nhất định:
- Thao tác thứ được thực hiện với xác suất .
- Ngược lại, nó bị bỏ qua với xác suất .
Các thao tác được xét lần lượt theo thứ tự từ đến . Hãy tính kỳ vọng của tổng chi phí của cả thao tác.
Gọi giá trị kỳ vọng là , trong đó và là hai số nguyên nguyên tố cùng nhau. Hãy in ra giá trị , trong đó là nghịch đảo modulo của theo modulo .
Lưu ý: số công tắc là vô hạn, chỉ là cận trên của các trong dữ liệu vào.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên , (): cận trên của các và số thao tác.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên , , (, , , ): vị trí công tắc và xác suất thực hiện thao tác thứ dưới dạng phân số .
Dữ liệu ra
In ra một số nguyên duy nhất: giá trị , với là kỳ vọng của tổng chi phí các thao tác.
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 0 1 2 1 1 2 2 1 2 |
499122178 | Mỗi thao tác được thực hiện với xác suất và ba thao tác đảo ba công tắc khác nhau đang TẮT, nên mỗi thao tác được thực hiện có chi phí . Kỳ vọng là , tức theo modulo. |
| 100 5 0 100 333 0 333 666 0 666 1234 1 1234 1235 2 1235 1236 |
610769569 | Ba thao tác đầu cùng đảo công tắc , nên khi nhiều thao tác được thực hiện sẽ có lan truyền sang các công tắc bên phải. |
Bình luận