← 返回题目列表

Codeforces · 1286/D

D. 线性奇兰碰撞器

中文机器翻译题面 查看原题

在 Chillland 建造了无限长线 Chillland Collider (LCC)。有 $$$n$$$ 坐标为 $$$x_i$$$ 的管道连接到 LCC。当实验在时间 0 开始时,第 $$$i$$$ 个质子以 $$$v_i$$$ 速度从第 $$$i$$$ 个管道中飞行。它以 $$$p_i$$$ 的概率向右飞,以 $$$(1 - p_i)$$$ 的概率向左飞。实验的持续时间被确定为任意两个质子第一次碰撞的时间。如果没有发生碰撞,则实验的持续时间被认为为零。

求实验持续时间的预期值。

第一个示例的插图

输入

输入的第一行包含一个整数 $$$n$$$ — 管道的数量 ($$$1 \le n \le 10^5$$$)。以下$$$n$$$行中的每一行都包含三个整数$$$x_i$$$、$$$v_i$$$、$$$p_i$$$——第$$$i$$$管道的坐标、第$$$i$$$个质子的速度以及第$$$i$$$个质子向右飞行的概率(以百分点为单位)($$$-10^9 \le x_i \le 10^9, 1 \le v \le 10^6, 0 \le p_i \le 100$$$)。保证所有 $$$x_i$$$ 都是不同的并且按升序排序。

输出

可以证明答案总是可以表示为分数 $$$P/Q$$$,其中 $$$P$$$ 是整数,$$$Q$$$ 是不能被 $$$998\,244\,353$$$ 整除的自然数。在这种情况下,打印 $$$P \cdot Q^{-1}$$$ 模 $$$998\,244\,353$$$。

示例

输入 #1

2
1 1 100
3 1 0

输出 #1

1

输入 #2

3
7 10 0
9 4 86
14 5 100

输出 #2

0

输入 #3

4
6 4 50
11 25 50
13 16 50
15 8 50

输出 #3

150902884