题意
对于一个长度为 \(N\) 的序列 \(H\)，可以通过如下方式构造一个序列 \(P\)：
若存在 \(j \in \left[1, i\right)\)，使得 \(H_j > H_i\)，则 \(P_i = \max\limits_{j \in \left[1, i\right) \land H_j > H_i} j\)，否则 \(P_i = -1\)。
给定一个长度为 \(N\) 的序列 \(X\)，求所有满足如下条件的 \(H\) 序列可以构造出的 \(P\) 序列的方案数：
\(\forall i \in \left[1, N\right], H_i \in \left[1, X_i\right]\)
对 \(10^9 + 7\) 取模。
\(1 \le N \le 100, 1 \le X_i \le 10^5\)。
题解
考虑从 \(i\) 向 \(P_i\) 连边，发现会连成一个森林，考虑将 \(H_0\) 设为 \(+\infty\)，这样就可以形成一颗以 \(0\) 为根的树。可以发现其一定有如下性质：
- 对于任意节点 \(u\)，有 \(\forall v \in \operatorname{subtree}_u \Rightarrow H_u > H_v\)
证明：
对于任意节点 \(x\)，有 \(H_{fa_x} > H_{x}\)，通过不等式的传递性可证。
- 一定存在一种 \(\tt{DFS}\) 方式使得 \(\forall i \in \left[1, N\right]\)，有 \(\operatorname{dfn}(i) = i\)
证明：
考虑 \(\tt{DFS}\) 到节点 \(u\) 后，下一个访问的节点是否可以是 \(u + 1\)。
- 若 \(H_u > H_{u + 1}\)，那么 \(u\) 和 \(u + 1\) 之间一定有边相连；
- 否则对于任意 \(i > u + 1\)，其不会向 \(u\) 连边，所以在 \(\tt{DFS}\) 过程中，不会访问其他节点。
- 对于节点 \(u\) 的儿子节点序列 $v_1 < v_2 < \cdots v_k $，有 \(\forall i \in \left[1, k\right], H_{v_i} \le H_{v_{i + 1}}\)
证明：
考虑若存在 \(i < j\)，使得 \(H_{v_i} > H_{v_j}\)，那么 \(v_i\) 和 \(v_j\) 之间一定有边相连，矛盾。
- 对于节点 \(u\) 的儿子节点序列 $v_1 < v_2 < \cdots v_k $，有 \(\forall i \in \left[1, k\right], H_{v_i} < H_u\)
证明：
考虑若存在 \(i\)，使得 \(H_{v_i} \ge H_u\)，那么 \(v_i\) 和 \(u\) 之间一定没有边相连，矛盾。
至此我们可以得出对于一个节点 \(u\)，有 \(H_u \ge \max\left\{\max\limits_{v \in \operatorname{son}_u}H_v + 1,\max\limits_{v \in \operatorname{brother}_u \land v < u}H_v\right\}\)。
考虑如何在给定 \(P\) 序列即树的形态的情况下构造出一组合法的 \(H\) 或报告无解。发现从叶子节点向上构造并直接将 \(H_u\) 的值取至下界一定不劣，因此我们就得出了一个基于贪心的构造方法。
同时我们可以发现按此方法构造出的 \(H\) 序列其值不超过 \(N\)，因此若 \(X_i > N\) 那么使其对 \(N\) 取 \(\min\) 即可。
考虑按此方法进行 \(\tt{DP}\)，设 \(f_{l, r, x}\) 表示由编号区间 \(\left[l, r\right]\) 中的点构成的树且 \(l\) 节点作为根节点有 \(H_l = x\) 的方案数，\(g_{l, r, x}\) 表示由编号区间 \(\left[l, r\right]\) 中的点构成的森林且对于编号最大的根节点 \(u\) 有 \(H_u = x\) 的方案数。
初始状态为 \(\forall i \in \left[1, N\right], f_{i, i, 1} = 1\)。
接下来考虑如何转移，首先我们有
\[f_{l, r, x} = g_{l + 1, r, x - 1} \]然后考虑 \(g_{l, r, x}\) 的转移，我们可以枚举其最后一棵子树的编号区间和根节点权值，有
\[g_{l, r, x} = \sum\limits_{m = l}^{r - 1}\sum\limits_{\max\limits\left\{a, b\right\} = x} g_{l, m, a} \times f_{m + 1, r, b} \]考虑若 \(b = x\)，那么使得枚举的子树作为其最右侧的子树即可；反之则有 \(a = x\)，使得枚举的子树并入其最右侧的子树即可。
最后答案即为 \(\sum\limits_{i = 1}^{N}g_{1, N, i}\)。
使用前缀和优化转移即可做到 \(\mathcal{O}(N^4)\) 的时间复杂度，可以通过本题。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
namespace MODINT {
constexpr valueType MOD = 1e9 + 7;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
}// namespace MODINT
using namespace MODINT;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
ValueVector H(N + 1);
for (valueType i = 1; i <= N; ++i) {
std::cin >> H[i];
H[i] = std::min(H[i], N);
}
auto ModSum = [](valueType const &a, valueType const &b) -> valueType {
return sum(a, b, MOD);
};
ValueCube F(N + 1, ValueMatrix(N + 1, ValueVector(N + 1, 0)));
ValueCube G(N + 1, ValueMatrix(N + 1, ValueVector(N + 1, 0)));
ValueCube SumF(N + 1, ValueMatrix(N + 1, ValueVector(N + 1, 0)));
ValueCube SumG(N + 1, ValueMatrix(N + 1, ValueVector(N + 1, 0)));
for (valueType i = 1; i <= N; ++i) {
F[i][i][1] = 1;
G[i][i][1] = 1;
std::partial_sum(F[i][i].begin(), F[i][i].end(), SumF[i][i].begin(), ModSum);
std::partial_sum(G[i][i].begin(), G[i][i].end(), SumG[i][i].begin(), ModSum);
}
for (valueType len = 1; len <= N; ++len) {
for (valueType l = 1; l + len <= N; ++l) {
valueType const r = l + len;
for (valueType k = 1; k <= H[l]; ++k) {
F[l][r][k] = G[l + 1][r][k - 1];
G[l][r][k] = G[l + 1][r][k - 1];
}
for (valueType mid = l; mid < r; ++mid) {
for (valueType k = 1; k <= H[mid + 1]; ++k) {
Inc(G[l][r][k], mul(G[l][mid][k], SumF[mid + 1][r][k - 1]));
Inc(G[l][r][k], mul(SumG[l][mid][k - 1], F[mid + 1][r][k]));
Inc(G[l][r][k], mul(G[l][mid][k], F[mid + 1][r][k]));
}
}
std::partial_sum(F[l][r].begin(), F[l][r].end(), SumF[l][r].begin(), ModSum);
std::partial_sum(G[l][r].begin(), G[l][r].end(), SumG[l][r].begin(), ModSum);
}
}
std::cout << SumG[1][N][N] << std::endl;
return 0;
}