记录编号	259735	评测结果	AAAAAAAAAA
题目名称	1478.[UVa 1362] 多叉树遍历	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.683 s
提交时间	2016-05-11 15:06:42	内存使用	1.01 MiB

//KZNS
#include <fstream>
#include <cstring>
using namespace std;
//
ifstream fin ("Pyramids.in");
ofstream fout ("Pyramids.out");
#define Nmax 303
#define MD 1000000000
//
long long F[Nmax][Nmax] = {0};
//
int main() {
	string s;
	while (fin >> s) {
		memset(F, 0, sizeof(F));
		int n = s.length();
		for (int i = 0; i < n; i++)
			F[i][i] = 1;
		for (int c = 1; c < n; c++) {
			for (int i = 0, j = c; j < n; i++,j++) {
				if (s[i] != s[j])
					F[i][j] = 0;
				else {
					for (int k = i+2; k <= j; k++)
					F[i][j] = (F[i][j] + (F[i+1][k-1]*F[k][j])) % MD;
				}
			}
		}
		fout << F[0][n-1] << endl;
	}
	return 0;
}
//UBWH