[AGC024E] Sequence Growing Hard 题解

[AGC024E] Sequence Growing Hard 题解

首先手玩一下样例，考虑在哪些位置插入是合法，假设在 \(pos\) 位置前插入 \(x\)，则如果 \(x > a_{pos}\)，则显然字典序会变大，否则如果 \(a_{pos} = x\) 需要找到 \(pos\) 位置之后第一个不为 \(x\) 的位置，假设该位置为 \(t\)，则如果 \(x > a_t\)，那么字典序会变大。

考虑一段连续的由相同数字组成的子串，那么无论在其中哪个位置插入，最后序列的结果都是一样的，所以我们简化一下合法位置的条件，不妨钦定只能在连续段最后一个数后插入，那么只需要满足 \(x > a_{pos}\) 就行了。

进一步观察，发现对于同一个 \(A\)，在不同的合法位置插入一个数，得到的序列 \(A'\) 都是不一样的，这启发我们只需要计数不同的插入方案数，而不是不同的序列组方案数。

观察不断插入的过程，每一次都在一个数前面插入，可以被看作一个建树的过程，其中每一个节点都是一个序列元素，上文中插入 \((x, pos)\) 的时候，认为 \(a_{pos}\) 是 \(x\) 的父亲。

一棵操作树的每一个拓扑序对应了一个插入方案，那么不同的插入方案数等价于：所有可能的操作树的拓扑序个数之和。

设 DP 状态 \(f_{i, j}\) 表示对于所有大小为 \(i\) 的树，根节点权值为 \(j\) 拓扑序个数之和，转移枚举第一个访问的子树的子树大小 \(l\)，那么该子树内点的拓扑序 独立于 外面点的拓扑序，用组合数分配这些遍历顺序。

具体而言，子树内的贡献是 \(\sum_{k > j} f_{l, k}\)，子树外的贡献是 \(f_{i - l, j}\)，遍历顺序的分配的系数是 \(\binom{i - 2}{l - 1}\)。

时间复杂度：\(O(n^3)\)。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <ctime>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long double ld;
const int N = 300 + 10;int n, k, mod, f[N][N], s[N][N], C[N][N];signed main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> k >> mod;for(int i = 0; i <= k; i ++) f[1][i] = 1, s[1][i] = k - i + 1;C[0][0] = 1;for(int i = 1, j; i <= n; i ++)for(j = 1, C[i][0] = 1; j <= i; j ++)C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;for(int i = 2; i <= n + 1; i ++) {for(int j = 0; j <= k; j ++) {for(int l = 1; l < i; l ++) {f[i][j] = (f[i][j] + C[i - 2][l - 1] * f[i - l][j] % mod * s[l][j + 1]) % mod;}}for(int j = k; j >= 0; j --) s[i][j] = (s[i][j + 1] + f[i][j]) % mod;}cout << f[n + 1][0] << '\n';return 0;
}