#P3100. 「CTSC2018」假面
「CTSC2018」假面
Description
针针是绿绿的好朋友。
针针喜欢玩一款叫做 DotA (Defense of the Algorithm) 的游戏,在这个游戏中,针针会操纵自己的英雄与队友一起对抗另一支队伍。
针针在 DotA 中最喜欢使用的英雄叫做假面(Faceless),该英雄有 个技能:
-
锁定:对一名指定的敌方单位使用,以 的概率对该单位造成 点伤害(使其减少 点生命值)。
-
结界:在一片区域施放结界,让该区域内的所有其他单位无法动弹。
在游戏中,如果一个单位的生命值降至 或 以下,那么该单位就会死亡。
针针操纵假面的水平一般,因此他决定勤加练习。现在有 个敌方单位(编号从 至 ),编号为 的敌方单位有 点生命值。
针针已经安排好了练习的计划,他会按顺序施放 个技能:
-
对于锁定技能:针针会指定一个敌方单位 ,并对它施放。由于决定概率系数 的因素很多,因此每次的 都不一定相同。
-
特别地,如果该敌方单位已经死亡,那么该技能不会造成任何效果。
-
对于结界技能:针针会希望对 个指定的敌方单位施放,但由于针针并不擅长施放该技能,因此他只能命中恰好 个敌方单位。命中每个存活的敌方单位的概率是相等的(也就是说已经死亡的敌方单位不会有任何影响)。
-
特别地,如果这 个敌方单位均已死亡,那么该技能同样不会命中任何敌方单位。
现在,围观针针进行练习的绿绿想知道:
-
对于针针施放的每个结界技能,它命中各敌人的概率分别是多少。
-
在针针的所有技能施放完毕后,所有敌方单位剩余生命值的期望分别是多少。
由于绿绿还要围观针针训练,所以请你帮他解决这两个问题。
为了防止精度误差,对于所有需要输出的数值,请输出其在模 意义下的值。
由于结界为假面的终极技能,因此针针施放该技能的次数不会太多。具体请见「子任务」。
Input Format
第 行为 个正整数 ,表示敌方单位的数量。
第 行为 个正整数 ,依次表示各敌方单位的初始生命值。
第 行为 个非负整数 ,表示针针施放技能的数量。
第 行至第 行,每行描述一个技能,第 行描述第 个技能。
-
每行的开头为一个整数 ,表示该技能的种类。
-
如果 ,则表示锁定技能。并在此后跟随着 个正整数 ,表示技能施放的目标为 ,技能命中的概率为 。(保证 )
-
如果 ,则表示结界技能。并在此后跟随着 个正整数 表示技能施放的目标数量,随后还有额外的 个数 描述技能施放的所有目
标。(保证所有 互不相同)
对于每一行,如果行内包含多个数,则用单个空格将它们隔开。
Output Format
输出包括 行(其中 为结界技能的数量):
-
前 行依次对应每个结界技能,对于每行:
-
输出 个数,第 个数表示结界命中敌方单位 的概率。
-
第 行输出 个数,第 个数表示在所有技能施放完毕后,敌方单位 剩余生命值的期望值。
对于每一行,如果行内包含多个数,则用单个空格将它们隔开。
对于所有数值,请输出它们对 取模的结果:即设答案化为最简分式后的形式为 ,其中 和 的互质。输出整数 使得 且 。(可以证明这样的整数 是唯一的)
Sample
样例输入 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
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
对于各结界技能的分析:
- 第 个结界(目标为敌方单位 ):
- 号敌方单位存活的概率为 , 号敌方单位必定存活。
- 如果 号敌方单位存活,那么结界命中 的概率相等,均为 ;如果 号敌方单位死亡,那么结界必定命中 号敌方单位。
- 因此:命中 号敌方单位的概率为 $ \frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{2} = \frac{3}{4}$ ;命中 号敌方单位的概率为 $ \frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ 。
- 第 个结界(目标为敌方单位 ):
- 三个敌方单位存活的概率分别为 。
- 同时存活的概率为 ;只有 存活的概率为 ;只有 存活的概率为 ;只有 存活的概率为 。
- 因此:命中 号敌方单位的概率为 $\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}$ ;命中 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{9}$ ;命中 号敌方单位的概率为 $\frac{1}{6} \times \frac{1}{3} + \frac{1}{6} \times \frac{1}{2} = \frac{5}{36}$ 。 最终,三个敌方单位的剩余生命值的期望值为 。
样例 3 & 样例 4
见附加文件。
Hint
数据范围
我们记 为结界技能的数量。
| | | | 测试点编号 | | 其他限制 |
| :---: | :------: | :----: | :---: | :---: | :---------: |
| | | | 1 | | 无 |
| | | | 2 | | 所有 均相等 |
| | | | 3 | | 所有 |
| | | | 4 | | 无 |
| | | | 5 | | 无 |
| | | | 6 | | 无 |
| | | | 7 | | 无 |
| | | | 8 | | 无 |
| | | | 9 | | 无 |
| | | | 10 | | 无 |
为了优化你的阅读体验,我们把测试点编号放在了表格的中间,请注意这一点。
对于所有测试点,保证 。
提示
-
第 个样例满足测试点 的数据规模限制。
-
第 个样例满足限制‘‘所有 均相等’’。 -
的个位可以帮助你快速确定测试点的编号。
-
测试点顺序可能与难度无关。