公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：
　　1 1 1 1 6
　　0 0 6 3 57
　　8 0 11 3 2845
　　著名的科学家SS发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种SS表达式：
　　1． SS表达式是仅由'{'，'}'，'['，']'，'（'，'）'组成的字符串。
　　2． 一个空串是SS表达式。
　　3． 如果A是SS表达式，且A中不含字符'{'，'}'，'['，']'，则(A)是SS表达式。
　　4． 如果A是SS表达式，且A中不含字符'{'，'}'，则[A]是SS表达式。
　　5． 如果A是SS表达式，则{A}是SS表达式。
　　6． 如果A和B都是SS表达式，则AB也是SS表达式。

　　例如
　　()(())[]
　　{()[()]}
　　{{[[(())]]}}
　　都是SS表达式。
　　而
　　()([])()
　　[()
　　不是SS表达式。

　　一个SS表达式E的深度D(E)定义如下：

　　
　　例如(){()}[]的深度为2。

　　密文中的复杂运算是这样进行的：
　　设密文中每行前4个数依次为L1，L2，L3，D，求出所有深度为D，含有L1对{}，L2对[]，L3对()的SS串的个数，并用这个数对当前的年份11380求余数，这个余数就是密文中每行的第5个数，我们称之为"神秘数"。
　　密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

输入文件（secret.in）
　　共一行，4个整数L1，L2，L3，D。相邻两个数之间用一个空格分隔。
　　（0≤L1≤10，0≤L2≤10，0≤L3≤10，0≤D≤30）

输出文件（secret.out）
　　共一行，包含一个整数，即神秘数。

输入样例
1 1 1 2

输出样例
8

Noi2001之陨石的秘密（Secret）解题报告

福州第一中学 陈阳

【题意分析】
　　本题所谓的SS表达式，也就是一个通过{}、[]、()组成的，左右括号相对并且嵌套关系无误的一个式子。所谓的神秘数，也就是在给定三种括号的数量和最大的嵌套深度的情况下所有合法的SS表达式的数量除以11380的余数。因此，本题的实际意义就是，给定L1对{}、L2对[]、L3对()和最大深度D，求出符合以上条件的合法的SS表达式的数量除以11380的余数。

【解题思路】

　　这道题的要求是统计个数，如果用搜索的方法构造出所有的SS表达式，复杂度显然太大，也没有强有力的剪枝，而且一个子问题在大问题中要搜索多次，也就是具有子问题重叠性质，搜索浪费很大。而明显，这一题可以按照D的去值划分阶段，按照L1、L2、L3来描述一个状态，加上子问题重叠，因此，这题可能利用动态规划或者递推这样的方法解决。所以，下面我们就往这方面尝试。

　　首先，我们可以对题目做适当的简化。我们暂时不考虑三种括号的区别，假设所有括号的总数为L，那么用D和L来表示状态。我们设F(D,L)表示一共有L对无区别的括号所能构成的最大嵌套深度不超过D的表达式的总数。我们来考虑F(D,L)和其他的状态之间有什么联系。我们称一个表达式中，用加号连接的部分叫做它的子表达式。如果一个表达式没有加号相连，我们也可以认为它本身就是自己的子表达式。由于表达式嵌套深度就是它的子表达式嵌套深度的最大值，我们可以知道F(D,L)中，它的子表达式的最大深度也不超过D。

　　 1、如果原表达式唯一的表达式就是自身，也就是说，它的最外一层括号包括了整个表达式，那么，我们可以把最外面的这一层括号脱去，里面就是一个由L-1对括号组成的深度为D-1的表达式。这种情况的方案数为F(D-1,L-1)。
　　 2、如果表达式是由多个子表达式组成的，那么它的每一个子表达是的最大深度都不超过D。我们将原表达式按照加号人为分割成两块，一块含有t对括号，另一块就含有n-t对括号，两块的最大深度都不超过D。这样我们就知道这样用加号连接的表达式一共有种。但是，这种计算方法重复了多余的情况，在一个表达式由两个或以上的深度为D的子表达式的情况下，一个最大深度为D的子表达式会在F(D,t)和F(D,L-t)中各出现了一次。为了避免重复，我们规定，深度为D的子表达式，只能在第一项也就是F(D)中间出现，而对于另外的几项，强制规定它们的最大深度必须小于D，如果他们的深度也是D，我们也强制把它们脱去一层括号，就变成F(D-1,L-t-1)。这样有加号连接的表达式的总数为。加上第一种情况（最外层是括号的），这样就得到了关于F(D,L)的递归式 。

　　现在我们可以考虑如果由三种不同的括号的情况了。三种括号的实质区别是一种优先级的区别，那么，如果由{}，最外层就一定为{}；而如果没有{}，最外层才可能为[]。如果{}、[]都没有，最外层才能为()。所以，我们在脱括号的时候，最先脱{}，没有{}才能脱[]，如果{}、[]都没有才能脱()。因此我们把上面的递归式的第二维L改换成三个参数L1、L2、L3。因此状态表示为F(D,L1,L2,L3)，表示一共有L1对{}、L2对[]、l3对()所能构成的最大嵌套深度不超过D的表达式的总数。仿照上面的递归式，我们可以类似得到
　　
。另外，我们认为，F(0,0,0,0)为1，这是递归式的初始条件。

【算法完善和改进】

　　根据函数F的定义，我们的目标就是F(D,L1,L2,L3)-F(D-1，L1,L2,L3)。另外，题目要求我们求的不是最终的有多少种解，而是解数处以11380的余数。实际上我们知道，如果的话，那么也是t。因此，我们可以每求得一个F(D,L1,L2,L3)，就马上对它关于11380取模，这样可以避免使用高精度。而最终的结果就是（F(D,L1,L2,L3)-F(D-1，L1,L2,L3)+11380）mod 11380。
　　上述算法已经大致上满足编程的需求。

　　我们再观察递归式，容易发现，按照D值的不同分层，则某一层的状态，都是由前一层的状态和当前层已知的状态计算而来的。由于我们是自下到上逐步求解，因此我们只要记录当前层和前一层的数据就可以了。
　　另外，有一些特殊数据，如果L1+L2+L3<D，那么解的组数就是0。如果L1+L2+L3=D，那么解的组数就是1，不必搜索。

【算法分析】

　　经过以上分析和改进，算法已基本成行。算法的时间复杂度为，但循环计算小于次。空间复杂度为，实际上占用空间为实际测试表明，在Free Pascal 1.0.4环境下，能够通过所有测试数据。因此，算法是实际可行的。

【解题总结】

　　这一题想到递推不难，但是写好递归式却是一件不容易的事情。在推导递归式的过程中，必须考虑很多特殊情况需要，包括初始值和约束条件等。特别时本题，对于不同的状态，由不同的约束条件。因此写程序之前必须认真分析好各种可能情况，而如果没有慎重考虑，在调试中要遇到很多状态的大量数据，往往难以发现错误，花费大量时间在改进程序上。我们几位同学在比赛的时候都没有很好的考虑到各种情况，在调试中不断对程序修修补补，耗时巨大。因此，拿到题目出略分析就写程序，然后调试程序大部定不断改进，倒不如深思熟虑，先打好程序的"腹稿"，写程序一气呵成，马到成功。