trang chủ / đề bài / icpc22_mn_d

Vừng ơi, mở ra!

Đề bài

Mô tả

Các nhà khảo cổ tìm thấy một kho báu được chôn sâu trong thế giới Atlantis. Tuy nhiên, kho báu này được bảo vệ bởi nhiều lớp mật mã và mỗi lớp ứng với một con số. Sau nhiều năm nghiên cứu, các nhà khảo cổ đã tìm ra một xâu S cùng với các gợi ý để tìm mật khẩu trong một cuốn sách bí ẩn.

Cụ thể, lớp mật mã thứ i có một con số ma thuật k, và mật mã là kết quả của hàm f(wk), trong đó wk là xâu con đối xứng (palindrome) nhỏ thứ k theo thứ tự từ điển của S. Hàm f được định nghĩa là

f(p)=(∑i=1|p|pi×a|p|−i)modm

trong đó pi là mã ASCII của ký tự thứ i của xâu p, a=100001 và m=109+7.

Các xâu con đối xứng được tính theo từng lần xuất hiện: hai xâu con ở hai vị trí khác nhau được tính là hai xâu con khác nhau dù chúng bằng nhau.

Tuy nhiên, qua nhiều năm, một số chỗ trong sách đã bị mờ khiến wk không tồn tại; khi đó đáp án là −1.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên N (độ dài xâu S) và Q (số lớp mật mã).
  • Dòng thứ hai chứa xâu S chỉ gồm các chữ cái tiếng Anh in thường (từ a đến z).
  • Mỗi dòng trong Q dòng tiếp theo chứa một số nguyên K của một lớp.

Dữ liệu ra

Với mỗi lớp, in ra mật khẩu nếu con số K trong sách là đúng; ngược lại in ra −1.

Ràng buộc

  • 1≤N,Q≤105
  • 1≤K≤N×(N+1)/2

Ví dụ

Input Output Giải thích
5 7
abcba
1
2
3
4
6
7
8
97
97
696207567
98
29493435
99
-1
Các xâu con đối xứng theo thứ tự: a, a, abcba, b, b, bcb, c. Không có xâu thứ 8.
5 11
aabaa
1
2
3
4
5
6
7
8
9
10
11
97
97
97
97
9700194
9700194
702607844
29193502
98
-1
-1
Ví dụ bổ sung (không có trong đề gốc). Các xâu con đối xứng theo thứ tự: a, a, a, a, aa, aa, aabaa, aba, b; f(aa)=97·100001+97=9700194.

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