linux怎么查看本机内存大小
287
2022-09-02
loj 2552「CTSC2018」假面
针针喜欢玩一款叫做 DotA (Defense of the Algorithm) 的游戏,在这个游戏中,针针会操纵自己的英雄与队友一起对抗另一支队伍。 针针在 DotA 中最喜欢使用的英雄叫做假面(Faceless),该英雄有 222 个技能:
锁定:对一名指定的敌方单位使用,以 ppp 的概率对该单位造成 111 点伤害(使其减少 111 点生命值)。结界:在一片区域施放结界,让该区域内的所有其他单位无法动弹。在游戏中,如果一个单位的生命值降至 000 或 000 以下,那么该单位就会死亡。针针操纵假面的水平一般,因此他决定勤加练习。现在有 nnn 个敌方单位(编号从 111 至 nnn),编号为 iii 的敌方单位有 hih_ihi 点生命值。
针针已经安排好了练习的计划,他会按顺序施放 QQQ 个技能:
对于锁定技能:针针会指定一个敌方单位 ididid ,并对它施放。由于决定概率系数 ppp 的因素很多,因此每次的 ppp 都不一定相同。 特别地,如果该敌方单位已经死亡,那么该技能不会造成任何效果。对于结界技能:针针会希望对 kkk 个指定的敌方单位施放,但由于针针并不擅长施放该技能,因此他只能命中恰好 111 个敌方单位。命中每个存活的敌方单位的概率是相等的(也就是说已经死亡的敌方单位不会有任何影响)。 特别地,如果这 kkk 个敌方单位均已死亡,那么该技能同样不会命中任何敌方单位。
现在,围观针针进行练习的绿绿想知道:
对于针针施放的每个结界技能,它命中各敌人的概率分别是多少。在针针的所有技能施放完毕后,所有敌方单位剩余生命值的期望分别是多少。
由于绿绿还要围观针针训练,所以请你帮他解决这两个问题。 为了防止精度误差,对于所有需要输出的数值,请输出其在模 998244353998244353998244353 意义下的值。 由于结界为假面的终极技能,因此针针施放该技能的次数不会太多。具体请见「子任务」。 输入格式
第 111 行为 111 个正整数 nnn ,表示敌方单位的数量。 第 222 行为 nnn 个正整数 m1,…,mn ,依次表示各敌方单位的初始生命值。 第 333 行为 111 个非负整数 QQQ ,表示针针施放技能的数量。 第 444 行至第 Q+3Q + 3Q+3 行,每行描述一个技能,第 i+3i + 3i+3 行描述第 iii 个技能。
每行的开头为一个整数 opopop ,表示该技能的种类。如果 op=0op = 0op=0 ,则表示锁定技能。并在此后跟随着 333 个正整数 id,u,vid , u , vid,u,v ,表示技能施放的目标为 ididid ,技能命中的概率为 p=uvp = \frac{u}{v}p=vu 。(保证 1≤id≤n,0
输出格式
输出包括 C+1C + 1C+1 行(其中 CCC 为结界技能的数量):
前 CCC 行依次对应每个结界技能,对于每行: 输出 kkk 个数,第 iii 个数表示结界命中敌方单位 idiid_iidi 的概率。第 C+1C + 1C+1 行输出 nnn 个数,第 iii 个数表示在所有技能施放完毕后,敌方单位 iii 剩余生命值的期望值。
对于每一行,如果行内包含多个数,则用单个空格将它们隔开。 对于所有数值,请输出它们对 998244353998244353998244353 取模的结果:即设答案化为最简分式后的形式为 ab\frac{a}{b}ba ,其中 aaa 和 bbb 的互质。输出整数 xxx 使得 bx≡amod998244353 且 0≤x<9982443530 \le x < 9982443530≤x<998244353 。(可以证明这样的整数 xxx 是唯一的) 样例 样例输入 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
针针按顺序施放如下技能:
对敌方单位 222 施放技能锁定:以 111 的概率对其造成 111 点伤害。 此时 222 号敌方单位必定剩余 111 点生命值。对敌方单位 222 施放技能结界:(由于 222 号敌方单位尚存活,)必定命中 222 号单位。对敌方单位 222 施放技能锁定:以 111 的概率对其造成 111 点伤害。对敌方单位 333 施放技能锁定:以1 的概率对其造成 111 点伤害。 此时三个敌方单位的生命值一定分别为 1,0,21, 0 ,21,0,2 ,敌方单位 222 一定死亡。对敌方单位 222 施放技能结界:(由于 222 号敌方单位已死亡,)必定不命中任何单位。对敌方单位 1,2,31, 2, 31,2,3 施放技能结界:命中敌方单位 1,31, 31,3 的概率是相等的,即各 12\frac{1}{2}21 。 最终,三个敌方单位的剩余生命值一定为 1,0,21 , 0 , 21,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
对于各结界技能的分析:
第 111 个结界(目标为敌方单位 1,21, 21,2 ): 222 号敌方单位存活的概率为 12\frac{1}{2}21 , 111 号敌方单位必定存活。 如果 222 号敌方单位存活,那么结界命中 1,21 , 21,2 的概率相等,均为 12\frac{1}{2}21 ;如果 222 号敌方单位死亡,那么结界必定命中 111 号敌方单位。 因此:命中 111 号敌方单位的概率为 12×1+12×12=34 \frac{1}{2} \times 1 + \frac{1}{2} \times \frac{1}{2} = \frac{3}{4}21×1+21×21=43 ;命中 222 号敌方单位的概率为 12×0+12×12=14 \frac{1}{2} \times 0 + \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}21×0+21×21=41 。第 222 个结界(目标为敌方单位 1,2,31, 2, 31,2,3 ): 三个敌方单位存活的概率分别为 1,12,131, \frac{1}{2} , \frac{1}{3}1,21,31 。 1,2,31 , 2 , 31,2,3 同时存活的概率为 16\frac{1}{6}61 ;只有 1,21, 21,2 存活的概率为 13\frac{1}{3}31 ;只有 1,31 , 31,3 存活的概率为 16\frac{1}{6}61 ;只有 111 存活的概率为 13\frac{1}{3}31 。 因此:命中 111 号敌方单位的概率为 16×13+(13+16)×12+13×1=2336\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}61×31+(31+61)×21+31×1=3623 ;命中 222 号敌方单位的概率为 16×13+13×12=29\frac{1}{6} \times \frac{1}{3} + \frac{1}{3} \times \frac{1}{2} = \frac{2}{9}61×31+31×21=92 ;命中 333 号敌方单位的概率为 16×13+16×12=536\frac{1}{6} \times \frac{1}{3} + \frac{1}{6} \times \frac{1}{2} = \frac{5}{36}61×31+61×21=365 。 最终,三个敌方单位的剩余生命值的期望值为 1,12,131 , \frac{1}{2} , \frac{1}{3}1,21,31 。
样例 3 & 样例 4
见附加文件。
这样一道题没写出来真是菜啊 还是数学不好造成的..
考虑这个血量的期望如何计算 我们只需要算出每个人为多少血的概率即可 最后计算答案的时候直接用概率*血即可 这个概率 简单背包dp即可解决
op=1的情况如何计算
考虑设dp1[i][j]表示k个人里前i个人有j个人存活的概率即可 考虑首先将所有人的这个状态都dp出来
那么我们关于这个人的答案就是枚举一下其他人除了这个人存活0,1,2,3…的概率 然后每次会攻击到我的概率就是 其他人分别存活0,1,2,3…的概率*我存活概率的和即可 注意处理特殊情况 如当前这个一定死亡或一定没死的情况 虽然因为逆元不会re但是算出来的答案其实是不对的 我们应该考虑直接去计算他们即可 如何求除了这个人的其他所有人 我就可以考虑dp的时候转移的时候我这个人是最后一个被转移的即可 把转移写出来 发现是可逆的 然后即可在c*n*n的时间内解决问题
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~