记录编号	314021	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]陨石的秘密	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2016-10-02 16:11:56	内存使用	1.54 MiB

// 假设一个ss串由两部分组合而成, 分别是ss1和ss2
// 情况一：第一位是“(”，与其配对的“)”位于第 i 位。设G1 (l1,l2,l3, d) 表示这种情况下的总数，G2 、G3 类似定义。
// ()将整个表达式分成两部分( ss1 和 ss2)。根据乘法原理，我们只需对两部分分别计数，然后乘起来即为结果。
// 我们设 ss1 中含有 x 对{}，y 对[]，z 对()。
// 因为 ss1 外层已经由一对()括起来，故其内部不可再含[]、{}，因此 x=0，y=0，且 ss1 的深度不可超过 d-1，ss1 的数目为 G(0,0,z,d-1)。
// ss2 中含有 l1-x=l1 个{}，l2-y=l2 个[]，l3-z-1 个()，深度不可超过 d，
// ss2 的数目为 G(l1,l2,l3-z-1,d)。
// 情况二：第一位是“[”，与其配对的“]”位于第 i 位。与情况一类似可得出
// 情况三：第一位是“{”，与其配对的“}”位于第 i 位。

#include "cstdio"
#include "cstring"
#include "iostream"
using namespace std;

int f[40][20][20][20];
// f[d][l1][l2][l3]: 深度<=d, {}l1对, []l2对, ()l3对的方案数
int d, l1, l2, l3;
const int mod = 11380;

#define SUBMIT
int main()
{
#ifdef SUBMIT
	freopen("secret.in", "r", stdin); freopen("secret.out", "w", stdout);
#endif

	scanf("%d%d%d%d", &l1, &l2, &l3, &d);
	for(int i = 0; i <= d; i++){
		f[i][0][0][0] = 1;
	}
	for(int depth = 1; depth <= d; depth++){
		for(int num1 = 0; num1 <= l1; num1++){
			for(int num2 = 0; num2 <= l2; num2++){
				for(int num3 = 0; num3 <= l3; num3++){
					if(num1 || num2 || num3){
						int G = 0;
						for(int a3 = 0; a3 <= num3-1; a3++){
							G = (G + f[depth-1][0][0][a3] * f[depth][num1][num2][num3-a3-1]) % mod;
						}
						for(int a3 = 0; a3 <= num3; a3++){
							for(int a2 = 0; a2 <= num2-1; a2++){
								G = (G + f[depth-1][0][a2][a3] * f[depth][num1][num2-a2-1][num3-a3]) % mod;
							}
						}
						for(int a3 = 0; a3 <= num3; a3++){
							for(int a2 = 0; a2 <= num2; a2++){
								for(int a1 = 0; a1 <= num1-1; a1++){
									G = (G + f[depth-1][a1][a2][a3] * f[depth][num1-a1-1][num2-a2][num3-a3]) % mod;
								}
							}
						}
						f[depth][num1][num2][num3] = G;
					}
				}
			}
		}
	}
	int ans;
	if(d)
		ans = f[d][l1][l2][l3] - f[d-1][l1][l2][l3];
	else
		ans = f[d][l1][l2][l3];
	if(ans < 0) ans += mod;
	printf("%d\n", ans);

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdout); fclose(stdout);
#endif
	return 0;
}