CS Academy Distinct Palindromes

リンク : https://csacademy.com/contest/archive/task/distinct-palindromes/statement/

問題概要

文字列が与えられる。この文字列の部分文字列であり、回文であるのは何種類か求めよ。

解説

文字列をSとし、i番目の文字をS[i]とする。dp[l][r]をS[l]=S[r]=σであるときに、必ずlとrを回文に含む[l~r]間の回文の種類数とする。(l~r)の間に文字cが二つ以上存在するとき、(l~r)間にありlから最も近い文字cをc_l番目、rから最も近い文字cをc_r番目とする。σc...cσと取ることになる。dp[l][r]+=dp[c_l][c_r]となる。またこのσのときの間に一つしか文字がないときの場合は、a~zのそれぞれの文字について(l~r)間に存在すればdp[l][r]+=1する。最後にσσのみも考慮してdp[l][r]+=1する。これですべての遷移が終わった。実装する際にa~z以外の文字を番兵にすることで実装が楽になる。 下の図が具体例となる。$を番兵とする。答えに∅を回文として含んでしまうため-1をする。

これ典型なんですか？

kmjpさんのコードを参考にしました。

string str;
LL n;
LL dp[1010][1010], r[1010][30], l[1010][30];
LL func(int L, int R) {
    if (dp[L][R] != -1)return dp[L][R];
    LL ret = 1;
    rep(i, 26)if (r[L][i]<R&&l[R][i]>L) {
        ret++;
        if (r[L][i] < l[R][i])ret += func(r[L][i], l[R][i]);
        ret %= MOD;
    }
    return dp[L][R] = ret;
}
int main() {
    cin >> str;
    str = (char)('a' + 26) + str + (char)('a' + 26);
    n = str.size();
    rep(i, n + 1)rep(j, n + 1)dp[i][j] = -1;
    rep(i, n)str[i] -= 'a';
    rep(i, 30)r[n - 1][i] = n, l[0][i] = -1;
    for (int i = n - 2; i >= 0; i--) {
        rep(j, 27) {
            if (str[i + 1] == j)r[i][j] = i + 1;
            else r[i][j] = r[i + 1][j];
        }
    }
    for (int i = 1; i<n; i++) {
        rep(j, 27) {
            if (str[i - 1] == j)l[i][j] = i - 1;
            else l[i][j] = l[i - 1][j];
        }
    }
    cout << (func(0, n - 1)-1+MOD)%MOD << endl;
    return 0;
}