题目链接

题意

在一个排列中我们定义 $x$ 是好的当且仅当排列中所有包含 $x$ 的子串中恰好有 $m$ 种不同的子串内元素最大值。询问恰好有 $k$ 个好元素的 $n$ 排列数量。

$m,k \le n \le 100$

分析

不难发现排列中包含 $x$ 的子串的不同的子串内最大值数量等于 $x$ 向左的最长上升子序列长度加上向右的最长上升子序列长度，而这个值是等于对原序列建立笛卡尔树后 $x$ 到树根之间的距离。询问转化为询问有多少个 $n$ 排列满足其笛卡尔树上恰好有 $k$ 个结点深度为 $m$。

考虑笛卡尔树的建立过程，我们每次从整个序列中取出最大值，然后从这个最大值所在的位置将原序列分为两半递归构造。我们可以考虑进行区间 DP，$f[l][r][m][k]$ 表示 $l$ 到 $r$ 之间的满足笛卡尔树上恰好有 $k$ 个点深度为 $m$ 的排列数量。转移时我们枚举一个 $m \in [l,~r]$，钦定他为区间内的最大值，然后将区间分为两半，再暴力枚举这 $k$ 个深度为 $m$ 的点中有几个是在左区间，最终使用组合数将左右区间的两个排列合并起来即可。进一步我们发现 $l$ 和 $r$ 的具体值我们并不关心，因此仅记录区间长度即可。

时间复杂度 $O(n^2 \times m \times k^2)$，空间复杂度 $O(n \times m \times k)$。需要加上一些剪枝。

吐槽

比赛时我花了半个小时，在此前只会写笛卡尔树板子完全不了解笛卡尔树上一点到根路径长度等于其向左和向右的最长上升子序列长度和的情况下想出了这个做法，当时还是比较高兴能够想出这一做法的。但是 $n \le 100$ 而且复杂度接近 $O(n^5)$，赛时认为有更加优秀的做法因此没有提交差不多写完的代码。痛失九十多 Rating 。

代码

View on GitHub

/**
 * @author Macesuted (i@macesuted.moe)
 * @copyright Copyright (c) 2021
 * @brief
 *      My Solution: https://macesuted.moe/article/cf1580b
 */

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define maxn 105

typedef pair<int, int> pii;

int f[maxn][maxn][maxn];
int C[maxn][maxn], fac[maxn];

int n, m, k, mod;

int dp(int len, int up, int cnt) {
    if (!len) return cnt == 0;
    if (up == 1) return cnt == 1 ? fac[len] : 0;
    if ((cnt - 1) * 2 > len) return 0;
    if (f[len][up][cnt] >= 0) return f[len][up][cnt];
    int answer = 0;
    for (int mid = 0; mid < len; mid++)
        for (int t = 0; t <= cnt; t++)
            answer = (answer +
                      dp(mid, up - 1, t) * dp(len - mid - 1, up - 1, cnt - t) % mod * C[len - 1][mid]) %
                     mod;
    return f[len][up][cnt] = answer;
}

void work(void) {
    memset(f, -1, sizeof(f));
    cin >> n >> m >> k >> mod;
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod;
    for (int i = 0; i < maxn; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    cout << dp(n, m, k) << endl;
    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cout << setiosflags(ios::fixed) << setprecision(11);
    int _ = 1;
    // cin >> _;
    while (_--) work();
    return 0;
}