Bài 3. Hoa đẹp (HSG THPT Nghệ An 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Nghệ An 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nhà Tuấn có một hàng ~N~ chậu hoa đơn sắc. Hàng ngày ngắm nhìn hàng chậu hoa, Tuấn thấy rằng nếu các chậu hoa được đặt cùng màu nằm về cùng một phía (nửa trái hoặc nửa phải) của hàng thì sẽ rất đẹp.

Dãy màu các chậu hoa đã được biểu diễn thành một xâu ~S~ có độ dài chẵn ~N~ chứa các kí tự latin thường hoặc in hoa được đánh chỉ số từ 1 đến ~N~. Xâu ~S~ được gọi là xâu đẹp nếu tất cả các kí tự giống nhau của xâu ~S~ đều cùng nằm về nửa trái hoặc nửa phải của xâu. Ví dụ xâu "abcd", "AbaB" là các xâu đẹp, còn "aaaa" hay "Bbba" thì không.

Bạn phải thực hiện ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~x, y (1 \le x, y \le N)~. Đưa ra số lượng xâu ~T~ thỏa mãn: ~T~ là một hoán vị của ~S; T~ là một xâu đẹp; kí tự ~S_x~ và ~S_y~ phải nằm cùng về một phía (có thể trái hoặc phải) trong xâu ~T~.

Dữ liệu vào

Gồm các dòng:

  • Dòng 1: Chứa xâu ~S~ có độ dài ~N (N \le 10^5)~.
  • Dòng 2: Chứa số nguyên dương ~Q (Q \le 10^5)~.
  • ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x, y (x, y \le N)~.

Kết quả

Gồm ~Q~ dòng, mỗi dòng trả lời cho mỗi truy vấn, kết quả chia lấy dư cho ~10^9 + 7~.

Ví dụ

Input 1

Abdb
2
1 3
1 2

Output 1

4
0

Với ~S =~ "Abdb" (số lượng: ~A \times 1, b \times 2, d \times 1~), có hai cách chia nửa hợp lệ: nửa trái là ~\{b\}~ hoặc nửa trái là ~\{A, d\}~. Truy vấn 1 hỏi hai kí tự ~'A'~ và ~'d' -~ cả hai cách chia đều xếp chúng cùng phía, cho 4 xâu. Truy vấn 2 hỏi ~'A'~ và ~'b' -~ không cách chia nào xếp được chúng cùng phía, cho 0.

Ràng buộc

  • Subtask 1 (20% số điểm): ~Q = 1, 0 < N \le 10^3~.
  • Subtask 2 (80% số điểm): ~1 < Q \le 10^3, 0 < N \le 10^5~.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...