作者:
navystar
,
2023-05-26 12:40:06
,
所有人可见
,
阅读 4
//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 310, mod = 1e9;
int h[N][N];
string s;
inline int dfs(int l, int r)
{
if (l == r) return 1;
if (l > r) return 0;
if (h[l][r] != -1) return h[l][r];
h[l][r] = 0;
for (int k = l + 2; k <= r; k ++ )
if (s[k] == s[l])
h[l][r] = (h[l][r] + (long long)dfs(l + 1, k - 1) * dfs(k, r)) % mod;
return h[l][r];
}
inline void solve()
{
memset(h, -1, sizeof h);
cin >> s;
cout << dfs(0, s.size() - 1) << endl;
}
int main()
{
solve();
return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~