记录编号	594968	评测结果	AAAAAAAAAA
题目名称	金字塔	最终得分	100
用户昵称	会挽弯弓满月	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2024-10-06 19:29:53	内存使用	3.75 MiB

#include <bits/stdc++.h> 
#define ll long long
const int N=310;
const int M=1e9;
using namespace std;
int n;
string s;
ll f[N][N];
int main()
{
	freopen("ZYH.in","r",stdin);
	freopen("ZYH.out","w",stdout);
	cin>>s;
	n=s.size();
	s=" "+s;
	for(int i=1;i<=n;i++)
	{
		f[i][i]=1;
	}
	for(int len=2;len<=n;len++)//枚举区间长度 
	{
		for(int i=1;i+len-1<=n;i++)//枚举区间起点 
		{
			int j=i+len-1;
			if(s[i]==s[j])//可能为同一个根节点组成的树 
			{
				for(int k=i;k<j;k++)//枚举中间点 
				{
					if(s[k]==s[i])//以k为中间点分成2棵树
					{
						f[i][j]+=(f[i][k]*f[k+1][j-1])%M;
						f[i][j]%=M;
					}
				}
			}
		}
	}
	printf("%d",f[1][n]);
	return 0;
}