记录编号	410751	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]陨石的秘密	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.092 s
提交时间	2017-06-02 13:06:34	内存使用	0.48 MiB

#include<cstdio>
const int p=11380;
int l1,l2,l3,d,dp[11][11][11][31];
bool vis[11][11][11][31];
//dp[l1][l2][l3][d]表示含有l1,l2,l3个括号且深度不超过d的方案数
int v(int l1,int l2,int l3,int d){
	if (d<0) return 0;
	if (!l1&&!l2&&!l3) return 1;
	if (!d) return 0;
	if (vis[l1][l2][l3][d]) return dp[l1][l2][l3][d];
	vis[l1][l2][l3][d]=1;
	int ans=0;
	//考虑划分成两部分
	for (int i=0;i<=l1;i++)
	for (int j=0;j<=l2;j++)
	for (int k=0;k<=l3;k++)//串联起来最左边那个
	if (i||j||k){
		int K;
		if (i) K=v(i-1,j,k,d-1);else
		if (j) K=v(i,j-1,k,d-1);else
		if (k) K=v(i,j,k-1,d-1);
		ans=(ans+K*v(l1-i,l2-j,l3-k,d))%p;
	}
	//printf("dp[%d,%d,%d,%d]=%d\n",l1,l2,l3,d,ans);
	return dp[l1][l2][l3][d]=ans;
}
int main()
{
	freopen("secret.in","r",stdin);
	freopen("secret.out","w",stdout);
	scanf("%d%d%d%d",&l1,&l2,&l3,&d);
	int ans=v(l1,l2,l3,d)-v(l1,l2,l3,d-1);
	printf("%d\n",ans<0?ans+p:ans);
	return 0;
}