Bedao OI Contest 5 - VASTR

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: vastr.inp
Output: vastr.out

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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~.


Comments

Please read the guidelines before commenting.