#PQJ42x4267. QOJ 42_4267
QOJ 42_4267
标题: ydc的奖金 - Problem - QOJ.ac
#4267. ydc的奖金
The problem was used in the following contests:
有一天,ydc 在网上乱逛的时候,发现了一场比赛。这场比赛共 n 位选手参加,编号为 1,…,n,且 ydc 的编号为 n。
如果你能在这场比赛中获得第 i 名,那么你可以得到 pi 块软妹币作为奖金。有奖金可以拿,ydc 是自然不会放过这个便宜的,而且软妹币肯定是拿得越多越好。所以 ydc 进行了充分的研究,分别计算出了所有选手得分的概率分布(包括自己)。
这场考试的得分可以为任意 [0,1] 中的实数。对于第 i 个人,他得 x 分的概率,与一个多项式函数 fi(x) 成正比。当然,fi(x) 的定义域为 [0,1]。
如果第 i 个人的函数为 fi(x)=2,那么他获得任意分数的概率都是相等的;如果一个人的函数为 fi(x)=x+1,那么他获得 0 分的概率是获得 1 分的概率二分之一倍。
你需要计算的是 ydc 得到的奖金的期望。由于分数是实数所以两个人分数相等的概率为无穷小,所以无需考虑排名相等的情况。
ydc 当然早就算出来啦!但是他想考考你。
对于一个有理数一定能表示成 ab 的形式,其中 a≥0,b>0,且 a,b 互质。对于一个质数 p,如果 b 不是 p 的倍数那么我们可以定义 abmodp 为使 bx≡a(modp) 的最小非负整数 x。如果 b 是 p 的倍数那么 abmodp 未定义。
答案一定是个有理数,输出对 998244353(7×17×223+1,一个质数)取模后的结果(保证有定义)。
输入格式
第一行包含一个整数 n。
在第二行有 n 个整数,第 i 个数代表 pi。保证 p1≥p2≥⋯≥pn。
接下来 n 行,每行第一个数为正整数 ti,代表第 i 个人所对应的函数是一个定义域在 [0,1] 上的 ti−1 次的多项式函数,接下来 ti 个非负整数,第 j 个数代表该函数中 xj−1 项的系数。所有系数均小于 998244353。
显然所有人的函数在 [0,1] 的范围以内大于等于 0。保证所有函数在 [0,1] 的范围内与 x 轴所成的面积在模 998244353 意义下有定义且不等于 0。
输出格式
输出一行,包含一个整数,表示 ydc 获得的软妹币数量的期望对 998244353 取模后的结果。
样例一
input
2
2 1
1 1
2 0 1
output
665496237
限制与约定
测试点编号 n ∑i=1nti 特殊限制 1=2=5无2=103=10=404=605=806=1007=100=4008=6009=80010=100011=500=4000所有名次奖金相等12所有人的函数相同13除了第一名与最后一名外其它名次奖金相等1415=1500无16=200017=250018=300019=350020=4000
保证数据为均匀随机生成。
对于 1≤i≤n 有 0≤pi≤10000。
**时间限制:**6s
**空间限制:**256MB
来源
中国国家集训队互测2015 - By 刘剑成