Ống dẫn quỹ đạo kín
Đề bài
Mô tả
Sâu bên trong lõi năng lượng của Khu vực 2026, một ống dẫn vòng quỹ đạo gồm bến neo được xếp dọc theo một đường ray tròn một chiều, đánh số theo chiều kim đồng hồ từ đến . Ngay sau bến theo chiều kim đồng hồ là bến .
Có hộp nhiên liệu dạng mô-đun với các nhãn định danh phân biệt . Ban đầu, hộp neo tại bến , và bến neo đích của nó là .
Một nhịp cơ khí chọn đúng một hộp và đẩy nó tiến thêm một bến theo chiều kim đồng hồ. Một nhịp là hợp lệ khi và chỉ khi bến đến đang trống. Các hộp không bao giờ di chuyển ngược chiều kim đồng hồ.
Một nhật ký vận hành hoàn chỉnh là một dãy gồm đúng nhịp hợp lệ mà sau đó mọi hộp đều nằm tại bến đích của mình. Hai nhật ký hoàn chỉnh được coi là khác nhau khi và chỉ khi dãy nhãn hộp được chọn của chúng khác nhau.
Gọi dãy nhãn được chọn là . Độ căng của bảng điều khiển ứng với nhật ký được định nghĩa là:
Nghĩa là, sau nhịp thứ , bảng điều khiển tích thêm đơn vị độ căng mỗi khi nhịp tiếp theo kích hoạt một hộp có nhãn nhỏ hơn hẳn. (Với , độ căng luôn bằng .)
Trọng số năng lượng của một nhật ký hoàn chỉnh là .
Cấu hình ban đầu và cấu hình đích có cùng một vết cắt vòng: liệt kê các bến có hộp theo thứ tự số hiệu giảm ngặt thì nhận được các nhãn . Tức là và .
Hãy tính tổng trọng số của tất cả các nhật ký hoàn chỉnh hợp lệ, theo modulo . Nếu , ứng viên duy nhất là nhật ký rỗng, nó đóng góp trọng số khi và chỉ khi cấu hình ban đầu và cấu hình đích đã trùng nhau (và đóng góp trong trường hợp ngược lại).
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và (, , , ).
- Dòng thứ hai chứa số nguyên giảm ngặt .
- Dòng thứ ba chứa số nguyên giảm ngặt .
Dữ liệu ra
In ra một số nguyên duy nhất: tổng có trọng số của tất cả các nhật ký hoàn chỉnh, theo modulo . Nếu không tồn tại nhật ký hoàn chỉnh nào, in ra .
Ràng buộc
- , , .
- .
- và .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 6 1 0 1 0 |
531441 | Chỉ có một bến trống nên nhật ký hoàn chỉnh duy nhất là . Các lần giảm xảy ra sau nhịp và nhịp , nên độ căng là . Trọng số là . |
| 5 2 12 3 0 4 1 |
214993899 | Mỗi hộp phải đi đúng bến (một vòng cộng thêm một bến). |
| 8 3 3 3 2 1 4 3 2 |
1 | Ba hộp nằm liền nhau nên phải đi theo thứ tự ; không có lần giảm nào, trọng số . |
Bình luận