题解：P5215 [SHOI2014] 神秘金字塔

· · 题解

这题通过率低的原因是因为题目难读懂吗。

题目要求每层的连通块都满足上下对称与左右对称，所以考虑将联通块分成四等份，我们只用算其中的一个部分即可。

假定我们算左上角的部分，根据题目的限制，这个联通块一定满足以下条件：

  1. 形状为阶梯；
  2. 长、宽均为 \frac{l_i}{2}。

容易发现，当 l_i=20 时，满足以上条件的连通块个数为 \binom{18}{9}=48620。

状态数是相对比较少的。

考虑 dp，并把连通块状态设进 dp 状态里。

先将所有连通块状态爆搜出来，然后依次编号，接着我们设 f_{i,j,s} 表示放完了前 i 层，当前用了 j 个点，现在的连通块状态为 s 的方案数。

考虑转移，我们发现 s 的转移本质上是包含关系，所以预处理 s 的关系后直接用高维后缀和优化即可。

时间复杂度 O(hnlS)，其中 S 为同一边长的连通块的最大状态数。虽然这东西算出来很大，但实际上 n 带有 \frac{1}{4} 常数，l 带有 \frac{1}{2} 常数，且 S 跑不满，数组内存访问比较连续，所以跑的并不慢。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int Maxn=1005,N=66199,mod=1e9+7;
inline void add(int&x,int y){(x+=y)>=mod?x-=mod:0;}
int n,m,a[11];
int tot=0,val[N];
map<vector<int>,int>idx;
vector<int>tpp;
int up[N],nxt[11][N];
int L[11],R[11];
void dfs(int x,int now,int nn){
    if(x==nn+1){
        idx[tpp]=++tot;
        for(int i=0;i<nn;i++)val[tot]+=tpp[i];
        vector<int>tp;
        if(nn<a[0]){
            tp.emplace_back(1);
            for(int i=0;i<nn-1;i++)tp.emplace_back(tpp[i]);
            tp.emplace_back(nn+1);
            up[tot]=idx[tp];
        }
        for(int i=1;i<=nn;i++){
            if(tpp[i-1]>1&&(i==1||tpp[i-1]>tpp[i-2])){
                --tpp[i-1];
                nxt[i][tot]=idx[tpp];
                ++tpp[i-1];
            }
        }
        return;
    }
    for(int i=(x==nn?nn:now);i<=nn;i++){
        tpp.emplace_back(i);
        dfs(x+1,i,nn);
        tpp.pop_back();
    }
}
int f[N][255],sum[N][255];
inline int get(int o,int s){
    for(int i=a[o];i<a[o-1];i++)s=up[s];
    return s;
}
int main(){
//  freopen("score.in","r",stdin);
//  freopen("score.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=m;i++)a[i]=read()/2;
    a[0]=a[1];
    for(int i=a[0];i;i--){
        L[i]=tot+1;
        dfs(1,1,i);
        R[i]=tot;
    }for(int j=1;j<=R[a[0]];j++)sum[j][0]=1;
    if(n%4!=0)return void(puts("0")),0;
    n/=4;int all=0;
    for(int o=1;o<=m;o++){all+=a[o]*2-1;
        for(int s=L[a[o]];s<=R[a[o]];s++){
      int s0=get(o,s);
            for(int i=n;i>=val[s];i--)sum[s][i]=f[s][i]=sum[s0][i-val[s]];
            for(int i=0;i<val[s];i++)sum[s][i]=0;
    }
        for(int j=1;j<=a[o];j++)for(int s=R[a[o]];s>=L[a[o]];s--)if(nxt[j][s]){
            for(int i=all;i<=n;i++)add(sum[nxt[j][s]][i],sum[s][i]);
        }
    }
    printf("%d\n",sum[L[a[m]]][n]);
    return 0;
}