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

· · 题解

思路

首先发现 l_i 一定为偶数，且左右上下对称，所以可以直接分成四半大小为 \frac{n}4 的部分，每层的最大宽度减半。

设第 i 列有 w_i 个数，根据题目限制，需要满足 w_i\ge w_{i+1}，且 w_1=l,w_l\ge 1。这个东西的个数并不多，具体的，当 l=10 时，状态数等于 \binom{18}{9}=48620。

那么就可以 DP 了，设 f_{i,j,s} 表示第 i 层，用了 j 个方块，这一层的阶梯为 s 的方案数。

考虑从 i 转移到 i+1，设 t 为最大一个阶梯使得长度为 l_{i+1} 且被 s 包含。先把 f_{i,j,s} 转移到 f_{i+1,j,t}，然后再对每一个 j 做高维后缀和即可。最后处理每个阶梯对 j 的影响。

时间复杂度 O(hnlV)，其中 V 表示不同的阶梯数量，最大为 48620。算出来大约为 10^9，不过常数被实现得特别优秀，可以通过。

细节

首先为了记录状态，我们需要对每一个 l 按字典序从小到大枚举阶梯，将每个阶梯映射到一个编号，这一步使用 map 即可。

预处理 mn_{i,s} 表示最大一个阶梯使得长度为 i 且被 s 包含。这个是简单的，mn_{s,i} 的第 x 个位置等于 \min(s_x,i)，套用上面的编号即可。

对于高维后缀和，我们需要预处理一个 del_{i,s} 表示 s 将第 i 位减一后到哪个区间。做高维后缀和的时候，直接从大到小枚举 i，从大到小枚举 s 的编号，让 f_{x,y,del_{s,i}} 加上 f_{x,y,s} 即可。

常数小的原因是长度固定时，阶梯的编号是一个区间，内存访问较为连续，所以可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 7e4+5,mod = 1e9+7;
int cnt;
map<vector<int>,int> mp;
vector<int> now;
int lim,lt[N],rt[N],del[30][N],mn[30][N],sum[N]; 
void dfs(int x)
{
    if(x==lim)
    {
        mp[now] = ++cnt;
        mn[lim][cnt] = cnt;
        for(auto i:now) sum[cnt]+=i;
        if(!lt[lim]) lt[lim] = cnt;
        rt[lim] = cnt;
        for(int i = 1;i<lim;i++)
        {
            vector<int> tmp;
            for(int j = 0;j<i;j++)
                tmp.push_back(min(now[j],i));
            mn[i][cnt] = mp[tmp];
        }
        for(int i = 1;i<lim;i++)
        {
            if(now[i]>(i==lim-1?1:now[i+1]))
            {
                now[i]--;
                del[i][cnt] = mp[now];
                now[i]++;
            }
        }
        return;
    }
    for(int i = 1;i<=now[x-1];i++)
    {
        now[x] = i;
        dfs(x+1);
    }
}
vector<int> vec[N];
int n,h,a[N],f[2][255][N];
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(lim = 1;lim<=10;lim++)
    {
        now.resize(lim);
        now[0] = lim;
        dfs(1);
    }
    cin>>n>>h;
    if(n%4) return cout<<0,0;
    n/=4;
    for(int i = 1,x;i<=h;i++)
    {
        cin>>a[i];
        if(a[i]%2) return cout<<0,0;
        a[i]/=2;
        if(i==1)
        {
            for(int j = lt[a[i]];j<=rt[a[i]];j++)
                if(sum[j]<=n) f[1][sum[j]][j] = 1;
        }
        else
        {
            int now = (i&1);
            for(int j = 0;j<=n;j++)
                for(int k = lt[a[i]];k<=rt[a[i]];k++)
                    f[now][j][k] = 0;
            for(int j = 0;j<=n;j++)
                for(int k = lt[a[i-1]];k<=rt[a[i-1]];k++)
                    (f[now][j][mn[a[i]][k]]+=f[now^1][j][k])%=mod;
            for(int j = n;j;j--)
            {
                for(int x = a[i]-1;x;x--)
                    for(int k = rt[a[i]];k>=lt[a[i]];k--)
                        (f[now][j][del[x][k]]+=f[now][j][k])%=mod;
                for(int k = lt[a[i]];k<=rt[a[i]];k++)
                {
                    if(j+sum[k]<=n) (f[now][j+sum[k]][k]+=f[now][j][k])%=mod;
                    f[now][j][k] = 0;
                }
            }
        }
    }
    int ans = 0;
    for(int i = lt[a[h]];i<=rt[a[h]];i++)
        (ans+=f[h&1][n][i])%=mod;
    cout<<ans;
    return 0;
}