模型:将区间按左端点排序,设公共长度为 L,左端点为升序数组 a1,…,an。
相交判定:两个区间相交当且仅当左端点差小于 L。
预处理:
DP 定义:f[i] 表示从第 i 个“尚未被覆盖”的区间开始,选出一组满足条件的方案数。
在一条直线上有 n 段栅栏,所有栅栏的长度都相同。第 i 段栅栏从位置 li 到位置 ri,构成闭区间 [li,ri]。两段栅栏若有至少一个公共点(即使仅端点重合),则称它们接触。形式化地,对于两段栅栏 [l1,r1] 和 [l2,r2],它们接触当且仅当 max(l1,l2)≤min(r1,r2)。
现在要从中选出若干段栅栏作为标记,要求满足以下条件:
请你计算一共有多少种不同的标记方案。由于答案可能很大,请将结果对 998244353 取模后输出。
约束条件:栅栏的总数 n 满足 2≤n≤105,所有位置 li 和 ri 满足 1≤li≤ri≤2×109。保证所有栅栏的长度 ri−li+1 完全相同。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册