526互联

[NOI2001] 陨石的秘密

发布时间 2023-10-27 13:38:22作者: HL_ZZP

题目描述

公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：

1 1 1 1 6
0 0 6 3 57
8 0 11 3 2845

著名的科学家 SS 发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种 SS 表达式：

  1. SS 表达式是仅由 {, }, [, ], (, ) 组成的字符串。
  2. 一个空串是 SS 表达式。
  3. 如果 AA 是SS表达式，且 AA 中不含字符 {, }, [, ]，则 (A)(A) 是SS表达式。
  4. 如果 AA 是 SS 表达式，且 AA 中不含字符 {, }，则 [A][A] 是 SS 表达式。
  5. 如果 AA 是 SS 表达式，则 {A}{A} 是 SS 表达式。
  6. 如果 AA 和 BB 都是 SS 表达式，则 ABAB 也是 SS 表达式。

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

D(E)={0,如果 E 是空串D(A)+1,如果 E=(A) 或者 E=[A] 或者 E={A}, 其中 A 是 SS 表达式max⁡(D(A),D(B)), 如果 E=AB,其中 A,B 是 SS 表达式D(E)={0,D(A)+1,max(D(A),D(B)),​如果 E 是空串如果 E=(A) 或者 E=[A] 或者 E={A}, 其中 A 是 SS 表达式 如果 E=AB,其中 A,B 是 SS 表达式​

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

密文中的复杂运算是这样进行的：

设密文中每行前 44 个数依次为 L1,L2,L3,DL1​,L2​,L3​,D，求出所有深度为 DD，含有 L1L1​ 对 {}，L2L2​ 对 []，L3L3​ 对 () 的 SS 串的个数，并用这个数对当前的年份 1138011380 求余数，这个余数就是密文中每行的第 55 个数，我们称之为“神秘数”。

密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

输入格式

共一行，44 个整数 L1,L2,L3,DL1​,L2​,L3​,D。相邻两个数之间用一个空格分隔。

输出格式

共一行，包含一个整数，即神秘数。

输入输出样例

输入 #1
1 1 1 2
输出 #1
8

说明/提示

0≤L1,L2,L3≤100≤L1​,L2​,L3​≤10，0≤D≤300≤D≤30。

状态设计还是很明显的
f[i][j][k][h]表示有i个大括号，j个中括号，k个小括号，深度为h的情况有多少种可能
我第一次考虑的转移，分为两种情况，一种是再外面套一个括号，一种是合并两种情况
还是很清晰的
但是这个是有问题的
举个具体的例子，就是如果我合并f[1][0][0][1]和f[0][1][1][1]，那会有()[]{}和(){}[]两个情况被统计
f[1][1][0][1]和f[0][0][1][1]合并也会产生()[]{}这个情况
那就被统计了两次，答案中出现了重复，是错误的

那要怎么排除呢？
我们可以发现，如果不对合并的两边做限制，那上述这种情况一定会一直存在，无法排除
那如果我们限制合并情况呢？
我们把合并情况的一边限制为被一个括号全部框住，也就是合并A{B}或者A(B)或者A[B]，
很明显，这是不重复的，那重复的答案问题就被解决了

为了方便转移,我们用f[i][j][k][h]表示有i个大括号,j个中括号,k个小括号,深度不大于h的情况有多少种可能
那么转移方程就很明显了，具体的直接看代码吧。。

这道题目的难点在于怎么转移来避免答案的重复统计
这种限制的方法是值得积累的，如果以后遇到了这种直接转移有重复的情况，可以尝试这样考虑来避免重复

（虽然我也不知道“这样”考虑到底具体指的是怎么考虑。。只是说加上点限制条件太宽泛了。。）
然后我这题因为看错了题目给的输入顺序调了tm5个小时。。。。

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
    char c=getchar();ll a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll L1,L2,L3,D,f[15][15][15][35];
ll Mod=11380;
int main()
{
//    freopen("1.in","r",stdin);
//    freopen("2.out","w",stdout);
    L1=read();L2=read();L3=read();D=read();
    for(ll i=0;i<=D;i++)
    {
        f[0][0][0][i]=1;
    } 
    for (int l1=0; l1 <= L1; l1++)//L1大括号 
    
        for (int l2=0; l2 <= L2; l2++)
        
            for (int l3=0; l3 <= L3; l3++)
            
                for (int d=1; d <= D; d++) 
                {
                    for(ll i=0;i<l1;i++)//大的 
                    {
                        for(ll j=0;j<=l2;j++)
                        {
                            for(ll k=0;k<=l3;k++)
                            {
                                f[l1][l2][l3][d]+=f[l1-i-1][l2-j][l3-k][d]*f[i][j][k][d-1]%Mod;
                                f[l1][l2][l3][d]%=Mod;
                            }
                        }
                    }
                    for(ll j=0;j<l2;j++)//中的 
                    {
                        for(ll k=0;k<=l3;k++)
                        {
                            f[l1][l2][l3][d]+=f[0][j][k][d-1]*f[l1][l2-j-1][l3-k][d]%Mod;
                            f[l1][l2][l3][d]%=Mod;
                        }
                    }
                    for(ll k=0;k<l3;k++)
                    {
                        f[l1][l2][l3][d]+=f[0][0][k][d-1]*f[l1][l2][l3-k-1][d]%Mod;
                        f[l1][l2][l3][d]%=Mod;
                    }
                }
//    for(ll i=0;i<=L1;i++)
//    {
//        for(ll j=0;j<=L2;j++)
//        {
//            for(ll k=0;k<=L3;k++)
//            {
//                if(!i&&!j&&!k)continue;
//                for(ll h=1;h<=D;h++)
//                {
//                    f[i][j][k][h]=(f[i][j][k][h]+(ans1(i,j,k,h)+ans2(i,j,k,h)+ans3(i,j,k,h))%Mod)%Mod;
//                    cout<<ans3(i,j,k,h)<<' '<<ans2(i,j,k,h)<<' '<<ans1(i,j,k,h)<<endl;
//                }
//            }
//        }
//    }
    if(L1==0&&L2==0&&L3==0&&D!=0)
        cout<<0<<endl;
    else
        cout<<((f[L1][L2][L3][D]-f[L1][L2][L3][D-1])>0?(f[L1][L2][L3][D]-f[L1][L2][L3][D-1])%Mod:(f[L1][L2][L3][D]-f[L1][L2][L3][D-1]+Mod)%Mod)<<endl;
    return 0;
}