#P11495. [2023省队模拟]星图

    ID: 10643 传统题 1500ms 888MiB 尝试: 6 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-笛卡尔树期望线性性线性 DP滚动数组离散化分段多项式导数积分转化模逆元

[2023省队模拟]星图

题目描述

Sandy DuckSandy\ Duck 现在正在满天繁星下发呆,看见了天上一部分区域的 nn 颗星星。

Sandy DuckSandy\ Duck 用翅膀比划着建立了一个平面直角坐标系,并将星星按照横坐标(假定每颗星星横坐标不相同)从小到大编号 1∼n1\sim n 。

但是由于观测不清,无法知道确切纵坐标,只知道 ii 号星星的纵坐标 aia_i 是区间 [li,ri) [l_i,r_i) 内的一个均匀随机实数。

Sandy DuckSandy\ Duck 希望将这一块天空划分为一整个树状星座。具体地,星座构成一棵二叉树的结构,对于 ii 号星星:

⋆ ii 号星星的左儿子的标号为满足下列条件且最大化对应的 aja_j 的 jj 。 11 . 1≤j<i1 \le j < i 。 22 . aj<aia_j < a_i 。 33 . jj 到 ii 的星星的纵坐标均不超过 max{aj,ai}max\{a_j , a_i\} 。 特别地,如果没有 jj 满足这样的条件,则它没有左儿子。

⋆ ii 号星星的右儿子的标号为满足下列条件且最大化对应的 aja_j 的 jj 。 11 . i<j≤ni < j \le n 。 22 . aj<aia_j < a_i 。 33 . ii 到 jj 的星星的纵坐标均不超过 max{ai,aj}max\{a_i, a_j\} 。 特别地,如果没有 jj 满足这样的条件,则它没有右儿子。

在这样的意义之下,星座对应的树自然也有了"根"。 Sandy DuckSandy\ Duck 认为,星座的复杂程度取决于每颗星星在星座中的位置。具体地,它定义星座上某颗星星的深度为到“根”的最短路径经过的边数,星座的复杂程度为所有星星的深度之和。

现在,它想问一问你,星座的复杂程度的期望是多少呢?由于 Sandy DuckSandy\ Duck 讨厌无穷无尽的小数,它只需要你告诉它答案对 998244353998244353 取模之后的结果。

【提示】 考虑 nn 个格子均匀分布在某个区间的连续随机变量 X1,X2,…,XnX_1,X_2,\ldots ,X_n 的时候,我们可以认为存在两个变量相同的概率为 00 。

输入格式

第一行一个正整数 nn ,表示星星的个数。 接下来 nn 行,第 ii 行两个正整数 li,ril_i, r_i ,表示 ii 号星星的纵坐标为 [li,ri)[l_i, r_i) 之中的随机实数。

输出格式

输出仅一行一个非负整数,表示星座的复杂程度的期望。

数据范围

设 m=max⁡1≤i≤nrim=\max_{1\le i\le n}r_i 。

对于所有测试点: 1≤n≤3001\le n\le 300 ,且 ∀1≤i≤n,1≤li<ri≤998244352\forall 1\le i\le n,1\le l_i < r_i\le 998244352 。

每个测试点的具体限制见下表:

测试点编号 n≤n \le m≤m \le 特殊限制
1∼41\sim 4 66 55 无
5∼65\sim 6 99 998244352998244352 所有 [li,ri][l_i,r_i] 全部相等
7∼87\sim 8 2020 无
9∼109\sim 10 998244352998244352
11∼1511\sim 15 100100
16∼2016\sim 20 300300

输入样例 1

3
1 3
1 3
1 3

输出样例 1

665496238

输入样例 2

3
1 2
1 2
1 3

输出样例 2

831870297

样例解释

样例 11 :

此时, a1,a2,a3a_1,a_2,a_3 均在同一区间 [1,3)[1,3) 中均匀分布。

由【提示】部分,我们可以转而考虑 a1,a2,a3a_1,a_2,a_3 的严格大小关系,并用一个排列 p∈S3p\in S_3 来表示这种大小关系。 ∀j≠k,pj>pk⇔aj>ak\forall j\neq k,p_j > p_k\Leftrightarrow a_j > a_k 。

那么,每一种排列的出现概率均为 13!=16\frac{1}{3!}=\frac 1 6 ,考察每种排列的情况下,星座的复杂程度:

p={1,2,3}p=\{1,2,3\} ,复杂程度为 33 。 p={1,3,2}p=\{1,3,2\} ,复杂程度为 22 。 p={2,1,3}p=\{2,1,3\} ,复杂程度为 33 。 p={2,3,1}p=\{2,3,1\} ,复杂程度为 22 。 p={3,1,2}p=\{3,1,2\} ,复杂程度为 33 。 p={3,2,1}p=\{3,2,1\} ,复杂程度为 33 。

因此,复杂程度的期望为 16(3×4+2×2)=83\frac{1}{6}(3\times 4+2\times 2)=\frac 8 3 ,对 998244353998244353 取模之后的结果为 665496238665496238 。

样例 22 :

按照 a3a_3 的取值范围来讨论:

a3∈[1,2)a_3\in [1,2) ,发生概率为 12\frac 1 2 :这中情况在【样例 11 】中已经讨论过,期望为 83\frac 8 3 。

a3∈[2,3)a_3\in [2,3) ,发生概率为 12\frac 1 2 :此时必然有 a3>a1,a3>a2a_3 > a_1,a_3 > a_2 。我们接着考虑可能的排列 pp (每种排列出现概率均为 12\frac 1 2 ):

p={1,2,3}p=\{1,2,3\} ,复杂程度为 33 。

p={2,1,3}p=\{2,1,3\} ,复杂程度为 33 。

因此,所有情况中,复杂程度的期望为 $\frac{1}{2}\times \frac 8 3+\frac 1 2\times (\frac 3 2 +\frac 3 2)=\frac {17} 6$ ,对 998244353998244353 取模之后的结果为 831870297831870297 。