[R21G]期望排名 - 代码源竞赛平台

时空限制

2S/256M

题目描述

给定 $n$ 个独立的离散型随机变量。第 $i$ 个随机变量 $X_i$ 有 $m_i$ 个可能的取值，记为 $a_{i,1}, a_{i,2}, \dots, a_{i,m_i}$（保证所有随机变量的取值两两不同），对应的概率分别为 $p_{i,1}, p_{i,2}, \dots, p_{i,m_i}$（满足 $\sum_{j=1}^{m_i} p_{i,j} = 1$）。

有 $Q$ 次询问。每次询问给出三个整数 $l, r, k$（满足 $l \leq k \leq r$），要求计算：当仅考虑第 $l$ 个到第 $r$ 个随机变量（共 $r-l+1$ 个）时，第 $k$ 个随机变量的取值在这些随机变量取值构成的集合中的期望排名（排名定义为：将所有随机变量的取值按从小到大排序后，目标值所处的位置序号）。计算结果需要对 $998244353$ 取模。

格式

输入格式

第一行包含一个整数 $n$，表示离散型随机变量的个数。

接下来 $n$ 行，每行第一个数是 $m_i$，表示该随机变量的取值种数，接下来有 $2 m_i$ 个整数，其中第 $2j$ 和第 $2j + 1$个整数为 $a_{i,j}$ 和 $c_{i,j}$，其中 $p_{i,j} = \frac{c_{i,j}}{100}$，$a_{i,j}$ 的含义见题目描述。

接下来一行包含一个整数 $Q$，表示询问的个数。

接下来有 $Q$ 行，每行包含 $3$ 个整数 $l,r,k$，具体含义见题目描述。

输出格式

对于每个查询，输出一行一个整数，表示第 $k$ 个随机变量的期望排名。

样例

样例输入 #1

2
2 1 40 3 60
1 2 100
2 
1 2 1
1 2 2

样例输出 #1

798595484
199648872

样例解释 #1

所有的取值可能如下（括号内为随机变量的编号）：

1. $\{ 1(1), 2(2)\}$，出现的概率为 $P(X_1 = 1 , X_2 = 2) = \frac{2}{5}\times 1= \frac{2}{5}$。
2. $\{2(2),3(1)\}$，出现的概率为 $P(X_1 = 3 , X_2 = 2) = \frac{3}{5}\times 1= \frac{3}{5}$。

故第 $1$ 个询问中 $X_1$ 的期望排名为 $1 \times \frac{2}{5} +2 \times \frac{3}{5} = \frac{8}{5} \equiv 798595484 \pmod {998244353}$。

第 $2$ 个询问中 $X_2$ 的期望排名为 $2 \times \frac{2}{5} +1 \times \frac{3}{5} = \frac{7}{5}\equiv 199648872 \pmod {998244353}$。

数据规模

对于 $20\%$ 的数据，$1 \leq n,Q \leq 5$，$1 \leq m \leq 2$。

对于 $60\%$ 的数据，$1 \leq n,Q \leq 5 \times 10^4$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq m_i \leq 10$，$1 \leq Q \leq 10^5$，$1 \leq l \leq k \leq r \leq n$，$1 \leq a_{i,j} \leq 10^9$，$\sum_{j = 1}^{m_i} c_{i,j}= 100$。