#2552. 「CTSC2018」假面

题目描述

针针是绿绿的好朋友。 针针喜欢玩一款叫做 DotA (Defense of the Algorithm) 的游戏，在这个游戏中，针针会操纵自己的英雄与队友一起对抗另一支队伍。 针针在 DotA 中最喜欢使用的英雄叫做假面（Faceless），该英雄有 $2$ 个技能：

• 锁定：对一名指定的敌方单位使用，以 $p$ 的概率对该单位造成 $1$ 点伤害（使其减少 $1$ 点生命值）。
• 结界：在一片区域施放结界，让该区域内的所有其他单位无法动弹。

在游戏中，如果一个单位的生命值降至 $0$ 或 $0$ 以下，那么该单位就会死亡。 针针操纵假面的水平一般，因此他决定勤加练习。现在有 $n$ 个敌方单位（编号从 $1$ 至 $n$），编号为 $i$ 的敌方单位有 $h_i$ 点生命值。 针针已经安排好了练习的计划，他会按顺序施放 $Q$ 个技能：

• 对于锁定技能：针针会指定一个敌方单位 $id$，并对它施放。由于决定概率系数 $p$ 的因素很多，因此每次的 $p$ 都不一定相同。
  • 特别地，如果该敌方单位已经死亡，那么该技能不会造成任何效果。
• 对于结界技能：针针会希望对 $k$ 个指定的敌方单位施放，但由于针针并不擅长施放该技能，因此他只能命中恰好 $1$ 个敌方单位。命中每个存活的敌方单位的概率是相等的（也就是说已经死亡的敌方单位不会有任何影响）。
  • 特别地，如果这 $k$ 个敌方单位均已死亡，那么该技能同样不会命中任何敌方单位。

现在，围观针针进行练习的绿绿想知道：

1. 对于针针施放的每个结界技能，它命中各敌人的概率分别是多少。
2. 在针针的所有技能施放完毕后，所有敌方单位剩余生命值的期望分别是多少。

由于绿绿还要围观针针训练，所以请你帮他解决这两个问题。 为了防止精度误差，对于所有需要输出的数值，请输出其在模 $998244353$ 意义下的值。 由于结界为假面的终极技能，因此针针施放该技能的次数不会太多。具体请见「子任务」。

输入格式

第 $1$ 行为 $1$ 个正整数 $n$，表示敌方单位的数量。 第 $2$ 行为 $n$ 个正整数 $m_1, \dots ,m_n$，依次表示各敌方单位的初始生命值。 第 $3$ 行为 $1$ 个非负整数 $Q$，表示针针施放技能的数量。 第 $4$ 行至第 $Q + 3$ 行，每行描述一个技能，第 $i + 3$ 行描述第 $i$ 个技能。 每行的开头为一个整数 $op$，表示该技能的种类。

• 如果 $op = 0$，则表示锁定技能。并在此后跟随着 $3$ 个正整数 $id, u, v$，表示技能施放的目标为 $id$，技能命中的概率为 $p = \frac{u}{v}$。（保证 $1\le id \le n , 0 < u \le v < 998244353$）
• 如果 $op = 1$，则表示结界技能。并在此后跟随着 $1$ 个正整数 $k$ 表示技能施放的目标数量，随后还有额外的 $k$ 个数 $id_1, \dots , id_k$ 描述技能施放的所有目标。（保证所有 $1 \le id_i \le n$ 互不相同）

对于每一行，如果行内包含多个数，则用单个空格将它们隔开。

输出格式

输出包括 $C + 1$ 行（其中 $C$ 为结界技能的数量）： 前 $C$ 行依次对应每个结界技能，对于每行： 输出 $k$ 个数，第 $i$ 个数表示结界命中敌方单位 $id_i$ 的概率。 第 $C + 1$ 行输出 $n$ 个数，第 $i$ 个数表示在所有技能施放完毕后，敌方单位 $i$ 剩余生命值的期望值。 对于每一行，如果行内包含多个数，则用单个空格将它们隔开。 对于所有数值，请输出它们对 $998244353$ 取模的结果：即设答案化为最简分式后的形式为 $\frac{a}{b}$，其中 $a$ 和 $b$ 的互质。输出整数 $x$ 使得 $bx \equiv a \bmod 998244353$ 且 $0 \le x < 998244353$。（可以证明这样的整数 $x$ 是唯一的）

样例

样例 1

输入

