#include <stdio.h>
#define MOD(x) (((x) + 11380) % 11380)
int L1, L2, L3, D, f[11][11][11][31];
inline int part(int ma, int mb, int mc, int md,
int a, int b, int c
)
{
return MOD(f[a][b][c][md - 1] * f[ma - a][mb - b][mc - c][md]);
}
inline int calc(int ma, int mb, int mc, int md)
{
int a, b, c, r;
if (!ma && !mb && !mc)
return 1;
r = 0;
if (mc) {
for (c = 0; c <= mc - 1; c++)
r = MOD(r + part(ma, mb, mc - 1, md, 0, 0, c));
}
if (mb) {
for (b = 0; b <= mb - 1; b++)
for (c = 0; c <= mc; c++)
r = MOD(r + part(ma, mb - 1, mc, md, 0, b, c));
}
if (ma) {
for (a = 0; a <= ma - 1; a++)
for (b = 0; b <= mb; b++)
for (c = 0; c <= mc; c++)
r = MOD(r + part(ma - 1, mb, mc, md, a, b, c));
}
return r;
}
int main()
{
int a, b, c, d;
freopen("e:\\in.txt", "r", stdin);
scanf("%d%d%d%d", &L1, &L2, &L3, &D);
f[0][0][0][0] = 1;
for (d = 1; d <= D; d++)
for (a = 0; a <= L1; a++)
for (b = 0; b <= L2; b++)
for (c = 0; c <= L3; c++)
f[a][b][c][d] = calc(a, b, c, d);
printf("%d\n", D ? MOD(f[L1][L2][L3][D] - f[L1][L2][L3][D - 1]) :
MOD(f[L1][L2][L3][D])
);
return 0;
}
思路：
把括號的嵌套看成是一棵樹就簡單點了。
這棵樹的最大深度為 D。()節點下面不能有{}[]節點，[]節點下面不能有{}節點。
然后我們從上往下依次擺放節點。
考慮只有()節點的情況。
如果 f[n][d] 表示現在有n個節點需要擺放，深度小于等于d。
那么當前節點的下面可以擺 1，2 ... n 個節點。
擺完當前節點之后，剩下的在右邊繼續擺。
總方案數就是等于 下面的方案數*右邊的方案數
考慮三種節點都有的情況，實際上只是比上面的問題復雜一點點而已。
如果 f[a][b][c][d] 表示現在有a個{}節點，b個[]節點，c個()節點需要擺放。
當前節點擺 () 的時候，下面就只能擺 ()，其余的全放在右邊。
當前節點擺 [] 的時候，下面就只能擺 ()[]，。。。
。。。
這題的復雜度是 O(L1*L1*L2*L2*L3*L3*D)。
看上去比較大，但是可以AC的~
之前自己想的方法是 f[a][b][c][d] 表示深度等于d的方案數，而不是小于。
最后答案為 f[L1][L2][L3][D]。
復雜度多乘了一個D，就TLE了。
后來看了別人方法，發現保存深度小于等于d，這樣的話會好一些。
最后答案為 f[L1][L2][L3][D] - f[L1][L2][L3][D - 1]
這方法實在牛逼！
代碼：