记录编号	581500	评测结果	AAAAAAAAAA
题目名称	金字塔	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.134 s
提交时间	2023-08-04 10:02:33	内存使用	2.70 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1010,mod = 1e9;
ll dp[N][N];
char ch[410];
ll sou(int l,int r){
    if(l > r || ch[l] != ch[r])return 0;
    if(dp[l][r] != -1)return dp[l][r] % mod;
    if(l == r)return 1;
    dp[l][r] = 0;
    for(int k = l+2;k <= r;k++){
        dp[l][r] = dp[l][r] + ((sou(l+1,k-1) * sou(k,r)) % mod);
    }
    return dp[l][r] % mod;
}
int main(){
    freopen("ZYH.in","r",stdin);
    freopen("ZYH.out","w",stdout);
    cin>>ch;
    memset(dp,-1,sizeof(dp));
    int r = strlen(ch);
    printf("%lld\n",sou(0,r-1));
    
    return 0;
    
}