题解：P17140 [NOI 2026] 线段（暂无数据）

pbds_ · 2026-07-26 14:24:31 · 题解

模拟赛放 VP NOI，转移算重没调出来，我是区。

首先，如果线段互不包含，那么树的形态一定是一条链（因为选择的这些线段一定会有 l 和 r 单调不降，并且只有相邻两个选择的线段能有重叠，否则三个线段在某个位置重叠就成环了）。但是线段有包含，那么树的形态一定是一条链上挂了一些点（也就是“毛毛虫”）。

设 f_{i,j,x} 为现在选了 i 条线段，下一条线段的左端点至少为 j，选的线段的最大右端点为 x 的方案数。于是可以有两种转移：

• 选一条线段满足其右端点在原来的最大右端点的右边，延长链。设选择的线段是 [l,r]，那么就有 f_{i,j,r}\gets f_{i,j,r}+\sum_{y=0}^l f_{i-1,y,j-1}（l+1\le j\le r）。
• 选一条线段满足其被目前右端点最大的线段所包含，在链上挂点。设选择的线段是 [l,r]，那么就有 f_{i,r+1,x}\gets f_{i,r+1,x}+\sum_{y=0}^l f_{i-1,y,x}。

这样转移可能会算重（两条线段左端点重叠的时候一个状态会被两种转移各转移一遍），但是我们发现除了前两条线段之外不可能出现左端点重叠的情况（否则就有三条线段交在同一个位置成环了），于是 i\le 2 时暴力，i>2 时正常转移即可。

此时时间复杂度 O(nm^2k)，难以通过。但是显然 j 这一维可以前缀和优化，于是时间复杂度 O(nmk)，但是空间复杂度 O(m^2k)，仍然无法通过。然后我们再给 i 这一维上滚动数组优化，空间复杂度 O(m^2)，就可以通过了。

#include"segment.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=998244353;
ll f[2][1005][1005];
int cc[1005][1005]; 
void init(int c,int t){

}
struct p{
    int l,r;
    friend bool operator<(const p&a,const p&b){
        if(a.l==b.l)return a.r<b.r;
        return a.l<b.l;
    }
    friend bool operator==(const p&a,const p&b){
        return a.l==b.l&&a.r==b.r;
    }
}a[100005];
vector<int>segment(int n,int m,int k,vector<int>l,vector<int>r){
    m++;
    for(int i=1;i<=n;i++)a[i].l=l[i-1],a[i].r=r[i-1];
    sort(a+1,a+n+1);
    vector<int>ans(k+1);
    ans[1]=n;
    if(k==1)return ans;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i].r>=a[j].l&&a[j].r>=a[i].l)f[0][min(a[i].r,a[j].r)+1][max(a[i].r,a[j].r)]++,ans[2]++; 
    for(int j=1;j<=m;j++)for(int x=0;x<=m;x++)f[0][j][x]=(f[0][j][x]+f[0][j-1][x])%mod;
    for(int i=3;i<=k;i++){
        for(int j=0;j<=m;j++)for(int x=0;x<=m;x++)f[i&1][j][x]=0;
        for(int j=1;j<=n;j++){
            for(int x=a[j].l+1;x<=a[j].r;x++){
                f[i&1][x][a[j].r]=(f[i&1][x][a[j].r]+f[i&1^1][a[j].l][x-1])%mod;
            }
            for(int x=a[j].r;x<=m;x++){
                f[i&1][a[j].r+1][x]=(f[i&1][a[j].r+1][x]+f[i&1^1][a[j].l][x])%mod;
            } 
        }
        for(int j=0;j<=m;j++)for(int x=0;x<=m;x++)ans[i]=(ans[i]+f[i&1][j][x])%mod;
        for(int j=1;j<=m;j++)for(int x=0;x<=m;x++)f[i&1][j][x]=(f[i&1][j][x]+f[i&1][j-1][x])%mod;
    }
    return ans;
}