Alice cuồng nộ
Đề bài
Mô tả
Vừa học được một kỹ năng mới rất mạnh tên là "Cuồng nộ" (Rage Rush), Alice lập tức tới sân tập để làm quen với nó.
Kỹ năng này hoạt động khá đặc biệt. Giả sử khi Alice dùng kỹ năng, đang có quái vật Marchen còn sống với lượng máu lần lượt là (một quái vật còn sống nếu nó còn ít nhất máu). Khi đó:
- Đầu tiên, một Marchen trong con còn sống được chọn với xác suất tỉ lệ với lượng máu hiện tại của nó. Nói cách khác, xác suất chọn Marchen thứ là .
- Sau đó, một số nguyên trong đoạn được chọn, mỗi số có xác suất như nhau, và máu của Marchen được chọn giảm đi đúng số đó. Nếu Marchen có ít máu hơn số bị trừ, phần sát thương dư bị lãng phí (không chuyển sang Marchen nào khác).
Trong sân tập, Alice dựng hình nộm Marchen với lượng máu ban đầu là . Chúng không đánh trả nên Alice có thể tập bao lâu tùy thích.
Nếu Alice chỉ dùng "Cuồng nộ" để tấn công, hãy tính kỳ vọng số lần Alice dùng kỹ năng cho tới khi tất cả hình nộm đều chết.
Đặt . Có thể chứng minh đáp án biểu diễn được dưới dạng phân số tối giản với . Hãy in ra số nguyên thỏa mãn và .
Dữ liệu vào
Dòng đầu tiên chứa số bộ test (). Tiếp theo là mô tả các bộ test.
- Dòng đầu tiên của mỗi bộ test chứa số nguyên (): số hình nộm.
- Dòng thứ hai chứa số nguyên (): lượng máu ban đầu của các hình nộm.
Dữ liệu đảm bảo tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một số nguyên: kỳ vọng số lần Alice dùng kỹ năng để hạ hết các hình nộm, lấy modulo .
Ràng buộc
- , tổng trên tất cả các bộ test không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 3 5 3 3 4 5 5 1 4 2 9 5 |
665496238 4 665496243 |
Bộ test thứ nhất: máu ban đầu là . Chẳng hạn kịch bản "Marchen 1 về , Marchen 2 mất máu, Marchen 2 về " có xác suất và dùng lần kỹ năng. Cộng tất cả kịch bản có thể, kỳ vọng là , và . |
| 3 1 1 1 6 2 6 10 |
1 2 36972018 |
Một hình nộm máu chết sau đúng lần. Hình nộm máu luôn cần đúng lần. Bộ test thứ ba có kỳ vọng . |
Bình luận