trang chủ / đề bài / icpc26_mb_g

Ố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 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ừ 0 đến M−1. Ngay sau bến x theo chiều kim đồng hồ là bến (x+1)modM.

Có r hộp nhiên liệu dạng mô-đun với các nhãn định danh phân biệt 1,2,…,r. Ban đầu, hộp i neo tại bến ai, và bến neo đích của nó là bi.

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 K nhịp hợp lệ mà sau đó mọi hộp đều nằm tại bến đích bi 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à w=(w1,w2,…,wK). Độ căng của bảng điều khiển ứng với nhật ký được định nghĩa là:

strain(w)=∑1≤h<Kwh>wh+1h.

Nghĩa là, sau nhịp thứ h, bảng điều khiển tích thêm h đơ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 r=1, độ căng luôn bằng 0.)

Trọng số năng lượng của một nhật ký hoàn chỉnh là 9strain(w).

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 1,2,…,r. Tức là M>a1>a2>…>ar≥0 và M>b1>b2>…>br≥0.

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 998244353. Nếu K=0, ứng viên duy nhất là nhật ký rỗng, nó đóng góp trọng số 1 khi và chỉ khi cấu hình ban đầu và cấu hình đích đã trùng nhau (và đóng góp 0 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 M, r và K (2≤M≤109, 1≤r≤5, r<M, 0≤K≤200000).
  • Dòng thứ hai chứa r số nguyên giảm ngặt a1,a2,…,ar.
  • Dòng thứ ba chứa r số nguyên giảm ngặt b1,b2,…,br.

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 998244353. Nếu không tồn tại nhật ký hoàn chỉnh nào, in ra 0.

Ràng buộc

  • 2≤M≤109, 1≤r≤5, r<M.
  • 0≤K≤200000.
  • M>a1>a2>…>ar≥0 và M>b1>b2>…>br≥0.

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à [1,2,1,2,1,2]. Các lần giảm xảy ra sau nhịp 2 và nhịp 4, nên độ căng là 2+4=6. Trọng số là 96=531441.
5 2 12
3 0
4 1
214993899 Mỗi hộp phải đi đúng 6 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ự [1,2,3]; không có lần giảm nào, trọng số 90=1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0