Chuỗi đòn của Rain
Đề bài
Mô tả
Một trong những trò chơi đối kháng yêu thích của Rua là TODA2, trò chơi có một trong những giải đấu thể thao điện tử lớn nhất thế giới mang tên The Intergalactics (TI). TI 2025 vừa khép lại và khiến mọi người bất ngờ khi một trong những tuyển thủ xuất sắc nhất, Rain, lại một lần nữa lỡ hẹn với chức vô địch. Rain được mệnh danh là "Ông vua không ngai" vì chưa từng vô địch TI dù nhiều lần đến rất gần.
Trong TODA2, nhân vật Yug có một chiêu cuối nổi tiếng khó đoán vì phụ thuộc một phần vào may mắn. Trong ván đấu quyết định của cả loạt trận, Rain chọn Yug và để thua. Là một fan của TODA2, Rua quyết định tìm hiểu cơ chế chiêu cuối của Yug.
Chiêu cuối của Yug hoạt động như sau. Yug chọn một mục tiêu trong bán kính quanh mình, dịch chuyển tức thời đến vị trí của mục tiêu đó (đứng ngay trên mục tiêu) và đánh mục tiêu một lần. Sau đó Yug tiếp tục tìm mục tiêu kế tiếp trong bán kính quanh vị trí mới, kể cả những mục tiêu đã bị đánh, chọn ngẫu nhiên một mục tiêu, dịch chuyển đến đó và đánh một lần. Quá trình lặp lại cho đến khi Yug đã đánh đủ lần hoặc không tìm được mục tiêu nào.
Để đơn giản, thay vì Yug tự chọn mục tiêu đầu tiên, ta coi như Yug chọn ngẫu nhiên một mục tiêu trong tầm từ vị trí ban đầu, tức là bước chọn mục tiêu đầu tiên cũng là một thao tác "Tìm". Như vậy chiêu cuối là một dãy: Tìm Dịch chuyển Đánh Tìm Dịch chuyển Đánh , kết thúc khi đã có lần Đánh.
Khi "Tìm", Yug xét mọi mục tiêu cách vị trí hiện tại không quá : nếu Yug đứng ở thì mục tiêu ở được xét khi
Các mục tiêu đứng yên trong suốt chiêu cuối.
Cho vị trí của Yug, số lần đánh và vị trí của mục tiêu. Hãy đếm số kịch bản khác nhau mà mục tiêu thứ bị đánh ít nhất lần trong chiêu cuối, và tổng số kịch bản khác nhau có thể xảy ra. Hai kịch bản được coi là khác nhau nếu có ít nhất một bước trong dãy đánh mà Yug đánh vào hai mục tiêu khác nhau. Vì kết quả có thể rất lớn, hãy in theo modulo .
Dữ liệu vào
- Dòng đầu tiên gồm bốn số nguyên , , , .
- Dòng thứ hai gồm số nguyên .
- Dòng thứ trong dòng tiếp theo gồm hai số nguyên , : vị trí của mục tiêu thứ .
- Dòng cuối cùng gồm hai số nguyên và .
Dữ liệu ra
Gọi là số kịch bản khác nhau mà mục tiêu thứ bị đánh ít nhất lần, là tổng số kịch bản khác nhau có thể xảy ra khi Yug dùng chiêu cuối. In ra hai số nguyên và trên một dòng, cách nhau một dấu cách, mỗi số lấy theo modulo .
Ràng buộc
- , , .
- ; .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 1 3 3 3 3 4 4 3 3 2 |
1 9 | Lần đánh đầu chỉ có thể vào mục tiêu ; mỗi lần sau có thể vào mục tiêu , hoặc . Có kịch bản: , , , , , , , , ; chỉ đánh mục tiêu ít nhất lần. |
| 3 3 1 1 3 4 4 3 4 4 3 3 1 |
0 1 | Từ vị trí ban đầu Yug không với tới mục tiêu nào, nên kịch bản duy nhất là không đánh gì; mục tiêu không thể bị đánh ít nhất lần. |
| 8 2 1 1 3 2 1 1 2 9 9 3 2 |
0 256 | Mỗi lần đánh có thể vào mục tiêu hoặc , nên có kịch bản; mục tiêu không bao giờ bị đánh. |
Bình luận