题解：P5694 [NOI2001] 陨石的秘密

· · 题解

感觉挺难搞的一道题，决定写个题解纪念一下。

首先我们很容易看到这个小的可怜的数据范围：0\le L_1,L_2,L_3\le10,0\le D\le30。因此我们可以考虑设计一个非常暴力的 DP。

设 f_{i,j,k,l} 表示花括号用了 i 对，方括号用了 j 对，圆括号用了 k 对，当前的深度为 l 时的方案数是多少。我们可以尝试转移一下这个 DP。

反正在经过我一个小时的不懈努力之后发现：这个 DP 转移不了……于是我点开了题解，然后就大彻大悟了。

我们更改 DP 定义为 f_{i,j,k,l} 表示花括号用了 i 对，方括号用了 j 对，圆括号用了 k 对，深度不大于 l 时的方案数。于是我们分类讨论一下：

  1. 如果我们把一个花括号包在外面，形成 {A} 这种形状，那么转移方程应该是 f_{i,j,k,l}=f_{i,j,k,l}+f_{i-1,j,k,l-1}。
  2. 如果我们把一个方括号包在外面，形成 [A] 这种形状，那么我们首先要保证 i=0，然后转移方程就是 f_{i,j,k,l}=f_{i,j,k,l}+f_{0,j-1,k,l-1}。
  3. 如果我们把一个圆括号包在外面，形成 (A) 这种形状，那么我们首先要保证 i=0 且 j=0，然后转移方程就是 f_{i,j,k,l}=f_{i,j,k,l}+f_{0,0,k-1,l-1}。
  4. 如果我们把两个串拼在一起，形成 AB 这种形状。这时我们要仔细考虑一下了。

首先，我们肯定不能直接枚举两个串然后拼在一起，打个比方：要构成串 ()()()，我们可以选择 A=(),B=()()，这样 AB=()()()，我们还可以选择 A=()(),B=()，这样拼一起也是 ()()()。但是串 ()()() 只有一种，所以直接枚举肯定有问题。

不过我们可以取出最左边的合法串，然后考虑这个串最外层的字符是什么。最终肯定只有三种类型：(A)B,[A]B,{A}B。

相信各位读者读到这应该都会之后的转移了，基本跟上面类似。不会的看代码。

代码实现：

#include<bits/stdc++.h>
#define int long long
#define code using
#define by namespace
#define plh std
code by plh;
namespace fastio
{
    inline int read()
    {
        int z=0,f=1;
        char c=getchar();
        if(c==EOF)
        {
            exit(0);
        }
        while(c<'0'||c>'9')
        {
            if(c==EOF)
            {
                exit(0);
            }
            if(c=='-')
            {
                f=-1;
            }
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            z=z*10+c-'0';
            c=getchar();
        }
        return z*f;
    }
    inline void write(int x)
    {
        if(x<0)
        {
            putchar('-');
            x=-x;
        }
        static int top=0,stk[106];
        while(x)
        {
            stk[++top]=x%10;
            x/=10;
        }
        if(!top)
        {
            stk[++top]=0;
        }
        while(top)
        {
            putchar(char(stk[top--]+'0'));
        }
    }
    inline void write(string s)
    {
        for(auto i:s)
        {
            putchar(i);
        }
    }
}
using namespace fastio;
int l1,l2,l3,d,f[16][16][16][36];
const int mod=11380;
signed main()
{
    l1=read(),l2=read(),l3=read(),d=read();
    for(int i=0;i<=d;i++)
    {
        f[0][0][0][i]=1;
    }
    for(int j=0;j<=l1;j++)
    {
        for(int k=0;k<=l2;k++)
        {
            for(int l=0;l<=l3;l++)
            {
                for(int i=1;i<=d;i++)
                {
                    if(j)
                    {
                        f[j][k][l][i]+=f[j-1][k][l][i-1];
                        f[j][k][l][i]%=mod;
                    }
                    if(!j&&k)
                    {
                        f[j][k][l][i]+=f[j][k-1][l][i-1];
                        f[j][k][l][i]%=mod;
                    }
                    if(!j&&!k&&l)
                    {
                        f[j][k][l][i]+=f[j][k][l-1][i-1];
                        f[j][k][l][i]%=mod;
                    }
                    for(int p=1;p<=j;p++)
                    {
                        for(int q=0;q<=k;q++)
                        {
                            for(int r=0;r<=l;r++)
                            {
                                f[j][k][l][i]+=f[p-1][q][r][i-1]%mod*(f[j-p][k-q][l-r][i]-(j==p&&k==q&&l==r?1:0))%mod;//减掉后半部分完全没用括号的情况
                                f[j][k][l][i]%=mod;
                            }
                        }
                    }
                    for(int q=1;q<=k;q++)
                    {
                        for(int r=0;r<=l;r++)
                        {
                            f[j][k][l][i]+=f[0][q-1][r][i-1]%mod*(f[j][k-q][l-r][i]-(j==0&&k==q&&l==r?1:0))%mod;
                            f[j][k][l][i]%=mod;
                        }
                    }
                    for(int r=1;r<=l;r++)
                    {
                        f[j][k][l][i]+=f[0][0][r-1][i-1]%mod*(f[j][k][l-r][i]-(j==0&&k==0&&l==r?1:0))%mod;
                        f[j][k][l][i]%=mod;
                    }
                }
            }
        }
    }
    write((f[l1][l2][l3][d]-f[l1][l2][l3][d-1]+mod)%mod);
    return 0;
}