思路

定义 \(dp_{i,j}\) 表示区间 \([i,j]\) 中回文串的数量。那么，不难得出状态转移方程 \(dp_{i,j} = dp_{i - 1} + f_{i,j}\)。（其中 \(f_{i,j}\) 表示左端点大于等于 \(i\)，右端点为 \(j\) 的回文串数量）

由此，现在问题转变为了如何求 \(f_{i,j}\)。如果我们在求出了 \(f_{i + 1,j}\) 情况下，\(f_{i,j}\) 就等于 \(f_{i + 1,j}\) 再加上 \(s_{i \sim j}\) 是否是回文串。

判断回文串就很好求了，首先定义 \(st_{i,j} = 0/1\) 表示 \(s_{i \sim j}\) 不是/是 一个回文串。

然后，固定一个初始的点，然后向外扩展即可。即，对于 \(s_{i} = s_j\)，有 \(st_{i,j} = st_{i + 1,j - 1}\)。

Code

#include <bits/stdc++.h>  
#define re register  
  
using namespace std;  
  
const int N = 5010;  
int n,q;  
int f[N][N],dp[N][N];  
bool st[N][N];  
string s;  
  
int main(){  
    ios::sync_with_stdio(0);  
    cin.tie(0);  
    cout.tie(0);  
    cin >> s >> q;  
    n = s.length();  
    s = ' ' + s;  
    for (re int i = 0;i <= n + 1;i++){  
        for (re int j = 0;j <= n + 1;j++) st[i][j] = true;  
    }  
    for (re int i = n;i;i--){  
        for (re int j = i;j <= n;j++) st[i][j] = st[i + 1][j - 1] & (s[i] == s[j]);  
    }  
    for (re int j = 1;j <= n;j++){  
        for (re int i = j;i;i--) f[i][j] = f[i + 1][j] + st[i][j];  
    }  
    for (re int i = 1;i <= n;i++){  
        for (re int j = i;j <= n;j++) dp[i][j] = dp[i][j - 1] + f[i][j];  
    }  
    while (q--){  
        int l,r;  
        cin >> l >> r;  
        cout << dp[l][r] << "\n";  
    }  
    return 0;  
}