Bedao OI Contest 5 - VASTR
Xem dạng PDF
Via là một học sinh xuất sắc chuẩn bị dự thi VOI 2024. Ngày qua ngày cậu vẫn chăm chỉ luyện đề cho đến một ngày cậu gặp một bài toán về xâu chưa giải quyết được nên muốn nhờ các bạn học sinh chuyên Tin giải quyết giúp cậu.
Đề bài cho Via một xâu ~S~ có độ dài ~n~. Ta quy ước một xâu được gọi là palindrome nếu xâu đó đối xứng (Tức là khi viết xâu đó từ phải sang trái cũng trùng với viết xâu đó từ trái sang phải).
Với ~i < j~ ta gọi mảng ~cp[i][j]~ là tổng số cặp ~u,v~ thỏa mãn:
~i \leq u < v \leq j~
Xâu ~S[i...u]+S[v...j]~ là một palindrome
Nếu không tồn tại ~u,v~ thì ~cp[i][j]=0~
Quy ước:
~S[a...b]~ là xâu ~S[a]S[a+1]...S[b]~
"+" là phép nối hai xâu
Gọi ~sum~ là tổng của ~cp[i][j]~ với tất cả các cặp ~i,j (i\leq j)~. Hãy tính ~sum~.
Input
Dữ liệu vào từ file văn bản vastr.inp:
Dòng đầu tiên chứa số nguyên ~n~.
Dòng thứ hai chứa một xâu ~S~ chứa ~n~ kí tự in thường.
Output
In ra file văn bản vastr.out một số nguyên duy nhất là giá trị của ~sum~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30~ | ~n \leq 50~ |
| 2 | ~20~ | ~n \leq 500~ |
| 3 | ~50~ | ~n \leq 5000~ |
Sample Input 1
5
abacc
Sample Output 1
4
Sample Input 2
6
baaabc
Sample Output 2
15
Notes
Với test ví dụ ~1~, ta có:
~cp[1][3]=3~
~cp[4][5]=1~
Còn lại tất cả đều bằng 0.
Nên đáp án là ~3+1=4~.
Bình luận
.