trang chủ / đề bài / icpc24_reg_h

Hash-shashin

Đề bài

Mô tả

Hashshashin, thường được biết đến với tên gọi Hội Sát thủ, là một giáo phái nổi tiếng với những, ờ, hoạt động bí mật nhắm vào đối thủ. Để thực hiện các hoạt động bí mật mà không bị thế giới bên ngoài phát hiện, các thành viên của hội, gọi là Sát thủ, thường liên lạc với nhau bằng những thông điệp được mã hóa nghiêm ngặt. Người gửi trước tiên chuyển thông điệp thành một xâu s độ dài n chỉ gồm các ký tự 0 và 1. Sau đó, người gửi tính một dãy, gọi là hash, định nghĩa như sau:

  • hash0=0;
  • hashi=(2·hashi−1+si)modm với mọi 1≤i≤n.

Ở đây si là ký tự thứ i (đánh số từ 1) của thông điệp nhị phân và m là một số nguyên dương được người gửi và người nhận thống nhất từ trước. Người gửi sau đó gửi dãy hash cho người nhận.

Dễ thấy thông điệp có thể được khôi phục nếu biết m, với điều kiện m≥3. Ngoài ra, để đảm bảo thông điệp không bị can thiệp, người gửi còn gửi riêng một xâu key độ dài n chứa kết quả so sánh giữa từng cặp phần tử liên tiếp của hash:

  • keyi là < nếu hashi−1<hashi;
  • keyi là = nếu hashi−1=hashi;
  • keyi là > nếu hashi−1>hashi.

Nhiệm vụ của bạn là giúp Altaïr, một Sát thủ kỳ cựu, trong chiến dịch bí mật sắp tới. Altaïr chờ một thông điệp từ người thầy Mualim vạch ra các mục tiêu tiếp theo. Tuy nhiên, anh chỉ nhận được key; thông điệp chứa dãy hash đã bị gián điệp đối phương chặn mất. Vì gửi lại thông điệp lúc này rõ ràng không an toàn, Altaïr muốn khôi phục được càng nhiều ký tự của thông điệp gốc càng tốt. Cụ thể, với mỗi vị trí i (1≤i≤n), Altaïr muốn biết si có giống nhau với mọi thông điệp s phù hợp với key nhận được hay không. Cũng có thể chính key đã bị sửa đổi và không tồn tại xâu s nào phù hợp, khi đó Altaïr cũng muốn được biết điều này. Hãy giúp anh!

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤10000): số bộ test. Mỗi bộ test gồm:

  • Dòng đầu tiên chứa hai số nguyên n, m (1≤n≤200000, 3≤m≤109): độ dài thông điệp gốc và số modulo đã thống nhất.
  • Dòng thứ hai chứa xâu key độ dài n, mỗi ký tự là <, = hoặc > như mô tả ở trên.

Dữ liệu đảm bảo tổng n trên tất cả các bộ test không vượt quá 200000.

Dữ liệu ra

Với mỗi bộ test, gọi S là tập tất cả các xâu nhị phân s phù hợp với key. Nếu S rỗng, in ra impossible. Ngược lại, in ra một xâu a độ dài n, trong đó:

  • ai là 0 nếu si=0 với mọi s∈S;
  • ai là 1 nếu si=1 với mọi s∈S;
  • ai là ? trong các trường hợp còn lại.

Ràng buộc

  • 1≤t≤10000
  • 1≤n≤200000, 3≤m≤109
  • Tổng n không vượt quá 200000.

Ví dụ

Input Output Giải thích
3
5 6
<<<>>
10 998244353
==<<<<<<<<
5 3
<>=<=
10???
001???????
impossible
Bộ test thứ nhất: với s=10101, dãy hash là 0,1,2,5,4,3 và key là <<<>>; các xâu phù hợp còn lại là 10010, 10011 và 10100. Bộ test thứ hai: mọi xâu độ dài 10 bắt đầu bằng 001 đều phù hợp. Bộ test thứ ba: có thể chứng minh không có xâu nào phù hợp.
2
3 3
<<=
4 5
<>>>
101
impossible
Bộ test thứ nhất: chỉ có s=101 với hash=0,1,2,2.

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