Dotcpp  >  编程题库  >   蓝桥杯2019年第十届国赛真题-燃烧权杖
题目 2566:

蓝桥杯2019年第十届国赛真题-燃烧权杖

时间限制: 2s 内存限制: 192MB 提交: 29 解决: 1

题目描述

小 最近迷上了一款游戏。现在,在游戏中,小 有一个英雄,生命值为x;敌人也有一个英雄,生命值为 y。除此以外,还有 个士兵,生命值分别为a1a2、……、ak现在小 打算使用一个叫做“燃烧权杖”的技能。“燃烧权杖”会每次等概率随机选择一个活着的角色(英雄或士兵),扣减其 10 点生命值,然后如果该角色的生命值小于或等于 0,则该角色死亡,不会再被“燃烧权杖”选中。“燃烧权杖”会重复做上述操作,直至任意一名英雄死亡。小 想知道使用“燃烧权杖”后敌方英雄死亡(即,小 的英雄存活)的概率。为了避免精度误差,你只需要输出答案模一个质数 的结果,具体见输出格式。

输入格式

输入包含多组数据。
输入第一行包含一个正整数 T,表示数据组数。

接下来 组,每组数据第一行包含四个非负整数 xypk,分别表示小的英雄的生命值、敌方英雄的生命值,模数和士兵个数。

第二行包含 个正整数 a1a2、……、ak,分别表示每个士兵的生命值。

输出格式

对于每组数据,输出一行一个非负整数,表示答案模质数 p 的余数。
可以证明,答案一定为有理数。设答案为 a/b(a 和 b 为互质的正整数),你输出的数为 x,则你需要保证 a 与 bx 模 p 同余;也即,x = (a · b 1) mod p,其中 b 1 表示 b 模 p 的逆元, mod 为取模运算。

样例输入

6
1 10 101 0
100 1 101 0
50 30 4903 2
1 1
987 654 233 1
321
1000000000 999999999 233 3
1 2 3
1000000000 999999999 3 3
1 2 3

样例输出

51
37
1035
118
117
2

提示

【样例说明】
对于第一组数据,所求概率即为“燃烧权杖”第一次就扣减敌方英雄 10 点
生命值的概率,即 1/2。2 × 51 模 101 余 1。
对于第二组数据,答案为 1023/1024,1024 × 37 与 1023 模 101 同余。
对于第三组数据,答案为 99/128。
【评测用例规模与约定】

对于 10% 的评测用例,x, y, a1, · · · , ak ≤ 10。

对于 20% 的评测用例,x, y, a1, · · · , ak ≤ 100。
对于 50% 的评测用例,x, y, a1, · · · , ak ≤ 1000。
另有 10% 的评测用例,p = 3。
另有 20% 的评测用例,p ≤ 100。
对于全部评测用例,1 ≤ x, y, a1, · · · , ak ≤ 109,3 ≤ p ≤ 10000 且 p 为质数,0 ≤ k ≤ 10。

标签