AOJ 2895 回文部分列 (AUPC 2018 day3 G)

##問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2895
##見た感じ
文字列sを入れ替えた文字列tを用意して、$nxts[i][c]=sのi文字目以降に文字cが現れる最小のindex,nxtt[i][c]=nxts[i][c]のt版$として、先に計算しておく。
さてどうしようと思ったとき、最初にうかんだのは以下の操作を素直にプログラムすることだった。
sとtからおんなじ部分文字列a,bを取り出して、それぞれの最終文字のindexがうまくいくときに並べれば、sの回文部分文字列になるし、それが全部の回文文字列なので、
priority_queue(pairのfirstの小さい順)にa,bの最後の文字のindexのpairを突っ込んでいく。もしa,bに同じ文字がつけ足せるなら、付け足した奴の最後の文字のindexをpriority_queueに突っ込んでを繰り返し、priority_queが空になったら終わり。場合の数は、queueに入ってる区間をもとに計算し足していく。
これを書くと、priority_queueがでかくなりすぎて、メモリオーバー。。
dpしなきゃ間に合わないとわかっていても、漸化式は思いつかない。
調べました。
[この]{https://qiita.com/drken/items/a207e5ae3ea2cf17f4bd}サイトです。
dp[i][j]=0にそんな文字列はないって意味を添えるだけで、priority_queueまで使って避けていた更新の順番問題が解決し漸化式がたちました。
実装しました。
いけました。。
悔しいです。
##解法
[ここ]{https://qiita.com/drken/items/a207e5ae3ea2cf17f4bd}にあります。
```math
dp[i][j]=sの0からi-1文字目までとtの0からj-1文字目までを使って作れる回文部分文字列の個数\\
dp[0][0]=1\\
each c \in {1,2,\dots ,26}dp[nxts[i][c]+1][nxtt[j][c]+1]+=dp[i][j]
```
これを計算します。
##ソースコード
```c++
const int N_MAX=2005;
string s,t;
int nxts[N_MAX][26],nxtt[N_MAX][26],n;
//mint dp[N_MAX];
//素直に実装  間に合わない
/*mint solve(){
    auto compare=[](pint a,pint b){
        return a.first>b.first;
    };
    mint res=0,r=1;
    priority_queue<pint,vector<pint>,decltype(compare)> que {compare};
    que.push({-1,-1});
    int nows,nowt,ns,nt,count;
    while(!que.empty()){
        pint a=que.top();que.pop();
        nows=a.first+1;
        nowt=a.second+1;
        //if(a.first>=0)r=dp[a.first];
        r=1;
        if(a.first+a.second==n-2){
            res+=r;
        }else{
            count=1;
            rep(i,26){
                if(nxts[nows][i]<n-nowt)count++;
            }
            r*=count;
            res+=r;
        }
        //cout << "s["<<a.first<<"]="<<s[a.first]<<" t["<<a.second<<"]="<<t[a.second] <<endl;
        //cout <<"count="<<count<<" r=" <<r<<" res="<<res <<endl;
        rep(j,26){
            ns=nxts[nows][j];nt=nxtt[nowt][j];
            if(ns+nt<=n-2){
                //cout << "nxts["<<nows<<"]["<<j<<"]="<<ns<<" nxtt["<<nowt<<"]["<<j<<"]="<<nt <<" s[ns]="<<s[ns]<<endl;
                que.push({ns,nt});
                //if(nows-1<0)dp[ns]=1;
                //else dp[ns]+=dp[nows-1];
            }
        }
    }
    res-=1;
    return res;
}*/

mint dp[N_MAX][N_MAX];
mint solve(){
    dp[0][0]=1;
    rep(i,n){
        rep(j,n){
            rep(l,26){
                if(nxts[i][l]+nxtt[j][l]+2>n)continue;
                dp[nxts[i][l]+1][nxtt[j][l]+1]+=dp[i][j];
            }
        }
    }
    mint res=0,r;
    int x,y,count;
    rep(i,n+1){
        rep(j,i+1){
            x=j;y=i-j;
            count=1;
            rep(l,26){
                if(nxts[x][l]<n-y)count++;
            }
            r=dp[x][y];
            r*=count;
            res+=r;
        }
    }
    //空文字の分引く
    res-=1;
    return res;
}


int main(){
    int x,y;
    //入力
    cin>>s;
    t=s;
    reverse(t.begin(),t.end());
    //処理
    n=s.size();
    rep(i,n+1){
        rep(j,26){
            nxts[i][j]=n;
            nxtt[i][j]=n;
        }
    }
    vrep(i,n){
        rep(j,26){
            nxts[i][j]=nxts[i+1][j];
            nxtt[i][j]=nxtt[i+1][j];
        }
        nxts[i][s[i]-'a']=i;
        nxtt[i][t[i]-'a']=i;
    }
    mint ans=solve();
    //出力
    cout << ans <<endl;
}
```