线段 NOI 2026

[NOI 2026] 线段

简单题。

题目链接： [NOI 2026] 线段 。

题目描述：

给若干个区间，对于每一个 $s=1,2,\cdots,k$ ，求大小恰好为 $s$ 的区间构成的子集的区间图联通无环的方案数。

$n\le3000,m\le1000,k\le200$ 。

$l_i,r_i \in [1,m]$ 。

定义 $f_{i,j,k}$ 表示右端点为 $i$ ，次右为 $j$ ，个数为 $k$ 的方案数。

那么考虑选择的集合是否超出 $i$ ：

• 超出，此时有 $f_{i,j,k}\to f_{r_p,i,k+1}$ 。
• 不超出，此时有 $f_{i,j,k}\to f_{i,r_p,k+1}$ 。

对着转移就行，代码不放了。

PS: 直接转移是 $O(nm^2k)$ 的，为了能前缀和优化，不能直接算 $f_{i,j,k}$ 或着直接让 $f_{i,j,k}$ 做贡献。要用类似于 Random Painting 的思路转移。