「AGC 024E」Sequence Growing Hard
zhylj
·
·
题解
阅读体验，博客
题目
求有多少个序列组 A_0,A_1,\cdots,A_n 满足：
对 M 取模。
## 分析
大概是一个比较不同的二维 dp 的切入方法。
先考虑一个弱化版的问题：给定 $A_n$，求有多少种可能的序列组 $A_0,\cdots,A_{n-1}$.
我们发现，由 $A_n$ 得到 $A_0$ 的过程相当于每次从 $A_n$ 中删一个数，并要求字典序递减。
「字典序递减」看上去不是很好处理，于是考虑其是否存在等价条件：假如我们删了 $s$ 的第 $i$ 个位置得到了 $s'$，可以发现，$s$ 的前 $i - 1$ 个位置构成的前缀和 $s'$ 的前 $i - 1$ 个位置构成的前缀完全相同，我们实际上需要比较的是这两个串从 $i$ 开始的后缀的字典序。
注意到我们有 $s_{j+1}=s'_{j}(j\ge i)$，想象一下比较字典序的过程：
- 若 $s_i = s'_i = s_{i+1}$，则比较位置 $s_{i + 1}$ 和 $s'_{i+1}$.
- 若 $s_{i+1} = s_i = s'_{i+1} = s_{i+2}$，则比较位置 $s_{i+2}$ 和 $s_{i+2}'$.
- ...
故「$s$ 删去第 $i$ 个元素后字典序变小」的条件实际上等价于：「$s_i$ 大于 $i$ 之后第一个不等于 $s_i$ 的元素」。
但是，我们注意到，如果 $s$ 存在一段相同的元素，那么删除这段元素中的任何一个所得到的结果完全相同，它们不应该被重复统计，所以我们不妨给这段元素人为地定一个顺序：直觉告诉我们，定义每次只能删除一段连续元素中最右边的元素是最为方便的。
然后，我们再重新审视一下我们的条件，发现它惊人的简洁：「$s_i > s_{i+1}$」（当然，最后一个元素是一定能删的）.
于是我们考虑 dp，设 $f_{i,j}$ 表示长度为 $i$ 的 $A_i$，只用了 $[1,j]$ 中的整数的方案数。
转移的时候，为了避免重复，我们枚举**第一个** $1$ 出现的位置 $k$，以及这个 $1$ 被删除的时刻 $p$。那么就意味着：$1$ 后面的 $i - k$ 个数必须在前 $p - 1$ 个时刻中全部被删除。
于是有：
$$
f_{i,j} = \sum_{k=1}^i \sum_{p=i-k+1}^i f_{k-1,j-1}f_{i-k,j}{p-1\choose i-k}
$$
注意到 $\sum {p-1\choose i-k}$ 只和 $i,k$ 有关，而与 $j$ 无关，所以可以预处理，时间复杂度就做到了 $\mathcal O(n^3)$.
然后这题就做完了。
## 代码
```cpp
const int kN = 3e2 + 5;
int N, K; ll M;
ll C[kN][kN], t[kN][kN];
void Init() {
for(int i = 0; i <= N; ++i) {
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
}
for(int i = 1; i <= N; ++i)
for(int k = 1; k <= i; ++k)
for(int p = i - k + 1; p <= i; ++p)
t[i][k] = (t[i][k] + C[p - 1][i - k]) % M;
}
ll f[kN][kN];
void Calc() {
f[0][0] = 1;
for(int j = 1; j <= K; ++j) {
f[0][j] = 1;
for(int i = 1; i <= N; ++i) {
for(int k = 1; k <= i; ++k) {
ll tmp = f[k - 1][j - 1] * f[i - k][j] % M;
f[i][j] = (f[i][j] + tmp * t[i][k]) % M;
}
f[i][j] = (f[i][j] + f[i][j - 1]) % M;
}
}
}
int main() {
rd(N, K, M);
Init(); Calc();
printf("%lld\n", f[N][K]);
return 0;
}
```