记录编号	595031	评测结果	AAAAAAAAAA
题目名称	金字塔	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	0.111 s
提交时间	2024-10-07 08:46:35	内存使用	3.90 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9;
int n,dp[505][505];
char s[505];
signed main(){
	freopen("ZYH.in","r",stdin);
	freopen("ZYH.out","w",stdout);
	cin>>(s+1); n=strlen(s+1);
	for(int i = 0;i<=n;i++) dp[i][i]=1;
	for(int len=2;len<=n;len++){
		#define r (l+len-1)
		for(int l=1;r<=n;l++){
			if(s[l]==s[r])
			for(int k = l;k<=r;k++)
			if(s[k]==s[l]&&s[k+1]==s[r-1]) 
			dp[l][r]=(dp[l][r]+dp[l][k]*dp[k+1][r-1])%mod; 
		}
	}
	printf("%lld",dp[1][n]);
	return 0;
}