← 返回题目列表

AtCoder · npcapc_2024_h

H. 音乐游戏

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

配点 : 100 点

問題文

1 减去 N 有 N 开关。所有开关现已关闭。
从现在开始,按任意顺序切换。 1 你一一按下,但每个开关都坏了。具体来说,开关 i 按 它需要 T_i 秒,当你按下它时,它的行为如下:

  • 確率 \frac{A_i}{B_i} 将其打开。 所有
  • 確率 1 - \frac{A_i}{B_i} 在 N 开关均关闭。

每次按下开关时,都会独立选择是否打开开关。此外,按下一个开关时,无法按下另一个开关。

您的目标是尽快打开所有功能。正确按下所有开关后打开所有开关所需的预计秒数 查找 \bmod\ 998244353 。

期待値 \bmod\ 998244353 的定义

可以证明期望的期望值始终是有理数。另外,在这个问题的约束下,我们可以将该值转换为不可约分数 当表示为 \frac{P}{Q} 时, 也可以证明Q \neq 0 \pmod{998244353} 。因此,R \times Q = P \pmod{998244353},0 \le R < 998244353 的整数 选择 R 是唯一确定的。这个 请回答 R 。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le T_i \le 10^6
  • 1 \le A_i \le B_i \le 10^6

入力

输入是按以下格式从标准输入给出的。

N
T_1 A_1 B_1
T_2 A_2 B_2
⋮
T_N A_N B_N

出力

请打印答案。 到达


入力例 1

2
3 3 5
2 4 7

出力例 1

831870305

操作顺序的示例如下。 (此操作顺序不一定能达到最佳效果。)

  • 开关 按住 1 该值应乘以 3 秒。开关 1 已打开。
  • 开关 按住 2 该值应乘以 2 按住几秒钟。所有开关均关闭。
  • 开关 按住 2 该值应乘以 2 秒。开关 2 已打开。
  • 开关 按住 1 该值应乘以 3 秒。开关 1 已打开。

在这一系列操作中,所花费的时间是 10 秒,并且操作以这种方式进行的概率是 \frac{3}{5} \times \frac{3}{7} \times \frac{4}{7} \times \frac{3}{5} = \frac{108}{1225} 。

另外,在这种情况下,正确按下时打开所有开关所需的秒数的预期值为 \frac{65}{6} 秒。


入力例 2

5
2 5 9
6 4 7
1 9 14
17 8 13
10 4 11

出力例 2

914017655

入力例 3

8
6 2 8
3 1 8
5 30 71
7 9 58
6 4 7
6 9 25
2 8 67
6 6 55

出力例 3

923892723