trang chủ / đề bài / icpc21_reg_j

Ghép xâu

Đề bài

Mô tả

Cho xâu f0 có không quá 1000 ký tự. Bạn cần xử lý q truy vấn, truy vấn thứ i (1≤i≤q) thuộc một trong các loại sau:

  • 1 u c: tạo xâu mới fi bằng cách thêm ký tự c vào cuối xâu fu, tức là fi=fu+c.
  • 2 u c: tạo xâu mới fi bằng cách thêm ký tự c vào đầu xâu fu, tức là fi=c+fu.
  • 3 u v: tạo xâu mới fi bằng cách nối hai xâu fu và fv, tức là fi=fu+fv.
  • 4 u: tạo xâu mới fi là xâu đảo ngược của fu, tức là fi=reverse(fu).
  • 5 u v: đặt fi=fi−1. Xét mọi xâu có dạng prefix(fu)+suffix(fv), trong đó prefix(fu) là một tiền tố khác rỗng của fu và suffix(fv) là một hậu tố khác rỗng của fv. Hãy đếm số xâu phân biệt trong số đó.

Lưu ý rằng ở truy vấn thứ i ta luôn tạo ra một xâu mới fi, còn mọi xâu đã tạo trước đó vẫn giữ nguyên.

Dữ liệu vào

  • Dòng đầu tiên chứa xâu khác rỗng f0 gồm không quá 1000 chữ cái tiếng Anh in thường.
  • Dòng thứ hai chứa số nguyên q, số truy vấn.
  • q dòng tiếp theo, dòng thứ i mô tả truy vấn thứ i theo một trong năm loại ở trên. Mọi tham số của truy vấn thứ i thỏa mãn 0≤u,v<i, và c là một chữ cái tiếng Anh in thường.

Dữ liệu ra

Với mỗi truy vấn loại 5, in ra một dòng chứa số xâu phân biệt. Vì số này có thể rất lớn, hãy in ra phần dư của nó khi chia cho 109+7.

Ràng buộc

  • 1≤|f0|≤1000.
  • 1≤q≤105.
  • 0≤u,v<i với truy vấn thứ i.

Ví dụ

Input Output Giải thích
ab
5
1 0 z
2 0 y
3 1 0
4 2
5 2 4
7 Các xâu được tạo: f0=ab, f1=abz, f2=yab, f3=abzab, f4=bay, f5=bay. Ở truy vấn thứ 5, các tiền tố của f2 là y, ya, yab; các hậu tố của f4 là y, ay, bay. Ghép lại được 9 xâu: yy, yay, ybay, yay, yaay, yabay, yaby, yabay, yabbay, trong đó có 7 xâu phân biệt.
a
5
5 0 0
1 1 a
5 2 2
4 3
5 4 0
1
3
2
Ví dụ bổ sung (không có trong đề gốc). f1=a, f2=aa, f3=aa, f4=aa, f5=aa. Với f2 và f2 ta được các xâu aa, aaa, aaaa. Với f4=aa và f0=a ta được aa, aaa.

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