分别给出\(l_1,l_2,l_3\)个\(\{\},[],()\)，优先级从低到高，组成一个合法的括号序列，并保证一个括号里的括号优先级要大于等于它，定义深度为括号里套括号的层数，问深度恰好为d的方案数\(mod\ 11380\)，\(0 <= L1 <= 10,0 <= L2 <= 10,0 <= L3 <= 10,0 <= D <= 30\)。
解
不能单独去考虑一个括号，递推状态无法表现，于是考虑划分一个序列成为几个合法序列的方案数，但是注意到可能会有重复，于是用一个括号强制包一个序列即可，现在问题在于枚举深度太麻烦了，于是考虑差分设状态，因此可以设出\(f[i][j][k][l]\)表示深度小于等于i，有j个\(\{\}\)k个\([]\)l个\(()\)的方案数，因此不难有
\[f[i][j][k][l]=\begin{cases}1& if(j==k==l==0)\\\sum_{p=1}^j\sum_{q=0}^k\sum_{r=0}^lf[i-1][p-1][q][r]\times f[i][j-p][k-q][l-r]+&else\\ \sum_{p=1}^k\sum_{q=0}^lf[i-1][0][p-1][q]\times f[i][j][k-q][l-q]+\sum_{p=1}^l\\f[i-1][0][0][p-1]\times f[i][j][k][l-p]\end{cases}\]
边界:\(f[i][0][0][0]=1,i=0,1,2,..,d\)
答案：\(f[d][l1][l2][l3]-f[d-1][l1][l2][l3]\)
参考代码：
阶段实现：
#include#include #define il inline#define ri register#define lzq 11380using namespace std;int dp[11][11][11][31];int main(){ int l1,l2,l3,d; scanf("%d%d%d%d",&l1,&l2,&l3,&d); for(int i(0);i<=d;++i)dp[0][0][0][i]=1; for(int i(1),j,k,l,p,q,r;i<=d;++i) for(j=0;j<=l1;++j) for(k=0;k<=l2;++k) for(l=0;l<=l3;++l){ for(p=1;p<=j;++p) for(q=0;q<=k;++q) for(r=0;r<=l;++r) dp[j][k][l][i]+=dp[p-1][q][r][i-1]* dp[j-p][k-q][l-r][i]%lzq; for(p=1;p<=k;++p) for(q=0;q<=l;++q) dp[j][k][l][i]+=dp[0][p-1][q][i-1]* dp[j][k-p][l-q][i]%lzq; for(p=1;p<=l;++p) dp[j][k][l][i]+=dp[0][0][p-1][i-1]* dp[j][k][l-p][i]; dp[j][k][l][i]%=lzq; } int ans(dp[l1][l2][l3][d]); if(d)ans-=dp[l1][l2][l3][d-1]; (ans+=lzq)%=lzq;printf("%d",ans); return 0;}
dfs实现：
#include#include #define il inline#define ri register#define lzq 11380using namespace std;bool is[31][11][11][11];int dp[31][11][11][11];int dfs(int,int,int,int);il int mod(int);int main(){ int l1,l2,l3,D; scanf("%d%d%d%d",&l1,&l2,&l3,&D); for(int i(0);i<=D;++i)dp[i][0][0][0]|=true; printf("%d",mod(dfs(D,l1,l2,l3)-dfs(D-1,l1,l2,l3))); return 0;}il int mod(int x){ return ((x%=lzq)+=lzq)%=lzq;}int dfs(int a,int b,int c,int d){ if(a<0||b<0||c<0||d<0)return 0; if(is[a][b][c][d])return dp[a][b][c][d]; int &x(dp[a][b][c][d]),i,j,k; for(i=1;i<=b;++i) for(j=0;j<=c;++j) for(k=0;k<=d;++k) x+=dfs(a-1,i-1,j,k)*dfs(a,b-i,c-j,d-k)%lzq; for(i=1;i<=c;++i) for(j=0;j<=d;++j) x+=dfs(a-1,0,i-1,j)*dfs(a,b,c-i,d-j)%lzq; for(i=1;i<=d;++i) x+=dfs(a-1,0,0,i-1)*dfs(a,b,c,d-i)%lzq; return is[a][b][c][d]|=true,x%=lzq;}