Xâu ở giữa
Đề bài
Mô tả
Hôm nay, trong môn học thuật toán, Hạnh được học về thứ tự từ điển.
Giáo sư giao cho Hạnh một bài toán đếm: cho hai xâu , và một số nguyên , đếm số xâu có độ dài sao cho lớn hơn và nhỏ hơn theo thứ tự từ điển.
Bài toán này khá đơn giản với Hạnh. Bạn ấy viết ngay được hàm countBetween(a, b, l, p) hoạt động như sau:
- Hàm có bốn tham số: và là hai xâu gồm các chữ cái tiếng Anh in thường, và là hai số nguyên dương.
- Hàm đếm chính xác số xâu gồm đúng chữ cái tiếng Anh in thường thoả mãn theo thứ tự từ điển.
- Hàm trả về một số nguyên không âm là số dư khi chia số xâu như vậy cho .
Để bài toán thú vị và thử thách hơn, giáo sư yêu cầu Hạnh xử lý nhiều truy vấn đếm xâu nằm giữa. Để giải bài toán khó hơn này, Hạnh viết mã giả sau:
function solve(s, w, d, p):
a = "icpcvn"
b = "icpcvn"
res = 0
for each i from 0 to length(s) - 1:
if w[i] equals 'A':
insert character s[i] at the end of string a
else:
insert character s[i] at the end of string b
sum = 0
for each integer l in d:
sum += countBetween(a, b, l, p)
res = res xor (sum % p * (i + 1))
return res
Hàm solve nhận bốn tham số:
- Hai xâu và có cùng độ dài; chỉ gồm các chữ cái tiếng Anh in thường, chỉ gồm các ký tự
AvàB. - là một dãy các số nguyên dương.
- là một số nguyên dương.
Trong mã giả trên, length(s) là số ký tự của xâu , còn s[i] là ký tự thứ của xâu ; các ký tự được đánh số từ . Phép xor là phép XOR theo bit, và sum % p * (i + 1) được tính là .
Đáng tiếc, Hạnh nhận ra chương trình của mình có thể chạy quá chậm với một số bộ dữ liệu của giáo sư. Vì vậy, Hạnh nhờ bạn viết chương trình tính nhanh giá trị trả về của hàm trên khi biết giá trị của tất cả các tham số.
Nhắc lại, xâu được gọi là nhỏ hơn xâu theo thứ tự từ điển khi và chỉ khi một trong hai điều kiện sau thoả mãn:
- và với mọi ;
- tồn tại chỉ số sao cho , và với mọi .
Xâu được gọi là lớn hơn xâu theo thứ tự từ điển khi và chỉ khi nhỏ hơn theo thứ tự từ điển.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và (, , ): độ dài của các tham số và , số phần tử của tham số và giá trị của tham số .
- Dòng thứ hai chứa số nguyên (): các phần tử của tham số .
- Dòng thứ ba chứa một xâu gồm đúng chữ cái tiếng Anh in thường: tham số .
- Dòng thứ tư chứa một xâu gồm đúng ký tự
AvàB: tham số .
Dữ liệu ra
In ra một số nguyên duy nhất là giá trị trả về của hàm solve ở trên.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 45 6 7 8 ca BA |
25 | Ban đầu icpcvn. Khi : icpcvn, icpcvnc; có xâu độ dài , xâu độ dài (icpcvna, icpcvnb) và xâu độ dài (icpcvnaa tới icpcvnbz) nằm giữa, , nên và . Khi : icpcvna, icpcvnc; các giá trị lần lượt là , (icpcvnb) và , nên và . |
| 5 5 1000000000 7 8 9 8 1000000000 zbbaa BBAAB |
6279498621 | Ví dụ bổ sung. Ở mọi bước : sau hai bước đầu icpcvn là tiền tố của icpcvnzb, sau đó bắt đầu bằng icpcvnb còn bắt đầu bằng icpcvnz. |
Bình luận