3
1 2 3
6
0 2 1 1
1 1 2
0 2 1 1
0 3 1 1
1 1 2
1 3 1 2 3

输出

1
0
499122177 0 499122177
1 0 2

样例解释 针针按顺序施放如下技能：

1. 对敌方单位 $2$ 施放技能锁定：以 $1$ 的概率对其造成 $1$ 点伤害。此时 $2$ 号敌方单位必定剩余 $1$ 点生命值。
2. 对敌方单位 $2$ 施放技能结界：（由于 $2$ 号敌方单位尚存活，）必定命中 $2$ 号单位。
3. 对敌方单位 $2$ 施放技能锁定：以 $1$ 的概率对其造成 $1$ 点伤害。
4. 对敌方单位 $3$ 施放技能锁定：以 $1$ 的概率对其造成 $1$ 点伤害。 此时三个敌方单位的生命值一定分别为 $1, 0 ,2$，敌方单位 $2$ 一定死亡。
5. 对敌方单位 $2$ 施放技能结界：（由于 $2$ 号敌方单位已死亡，）必定不命中任何单位。
6. 对敌方单位 $1, 2, 3$ 施放技能结界：命中敌方单位 $1, 3$ 的概率是相等的，即各 $\frac{1}{2}$。

最终，三个敌方单位的剩余生命值一定为 $1 , 0 , 2$。

样例 2

输入

3
1 1 1
4
0 2 1 2
1 2 1 2
0 3 2 3
1 3 1 2 3

输出

249561089 748683265
804141285 887328314 305019108
1 499122177 332748118

样例解释 对于各结界技能的分析：

第 $1$ 个结界（目标为敌方单位 $1, 2$）： $2$ 号敌方单位存活的概率为 $\frac{1}{2}$，$1$ 号敌方单位必定存活。 如果 $2$ 号敌方单位存活，那么结界命中 $1 , 2$ 的概率相等，均为 $\frac{1}{2}$；如果 $2$ 号敌方单位死亡，那么结界必定命中 $1$ 号敌方单位。 因此： 命中 $1$ 号敌方单位的概率为 $\frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{2} = \frac{3}{4}$； 命中 $2$ 号敌方单位的概率为 $\frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$。

第 $2$ 个结界（目标为敌方单位 $1, 2, 3$）： 三个敌方单位存活的概率分别为 $1, \frac{1}{2} , \frac{1}{3}$。 $1 , 2 , 3$ 同时存活的概率为 $\frac{1}{6}$； 只有 $1, 2$ 存活的概率为 $\frac{1}{3}$； 只有 $1 , 3$ 存活的概率为 $\frac{1}{6}$； 只有 $1$ 存活的概率为 $\frac{1}{3}$。 因此： 命中 $1$ 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + (\frac{1}{3}+\frac{1}{6}) \times \frac{1}{2}+ \frac{1}{3} \times 1 = \frac{23}{36}$； 命中 $2$ 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{9}$； 命中 $3$ 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + \frac{1}{6} \times \frac{1}{2} = \frac{5}{36}$。

最终，三个敌方单位的剩余生命值的期望值为 $1 , \frac{1}{2} , \frac{1}{3}$。

数据范围与提示

我们记 $C$ 为结界技能的数量。

$n$	$Q$	$C$	测试点编号	$u,v$	其他限制
$5$	$2$	$1$		$u < v$	无
$60$	$199992$	$500$	$2$	$u=v$	所有 $p$ 均相等
$2$	$3$	$1$	$3$	$u<v$	所有 $m_i =1$
$199994$	$500$	$4$		$u=v$	无
$199995$	$5$			$u<v$
$199996$	$0$		$6$
$500$	$199997$	$500$	$7$	$u=v$
$1000$	$199998$	$1000$	$8$	$u<v$
$200$	$199999$		$9$
	$200000$		$10$

注意： 为了优化你的阅读体验，我们把测试点编号放在了表格的中间。 对于所有测试点，保证 $n \le 200 , Q \le 200000 , C \le 1000 , m_i \le 100$。

提示

• 第 $3$ 个样例满足测试点 $1$ 的数据规模限制。
• 第 $4$ 个样例满足限制“所有 $p$ 均相等”。事实上这个限制并不满足，这是原题面的错误，在此保留原文。
• $Q$ 的个位可以帮助你快速确定测试点的编号。
• 测试点顺序可能与难度无关。