#PQJ233x4944. QOJ 233_4944
QOJ 233_4944
IOI 2018 中国国家队选拔赛暨精英赛 第一试假面(faceless) 假面(faceless) 【题目背景】 针针是绿绿的好朋友。 【题目描述】 针针喜欢玩一款叫做DotA(Defense of the Algorithm)的游戏,在这个游戏中, 针针会操纵自己的英雄与队友一起对抗另一支队伍。 针针在DotA 中最喜欢使用的英雄叫做假面(Faceless),该英雄有2 个技能: • 锁定:对一名指定的敌方单位使用,以p 的概率对该单位造成1 点伤害(使其 减少1 点生命值)。 • 结界:在一片区域施放结界,让该区域内的所有其他单位无法动弹。 在游戏中,如果一个单位的生命值降至0 或0 以下,那么该单位就会死亡。 针针操纵假面的水平一般,因此他决定勤加练习。 现在有n 个敌方单位(编号从1 至n),编号为i 的敌方单位有hi 点生命值。 针针已经安排好了练习的计划,他会按顺序施放Q 个技能: • 对于锁定技能:针针会指定一个敌方单位id,并对它施放。由于决定概率系数p 的因素很多,因此每次的p 都不一定相同。 – 特别地,如果该敌方单位已经死亡,那么该技能不会造成任何效果。 • 对于结界技能:针针会希望对k 个指定的敌方单位施放,但由于针针并不擅长施 放该技能,因此他只能命中.恰.好1 个敌方单位。命中每个.存.活.的敌方单位的概 率是相等的(也就是说已经死亡的敌方单位不会有任何影响)。 – 特别地,如果这k 个敌方单位均已死亡,那么该技能同样不会命中任何敌 方单位。 现在,围观针针进行练习的绿绿想知道:
- 对于针针施放的每个.结.界技能,它命中各敌人的概率分别是多少。
- 在针针的所有技能施放完毕后,所有敌方单位剩余生命值的期望分别是多少。 由于绿绿还要围观针针训练,所以请你帮他解决这两个问题。 为了防止精度误差,对于所有需要输出的数值,请输出其在模998, 244, 353 意义下 的值。 由于结界为假面的终极技能,因此针针施放该技能的次数不会太多。具体请见【子 任务】。 【输入格式】 从文件faceless.in 中读入数据。 第2 页 共11 页 IOI 2018 中国国家队选拔赛暨精英赛 第一试假面(faceless) • 第1 行为1 个正整数n,表示敌方单位的数量。 • 第2 行为n 个正整数m1, . . . , mn,依次表示各敌方单位的初始生命值。 • 第3 行为1 个非负整数Q,表示针针施放技能的数量。 • 第4 行至第Q + 3 行,每行描述一个技能,第i + 3 行描述第i 个技能。 – 每行的开头为一个整数op,表示该技能的种类。 – 如果op = 0,则表示锁定技能。并在此后跟随着3 个正整数id, u, v,表 示技能施放的目标为id,技能命中的概率为p = u v。(保证1 ≤id ≤n, 0 < u ≤v < 998, 244, 353) – 如果op = 1,则表示结界技能。并在此后跟随着1 个正整数k 表示技能施 放的目标数量,随后还有额外的k 个数id1, . . . , idk 描述技能施放的所有目 标。(保证所有1 ≤idi ≤n 互不相同) 对于每一行,如果行内包含多个数,则用单个空格将它们隔开。 【输出格式】 输出到文件faceless.out 中。 输出包C + 1 行(其中C 为结界技能的数量): • 前C 行依次对应每个结界技能,对于每行: – 输出k 个数,第i 个数表示结界命中敌方单位idi 的概率。 • 第C + 1 行输出n 个数,第i 个数表示在所有技能施放完毕后,敌方单位i 剩余 生命值的期望值。 对于每一行,如果行内包含多个数,则用单个空格将它们隔开。 对于所有数值,请输出它们对998, 244, 353 取模的结果:即设答案化为最简分 式后的形式为a b ,其中a 和b 的互质。输出整数x 使得bx ≡a mod 998244353 且 0 ≤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 第3 页 共11 页 IOI 2018 中国国家队选拔赛暨精英赛 第一试假面(faceless) 【样例1 输出】 1 0 499122177 0 499122177 1 0 2 【样例1 解释】 针针按顺序施放如下技能:
- 对敌方单位2 施放技能锁定:以1 的概率对其造成1 点伤害。 • 此时2 号敌方单位必定剩余1 点生命值。
- 对敌方单位2 施放技能结界:(由于2 号敌方单位尚存活,)必定命中2 号单位。
- 对敌方单位2 施放技能锁定:以1 的概率对其造成1 点伤害。
- 对敌方单位3 施放技能锁定:以1 的概率对其造成1 点伤害。 • 此时三个敌方单位的生命值一定分别为1, 0, 2,敌方单位2 一定死亡。
- 对敌方单位2 施放技能结界:(由于2 号敌方单位已死亡,)必定不命中任何单 位。
- 对敌方单位1, 2, 3 施放技能结界:命中敌方单位1, 3 的概率是相等的,即各位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 第4 页 共11 页 IOI 2018 中国国家队选拔赛暨精英赛 第一试假面(faceless) 【样例2 解释】 对于各结界技能的分析:
- 第1 个结界(目标为敌方单位1, 2): • 2 号敌方单位存活的概率为1 2,1 号敌方单位必定存活。 • 如果2 号敌方单位存活,那么结界命中1, 2 的概率相等,均为1 2;如果2 号敌方单位死亡,那么结界必定命中1 号敌方单位。 • 因此:命中1 号敌方单位的概率为1 2 × 1 + 1 2 × 1 2 = 3 4;命中2 号敌方单位 的概率为1 2 × 0 + 1 2 × 1 2 = 1 4。
- 第2 个结界(目标为敌方单位1, 2, 3): • 三个敌方单位存活的概率分别为1, 1 2, 1 3。 • 1, 2, 3 同时存活的概率为1 6;只有1, 2 存活的概率为1 3;只有1, 3 存活的 概率为1 6;只有1 存活的概率为1 3。 ( ) • 因此:命中1 号敌方单位的概率为1 6 × 1 1 3 + 1 × 1 2 + 1 3 × 1 = 23 36;命 3 + 6 中2 号敌方单位的概率为1 6 × 1 3 + 1 3 × 1 2 = 2 9;命中3 号敌方单位的概率为 1 6 × 1 3 + 1 6 × 1 36。 5 2 = 最终,三个敌方单位的剩余生命值的期望值为1, 1 3。 2, 1 【样例3】 见选手目录下的faceless/faceless3.in 与faceless/faceless3.ans。 【样例4】 见选手目录下的faceless/faceless4.in 与faceless/faceless4.ans。 【子任务】 我们记C 为结界技能的数量。 第5 页 共11 页 IOI 2018 中国国家队选拔赛暨精英赛 第一试假面(faceless) 测试点编号 其他限制 u, v n = Q = C = 无 5 21 6 1 所有p 均相等 199, 992 500 2 23 6 3 所有mi = 1 u < v 199, 994 4 60 500 199, 995 5 199, 996 0 6 199, 997 500 7 u = v 无 199, 998 8 199, 999 u < v 200 1000 9 200, 000 10 .为.了.优.化.你.的.阅.读.体.验,.我.们.把.测.试.点.编.号.放.在.了.表.格.的.中.间,.请.注.意.这.一.点。 对于所有测试点,保证n ≤200,Q ≤200, 000,C ≤1000,mi ≤100。 【提示】
- 第3 个样例满足测试点1 的数据规模限制。
- 第4 个样例满足限制‘‘所有p 均相等’’。
- Q 的个位可以帮助你快速确定测试点的编号。
- 测试点顺序可能与难度无关。 第6 页 共11 页