#2552. 「CTSC2018」假面

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

针针是绿绿的好朋友。

针针喜欢玩一款叫做 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

1
0
499122177 0 499122177
1 0 2

样例解释 1

针针按顺序施放如下技能:

  1. 对敌方单位 2 施放技能锁定:以 1 的概率对其造成 1 点伤害。
  • 此时 2 号敌方单位必定剩余 1 点生命值。
  1. 对敌方单位 2 施放技能结界:(由于 2 号敌方单位尚存活,)必定命中 2 号单位。
  2. 对敌方单位 2 施放技能锁定:以 1 的概率对其造成 1 点伤害。
  3. 对敌方单位 3 施放技能锁定:以1 的概率对其造成 1 点伤害。
  • 此时三个敌方单位的生命值一定分别为 1, 0 ,2 ,敌方单位 2 一定死亡。
  1. 对敌方单位 2 施放技能结界:(由于 2 号敌方单位已死亡,)必定不命中任何单位。
  2. 对敌方单位 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

样例输出 2

249561089 748683265
804141285 887328314 305019108
1 499122177 332748118

样例解释 2

对于各结界技能的分析:

  1. 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}
  1. 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}

样例 3 & 样例 4

见附加文件。

数据范围与提示

数据范围

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

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

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

提示

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