← 返回题目列表

Codeforces · 1571/H

H. 激光束

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

Ira 正在开发一款电脑游戏。该游戏具有随机生成和关卡难度的特点。为了实现随机难度,每个级别中的一些敌人都会被更强大的敌人随机替换。

为了描述游戏中关卡的外观,我们引入一个坐标系,$$$Ox$$$ 轴从左到右,$$$Oy$$$ 轴从下到上。级别是一个矩形,其对角点为 $$$(0, 0)$$$ 和 $$$(a, b)$$$。每个敌人的位置都是这个矩形中的一个点。

目前,Ira 在游戏中实现了一种类型的敌人,有两个不同的版本——基本版和升级版。两个版本的敌人 Ira 都向多个方向发射激光射线:

- 基本敌人向四个方向发射四束激光:向右(与矢量 $$$(1, 0)$$$ 相同的方向)、向左(与矢量 $$$(-1, 0)$$$ 相同的方向)、向上(与矢量 $$$(0, 1)$$$ 相同的方向)和向下(与矢量 $$$(0, -1)$$$);
- 升级后的敌人向八个方向发射八束激光:四个方向为基本敌人列出,四个方向对应于向量 $$$(1, 1)$$$、$$$(1, -1)$$$、$$$(-1, 1)$$$、$$$(-1, -1)$$$。

激光射线穿过敌人并仅被关卡边界(表示关卡的矩形的边)阻挡。敌人不受激光影响。

Ira 正在处理的关卡有 $$$n$$$ 个敌人。第 $$$i$$$ 个敌人位于 $$$(x_i, y_i)$$$ 点,其升级概率为 $$$p_i$$$(要么以 $$$p_i$$$ 概率升级,要么以 $$$1-p_i$$$ 概率升级)。所有这些事件都是独立的。

Ira 想估计预期的难度。她认为评估关卡难度的一个好方法是计算关卡被激光束划分的部分数量。所以,她想计算一下这些零件的预计数量。

帮她做等级评估吧!

输入

第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le n \le 100$$$; $$$2 \le a, b \le 100$$$) — 关卡中敌人的数量和关卡的维度。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$p'_i$$$ ($$$1 \le x_i \le a - 1$$$; $$$1 \le y_i \le b - 1$$$; $$$1 \le p'_i \le 999999$$$),意味着第 $$$i$$$ 个敌人位于 $$$(x_i, y_i)$$$,升级的概率为 $$$\frac{p'_i}{10^6}$$$。

没有两个敌人位于同一点。

输出

打印一个整数 - 激光划分能级的预期部分数量,以 $$$998244353$$$ 为模(即,让预期部分数量为 $$$\frac{x}{y}$$$ 作为不可约分数;您必须打印 $$$x \cdot y^{-1} \bmod 998244353$$$,其中$$$y^{-1}$$$ 是一个数字,使得 $$$y \cdot y^{-1} \bmod 998244353 = 1$$$)。

示例

输入 #1

1 2 2
1 1 500000

输出 #1

6

输入 #2

2 3 2
1 1 500000
2 1 500000

输出 #2

499122187

注意

第一个例子的解释:

概率为 $$$\frac{1}{2}$$$,唯一的敌人不会升级,等级如下($$$4$$$ 部分):

以 $$$\frac{1}{2}$$$ 的概率,唯一的敌人升级,等级如下($$$8$$$ 部分):

因此,预期的零件数量为 $$$4 \cdot \frac{1}{2} + 8 \cdot \frac{1}{2} = 6$$$。