1 条题解

  • 1
    @ 2022-2-22 19:16:57

    在我的个人博客中阅读

    CF1580B Mathematics Curriculum

    题目大意

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

    m,kn100m,k \le n \le 100

    分析

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

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

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

    代码

    View On GitHub

    Code
    /**
     * @author Macesuted (i@macesuted.moe)
     * @copyright Copyright (c) 2021
     */
    
    #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;
    }
    
    • 1

    信息

    ID
    7327
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者