构造合法的bracket-sequence。首先满足以下条件的序列是合法的bracket-sequence：
(1)空串是一个合法的bracket-sequence；
(2)若A是一个合法的bracket-sequence，则(A)、[A]、{A}都 是合法的bracket-sequence；
(3)若A和B都是合法的bracket-sequence，则ABbn是合法的bracket-sequence。
现在有一个带有通配符“?”的序列，问可以构造成多少个合法的bracket-sequence。
由于这个数可能很大，输出时仅输出这个数的最后5位。
一看到这个带有括号的串，我们的第一感觉就是括号的匹配问题！又要用到栈了！但这里去并非如此，如果要运用栈的话，显然对于要求很大很大的数一定是件很费时的事！这里绝对不能动模拟的念头！！
那么该怎么思考这个问题呢？
我们先看样例：
(?([?)]?}?
对于这个串，首先我们要为第1个符号寻找与之匹配的符号
(1)第2个位置，由于?是通配符号，可以与第1个符号匹配，那只需要检查从第3个位置到最后有多少种匹配即可，即把原问题规模缩小了。
(2)再看第3个位置，对于这个位置，根本无需检查，因为即使它能与第1个位置匹配，那它中间只剩下一个符号，根本无法匹配，所以由此可知，第1个位置只能与偶数位置的去匹配！
(3)再找下一个可匹配的，是第6个位置，这样只需要检查第2个位置到第5个位置有多少种匹配，以及第7个位置到最后有多少种匹配，由于两个子路是独立的，所以此时的bracket-sequence数为两个子串的bracket-sequence数之积！
由此，可得出以下关系式：
若对于第1个位置标记为0，其匹配长度为j时的bracket-sequence数为f[0][j]，则有f[0][j]=f[1][j-1]*f[j*2][L-j]（其中L为串的长度/2）
这样，就可以得到这样的递推式来完成
f[i][j]=g(i,j)*f[i+1][j-1]+sum(f[i][k]*f[i+j*2][j-k]) （其中g(i,j)表示第i个位置，匹配长度为j时可与最后那个位置匹配可能数）
写完程序后，测试这组数据
6
()()()
时，输出的结果是2 ，这个结果明显应该是1啊！
结果发现上个式子错误的把()两两组合计算了两遍，原因就是f[0][1]*f[2][2]算一遍，而f[0][1]*f[4][2]也算一遍，这两个其实都是列出了f[0][1]、f[2][1]、f[4][1]这种可能，其主要原因就是f[0][2]的结果是1，它保存了f[0][1]与f[2][1]这种，而f[2][2]保存了f[2][1]与f[4]1]这种，从而导致重复计算！
问题的关键就在于要把f[i][k]*f[i+j*2][j-k]中的f[i][k]一定表示为首尾匹配情况下所得到的数，这里可以把数组再加一维，用于记录！则原递推式改为：
f[i][j][0]=g(i,j)*f[i+1][j-1][1]
f[i][j][1]=f[i][j][0]+sum(f[i][k][0]*f[i+j*2][j-k][1])
在求解过程中加上取模运算即可！
另需要提醒的时，由于保存的是后5位数，所以乘法运算会超出整型范围，要使用__int64数据类型！
还有输出后5位数，所以有可能有前导0！！