UOJ Logo Universal Online Judge

UOJ

#102. 【集训队互测2015】ydc的奖金

统计

有一天,ydc 在网上乱逛的时候,发现了一场比赛。这场比赛共 $n$ 位选手参加,编号为 $1, \dots, n$,且 ydc 的编号为 $n$。

如果你能在这场比赛中获得第 $i$ 名,那么你可以得到 $p_i$ 块软妹币作为奖金。有奖金可以拿,ydc 是自然不会放过这个便宜的,而且软妹币肯定是拿得越多越好。所以 ydc 进行了充分的研究,分别计算出了所有选手得分的概率分布(包括自己)。

这场考试的得分可以为任意 $[0, 1]$ 中的实数。对于第 $i$ 个人,他得 $x$ 分的概率,与一个多项式函数 $f_i(x)$ 成正比。当然,$f_i(x)$ 的定义域为 $[0, 1]$。

如果第 $i$ 个人的函数为 $f_i(x)=2$,那么他获得任意分数的概率都是相等的;如果一个人的函数为 $f_i(x)=x+1$,那么他获得 $0$ 分的概率是获得 $1$ 分的概率二分之一倍。

你需要计算的是 ydc 得到的奖金的期望。由于分数是实数所以两个人分数相等的概率为无穷小,所以无需考虑排名相等的情况。

ydc 当然早就算出来啦!但是他想考考你。

对于一个有理数一定能表示成 $\frac{a}{b}$ 的形式,其中 $a \geq 0, b > 0$,且 $a, b$ 互质。对于一个质数 $p$,如果 $b$ 不是 $p$ 的倍数那么我们可以定义 $\frac{a}{b} \bmod p$ 为使 $bx \equiv a \pmod{p}$ 的最小非负整数 $x$。如果 $b$ 是 $p$ 的倍数那么 $\frac{a}{b} \bmod p$ 未定义。

答案一定是个有理数,输出对 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)取模后的结果(保证有定义)。

输入格式

第一行包含一个整数 $n$。

在第二行有 $n$ 个整数,第 $i$ 个数代表 $p_i$。保证 $p_1 \geq p_2 \geq \dots \geq p_n$。

接下来 $n$ 行,每行第一个数为正整数 $t_i$,代表第 $i$ 个人所对应的函数是一个定义域在 $[0, 1]$ 上的 $t_i - 1$ 次的多项式函数,接下来 $t_i$ 个非负整数,第 $j$ 个数代表该函数中 $x^{j-1}$ 项的系数。所有系数均小于 $998244353$。

显然所有人的函数在 $[0,1]$ 的范围以内大于等于 $0$。保证所有函数在 $[0,1]$ 的范围内与 $x$ 轴所成的面积在模 $998244353$ 意义下有定义且不等于 $0$。

输出格式

输出一行,包含一个整数,表示 ydc 获得的软妹币数量的期望对 $998244353$ 取模后的结果。

样例一

input

2
2 1
1 1
2 0 1

output

665496237

限制与约定

测试点编号 $n$ $\sum_{i = 1}^{n} t_i$ 特殊限制
1$=2$$= 5$
2$=10$
3$=10$$= 40$
4$= 60$
5$= 80$
6$= 100$
7$=100$$= 400$
8$= 600$
9$= 800$
10$= 1000$
11$=500$$= 4000$所有名次奖金相等
12所有人的函数相同
13除了第一名与最后一名外其它名次奖金相等
14
15$= 1500$
16$= 2000$
17$= 2500$
18$= 3000$
19$= 3500$
20$= 4000$

保证数据为均匀随机生成。

对于 $1 \leq i \leq n$ 有 $0 \leq p_i \leq 10000$。

时间限制:$6\texttt{s}$

空间限制:$256\texttt{MB}$

来源

中国国家集训队互测2015 - By 刘剑成

下载

样例数据下载