AtCoder

Luogu

分析

假设当前要插入一个数 $x$，那么只能插入到序列末尾或者一个 $<x$ 的数之前。

我们把操作序列转化为一棵树，每个节点都是一个二元组 $(w, t)$，表示第 $t$ 次操作在其父节点插入的数前插入了 $w$。为了方便我们新建一个点 $(0, 0)$ 作为根，表示插入到序列末尾。

那么这棵树满足：$t$ 是 $[0, n]$ 的排列、$w\in [0, k]$、$w_{fa(u)} < w_u \land t_{fa(u)} < t_u$。可以发现这样子的树和满足条件的操作序列是双射。

现在考虑如何对这样的树计数。考虑 DP，设 $dp_{i, j}$ 表示 $i$ 个节点的、根的 $w$ 等于 $j$ 的树的个数。

考虑转移。考虑根的儿子中 $t$ 最小的，枚举其子树大小与 $w$ 值，并用组合数分配子树中的 $t$ 值，有
$$
dp_{i, j} = \sum_{l = 1}^{i - 1} {i - 2 \choose l - 1} dp_{i - l, j} \sum_{w = j + 1}^k dp_{l, w}
$$
后缀和优化转移即可。时间复杂度 $\mathcal{O}(n^2k)$.

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 300 + 10;

int n, k, mod;
int C[N][N], dp[N][N], s[N][N];

int main() {
    n = read(), k = read(), mod = read();
    for (int i = C[0][0] = 1; i <= n; ++i)
        for (int j = C[i][0] = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    for (int i = 0; i <= k; ++i) dp[1][i] = 1;
    for (int i = 0; i <= k; ++i) s[1][i] = k - i + 1;
    for (int i = 2; i <= n + 1; ++i) {
        for (int j = 0; j <= k; ++j)
            for (int l = 1; l < i; ++l)
                dp[i][j] = (dp[i][j] + 1ll * C[i - 2][l - 1] * dp[i - l][j] % mod * s[l][j + 1]) % mod;
        for (int j = k; ~j; --j) s[i][j] = (s[i][j + 1] + dp[i][j]) % mod;
    }
    printf("%d\n", dp[n + 1][0]);
    return 0;
}