CF102428F Fabricating Sculptures

[Fabricating Sculptures](https://vjudge.net/contest/344794#problem/F)

## 题意

米格尔·安杰洛（Miguel Angelo）是一位伟大的雕塑家，以其户外雕塑作品而闻名。在他的家乡，人们经常能在广场和花园里看到他的作品。人们喜爱这些雕塑，不仅因为它们美观，还因为即使经历数十年，看上去仍然像新的。

这些雕塑不易老化，这得益于米格尔和他的团队多年来开发的材料与工艺。

为了制作雕塑，他首先通过堆叠防水石膏块（他秘密的材料）来搭建底座：将若干个“块堆”（stack）按一条直线排成一排。所有石膏块完全相同，并且每一堆至少包含一个石膏块。为了让结构更稳固，他会在这些块堆的前后各放置一块大的玻璃板（即一块在块堆后面，一块在块堆前面）。然后他会等待雨水降落，不管需要等多久。

如果该结构在这个过程中**不会积水**，米格尔就确信这个底座可以用来制作一件经久耐用的艺术品。

注意：**当一个石膏块的左右两侧（左边和右边）都存在障碍（其他石膏块）时，水就会在该石膏块上方积累。**

题目中的图片展示了若干不同底座的正视图。它们都由 **3 个块堆**组成，总共使用 **6 个石膏块**，并且每个块堆至少一个石膏块（满足要求）。其中，左边的 **8 种**底座不会积水，而右边的 **2 种**会积水。

米格尔目前接到大量雕塑请求。虽然他可以自由创作，但他希望公平起见，所有雕塑都使用相同数量的块堆与相同数量的石膏块。由于他不想把完全相同的雕塑卖给不同客户，因此每次都会构造一个不同的底座。

他担心自己无法满足所有请求。请你帮助他计算：给定块堆数量和石膏块总数时，**不积水**的不同底座共有多少种。

## Sol

首先想办法刻画一下这个题目要求的状态。大概是只能是“凸“形的，不能是”凹“形的。这个凸形的本身就很有灵性了，凸形意味着它是 **单峰** 的。

简单考虑从左到右， 比如说是设 $dp_{i, n, j}$ 表示现在搞到了第 $i$ 个 stack，还剩下 $n$ 个 block 可以用，当前 stack 已经用了 $j$ 个 block。考虑转移是不可能的，因为发现这样只能处理单调的情况，对于“凸”这种单峰的形式是做不了的。

实际上处理单峰的手段也比较少吧。**核心思路** 基本都是想办法弄成单调的。比如说：**三分实际上是利用了单峰函数一阶导为一次函数单调** 。考虑怎么把问题刻画成单调的。

如果我们是从下往上堆，你会发现凸这个性质在每一“层”都只需要是数量**单调不增即可**并且**连续的一段** block。比如说，最底下（记为 $h_1$ 层）放了5个 block，那么第四层一定是**连续的一段，数量 ** $\leq 5$ 即可。

这样计数的话，我们只要考虑枚举每一层放的数量（仅仅依赖于上一层放的数量）+ 放的位置（可以想象成一个“滑动窗口”在每一层上）

设 $dp_{i, j}$ 表示当前层还剩下 $i$ 个block可以放，上一层放了 $j$ 个。考虑如何转移： 
$$
dp_{i, j} = \sum_{k = 1}^{\min(i,j)} dp_{i-k, k} \times (j - k + 1)
$$
然后我们会需要枚举 $O(B)$ 个 block （注意实际上按照现在状态的定义，最多是放 $B - S$ 个，因为最底下一层必须全部放一个），然后枚举上一层放了多少个 $O(S)$，然后再算这个和式 $O(S)$，然后 $B,S$ 同阶，可以认为是立方级别的复杂度。

观察到这个和式是比一个比较经典的下标和为 $i$ 的和式，也就是对对角线求和。那么可以考虑前缀和优化。不过由于这个转移比较 naive，所以需要一些技巧来处理这个和式。

首先是经典的参变分离：
$$
dp_{i, j} = (j + 1) \sum_{k = 1}^{\min(i,j)}  \times dp_{i-k, k} + \sum_{k = 1}^{\min(i,j)} k \times dp_{i - k, k}
$$
注意这里的 $i$ 对于和式是一个常量，所以直接提出去。

这样的话，对于每一个 $i$，可以线性预处理出 $dp_{i - k,k}$ 和 $k \times dp_{i - k, k}$ 的前缀和。具体的，记第一项的前缀和为 $A_k$, 那么 
$$
A_k = A_{k - 1} + dp_{s - k, k}
$$
记第二项的前缀和为 $Bw_k$，那么 
$$
Bw_k = Bw_{k - 1} + k \times dp_{s - k, k}
$$
那么转移写成 
$$
dp_{i, j } = (j + 1) \times A_m - Bw_m \bmod p
$$
其中 $p = 10^9 + 7$ 为题目给定的模数，$m = \min(i, j)$

## Idea

- 单峰状态的处理手段：转换成单调
- 经典和式的处理

## Code

知道你们爱看

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

#define int long long
const int mod = 1e9 + 7;
const int SIZE = 5000 + 5;

int dp[SIZE][SIZE], A[SIZE], Bw[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

signed main() {
    // freopen("test.in", "r", stdin);
    int S = read(), Btotal = read();
    int E = Btotal - S; 
    int W = S;

for (int n = 0; n <= W; ++n) dp[0][n] = 1;

for (int s = 1; s <= E; ++s) {  
        A[0] = Bw[0] = 0;

int K = min(s, W);
        for (int k = 1; k <= K; ++k) {
            A[k]  = (A[k - 1] + dp[s - k][k]) % mod;
            Bw[k] = (Bw[k - 1] + 1ll * k * dp[s - k][k]) % mod;
        }

for (int n = 1; n <= W; ++n) { 
            int m = min(s, n);
            long long val = (n + 1) * A[m] - Bw[m];
            val %= mod;
            if (val < 0) val += mod;
            dp[s][n] = val;
        }
    }

cout << dp[E][W] << "\n";
    return 0;
}
```