题目

题目描述

博士经常阅读图书馆里的书籍。有一天，她在书中看到了一个长长的只由小写字母组成的字符串$S$
博士发现这个串有很多子序列都是回文串，非常优美，于是便列出了这个串的所有非空回文子序列
可是，博士忽然发现，她列出了很多相同的回文串
博士想知道，如果她只想把每种重复的串保留一个，一共需要从她的列表中移除多少回文串？
子序列$S$的一个子序列可以用一个数组$p$表示，构成的子序列为$S_{p_1}S_{p_2} \cdots \cdots S_{p_m}$，其中$m$为该子序列的长度
满足$0 < p_1 < p_2 < \cdots \cdots < p_m \leqslant |S|$

输入格式

一行一个非空字符串$S$

输出格式

输出一行一个整数，表示博士一共需要移除多少重复的回文串。由于答案可能很大，请对$10^9+7$取模

样例

样例输入1

bccb

样例输出1

样例输入2

abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba

样例输出2

679266098

数据范围与提示

样例1解释

对于第一组样例，非空子序列一共有：
${b,c,c,b,bc,bc,bb,cc,cb,cb,bcc,bcb,bcb,ccb,bccb}$
其中回文子序列有：
${b,c,c,b,bb,cc,bcb,bcb,bccb}$
需要删去$3$个重复的回文子序列

数据范围

对于$30 %$的数据，$|S| \leqslant 20$
对于$60 %$的数据，$|S| \leqslant 100$
对于$100 %$的数据， $1 \leqslant |S| \leqslant 2000$，$S$只会包含小写字母

题解

毒瘤区间DP……
我们用$f_{i,j}$表示$S_iS_{i+1}\cdots \cdots S_j$中回文串的总个数，$g_{i,j}$表示不重复回文串的个数，$to_i$表示$s_{to_i}=s_i$且$to_i$为最小的满足$s_j=s_i$的数，同理有$fr_i$
接着，我们可以得到转移方程：
$f_{i,j}=\begin{cases}1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=j\f_{i,j-1}+f_{i+1,j}+1\ \ \ \ \ \ \ \ \ \ \ \ \ \ s_i=s_j\f_{i,j-1}+f_{i+1,j}-f_{i+1,j-1}\ \ \ ,s_i\neq s_j\end{cases}$
$g_{i,j}=\begin{cases}1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=j\g_{i,j-1}+g_{i+1,j}-g_{i+1,j-1}\ \ \ \ s_i\neq s_j\2\times g_{i+1,j-1}+2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,s_i=s_j且to_i=j\2\times g_{i+1,j-1}+1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,s_i=s_j且to_i=fr_j\2\times g_{i+1,j-1}-g_{to_i+1,fr_j-1}\ ,,s_i=s_j且to_i\neq fr_j,to_i\neq j\end{cases}$
那么，答案就是$f_{1,n}-f_{1,g}$了！
附上代码：

#include<iostream>
#include<cstring>
using namespace std;
int n,to[2010],fr[2010],pos[30];
long long MOD=1e9+7,f[2010][2010],g[2010][2010];
char a[2010];
int main()
{
    cin>>(a+1),n=strlen(a+1);
    for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++)
        if(i==1) f[j][j+i-1]=1;
        else{
            if(a[j]==a[j+i-1]) f[j][j+i-1]=(f[j][j+i-1-1]+f[j+1][j+i-1]+1)%MOD;
            else f[j][j+i-1]=(f[j][j+i-1-1]+f[j+1][j+i-1]-f[j+1][j+i-1-1])%MOD;
        }
    for(int i=1;i<=n;i++) fr[i]=pos[a[i]-'a'+1],pos[a[i]-'a'+1]=i;
    for(int i=1;i<=26;i++) pos[i]=n+1;
    for(int i=n;i;i--) to[i]=pos[a[i]-'a'+1],pos[a[i]-'a'+1]=i;
    for(int i=1;i<=n;i++) for(int j=1;j<=n-i+1;j++)
        if(i==1) g[j][j+i-1]=1;
        else{
            if(a[j]!=a[j+i-1]) g[j][j+i-1]=(g[j][j+i-1-1]+g[j+1][j+i-1]-g[j+1][j+i-1-1])%MOD;
            else{
                if(to[j]==j+i-1) g[j][j+i-1]=(2*g[j+1][j+i-1-1]+2)%MOD;
                if(to[j]==fr[j+i-1]) g[j][j+i-1]=(2*g[j+1][j+i-1-1]+1)%MOD;
                if(to[j]!=j+i-1&&to[j]!=fr[j+i-1]) g[j][j+i-1]=(2*g[j+1][j+i-1-1]-g[to[j]+1][fr[j+i-1]-1])%MOD;
            }
        }
    cout<<(f[1][n]-g[1][n]+MOD)%MOD;
}