Subtask ~1~: Duyệt trâu

Subtask ~2~ và ~3~:

Ta có thể quy về bài toán đếm số bộ ~(i,j,k,t)~ thỏa mãn:

• ~1 \leq i \leq j < k \leq t \leq n~.

• Xâu ~S[i...j]+S[k...t]~ là palindrome.

Sẽ có ~3~ trường hợp xảy ra:

TH1: ~j-i>t-k~

Gọi ~pos~ là vị trí thỏa mãn:

• ~i \leq pos \leq j~.

• ~pos-i=t-k~.

Để xâu ~S[i...j]+S[k...t]~ là một palindrome thì ta phải có:

• ~S[i...pos]+S[k...t]~ là palindrome.

• ~S[(pos+1)...j]~ là palindrome.

Gọi ~dp[i][j]=l~ lớn nhất sao cho ~S[(i-l+1)...i]+S[j...(j+l-1)]~ là palindrome. Tính ~dp[i][j]~ mất độ phức tạp ~O(n^2)~.

Gọi ~sl[i][j]~ là số lượng cặp ~(i,u)(i\leq u \leq j)~ thỏa mãn ~S[i...u]~ là palindrome. Tính ~sl[i][j]~ mất độ phức tạp ~O(n^2)~.

Với mỗi cặp ~(pos,k)~, kết quả sẽ cộng vào ~dp[pos][k]*sl[pos+1][k-1]~. Duyệt qua các cặp ~(pos,k)~ mất độ phức tạp ~O(n^2)~.

TH2: ~j-i<t-k~</p>

Làm tương tự TH1.

TH3: ~j-i=t-k~

Chỉ cần tính tổng các ~dp[pos][k]~.

Độ phức tạp: ~O(n^2)~.

#include <bits/stdc++.h>

using namespace std;
int n;
string s;
bool ok[5005][5005];//ok[i][j] de kiem tra xem xau tu i den j co phai la xau palindrome khong
int dp[5005][5005];//dp[i][j] la l lon nhat sao cho xau s[i-l+1...i]=s[j...j+l-1]
int cnt1[5005][5005];//cnt1[i][j] la so luong vi tri u(i<=u<=j) sao cho xau s[i...u] la xau doi xung
int cnt2[5005][5005];//cnt2[i][j] la so luong vi tri u(i<=u<=j) sao cho xau s[u...j] la xau doi xung
long long ans=0;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("vastr.inp", "r", stdin);
    freopen("vastr.out", "w", stdout);
    cin>>n;
    cin>>s;
    s=" "+s;
    for(int i=1; i<=n; i++)ok[i][i]=1;
    for(int i=1; i<n; i++)if(s[i]==s[i+1])ok[i][i+1]=1;
    for(int i=n; i>=1; i--)
        for(int j=i+2; j<=n; j++)
            if(s[i]==s[j]&&ok[i+1][j-1]==1)ok[i][j]=1;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            if(s[i]==s[j])dp[i][j]=1;
    for(int i=1; i<=n; i++)
        for(int j=n; j>i; j--)
            if(s[i]==s[j]) {
                dp[i][j]=max(dp[i][j],dp[i-1][j+1]+1);
            } else dp[i][j]=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cnt1[i][j]=cnt1[i][j-1]+ok[i][j];
    for(int i=1; i<=n; i++)
        for(int u=i; u>=1; u--)
            cnt2[u][i]=cnt2[u+1][i]+ok[u][i];
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++) {
            ans+=dp[i][j];
            ans+=1LL*dp[i-1][j+1]*(cnt1[i][j]+cnt2[i][j]);
        }
    cout<<ans;
    return 0;
}