NOI D1T1

Register_int · 2026-07-22 14:20:54 · 题解

简单题。

不难发现，树建出来形如一条主链上面挂若干个点。设 f_{i,j,k} 表示：当前选了 i 个区间，右端点最大为 j，次大为 k。那么有转移：

• 延伸主链，即选择一个区间 (l,r) 满足 k<l\le j，转移到 f_{i+1,r,j}。
• 挂点，即选择一个区间 (l,r) 满足 k<l\le r<j，转移到 f_{i+1,j,r}。

其实有个问题，就是不记下标可能会重复转移。但是容易发现：除了前两个区间，我们每次选的区间左端点严格递增，暴力枚举一下前两个即可。直接转移即可做到 \mathcal{O}(nm^2K)。施前缀和优化，再把第一维滚掉即可通过。时间复杂度 \mathcal{O}(nmK)，空间复杂度 \mathcal{O}(m^2)。

#include <bits/stdc++.h>
#include "segment.h"

using namespace std;

const int mod = 998244353;

inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }

void init(int c, int t) {}

vector<int> segment(int n, int m, int K, vector<int> l, vector<int> r) {
    vector<int> ans(K + 1); ans[1] = n;
    if (K == 1) return ans;
    vector<vector<int>> dp(m + 1, vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (max(l[i], l[j]) <= min(r[i], r[j])) {
                ++dp[max(r[i], r[j])][min(r[i], r[j])];
            }
        }
    }
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) cadd(ans[2], dp[i][j]);
    }
    for (int _ = 3; _ <= K; _++) {
        vector<vector<int>> tmp(m + 1, vector<int>(m + 1));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) cadd(dp[i][j], dp[i][j - 1]);
        }
        for (int i = 0; i < n; i++) {
            for (int j = l[i]; j < r[i]; j++) cadd(tmp[r[i]][j], dp[j][l[i] - 1]);
            for (int j = r[i]; j <= m; j++) cadd(tmp[j][r[i]], dp[j][l[i] - 1]);
        }
        dp = tmp;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) cadd(ans[_], dp[i][j]);
        }
    }
    return ans;
}