f(i,j)=sum(f(i+1,k-1)*f(k,j) | i+2<=k<=j，Si=Sk=Sj）。
f(i+1,k-1)是划分出第一颗子树，f(k,j)是划分出剩下的子树。
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define MOD 1000000000ll
char s[310];
ll f[310][310];
int n;
ll dp(int l,int r){
if(f[l][r]!=-1){
return f[l][r];
}
f[l][r]=0;
for(int k=l+2;k<=r;++k){
if(s[l]==s[k]){
f[l][r]=(f[l][r]+dp(l+1,k-1)*dp(k,r)%MOD)%MOD;
}
}
return f[l][r];
}
int main(){
// freopen("uvaLive3516.in","r",stdin);
while(scanf("%s",s+1)!=EOF){
memset(f,-1,sizeof(f));
n=strlen(s+1);
for(int i=1;i<=n;++i){
f[i][i]=1;
}
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(s[i]!=s[j]){
f[i][j]=0;
}
}
}
printf("%d\n",(int)dp(1,n));
}
return 0;
}