"A fight? Count me in!" 要打架了,算我一个。
"Everyone, get in here!" 所有人,都过来!
小 Y 是一个喜欢玩游戏的 OIer。一天,她正在玩一款游戏,要打一个 Boss。
虽然这个 Boss 有 点生命值,但它只带了一个随从——一个只有 点生命值的「恐怖的奴隶主」。
这个「恐怖的奴隶主」有一个特殊的技能:每当它被扣减生命值但没有死亡(死亡即生命值 ),且 Boss 的随从数量小于上限 ,便会召唤一个新的具有 点生命值的「恐怖的奴隶主」。
现在小 Y 可以进行 次攻击,每次攻击时,会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个,并扣减 点生命值,她想知道进行 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差,你的答案需要对 取模。
输入第一行包含三个正整数 , 表示询问组数, 的含义见题目描述。
接下来 行,每行包含一个正整数 ,表示询问进行 次攻击后扣减 Boss 的生命值点数的期望。
输出共 行,对于每个询问输出一行一个非负整数,表示该询问的答案对 取模的结果。
可以证明,所求期望一定是一个有理数,设其为 (),那么你输出的数 要满足 。
3 2 6
1
2
3
499122177
415935148
471393168
对于第一次询问,第一次攻击有 的概率扣减 Boss 的生命值,有 的概率扣减随从的生命值,所以答案为 。。
对于第二次询问,如果第一次攻击扣减了 Boss 的生命值,那么有 的概率第二次攻击仍扣减 Boss 的生命值,有 的概率第二次攻击扣减随从的生命值;如果第一次攻击扣减了随从的生命值,那么现在又新召唤了一个随从(「恐怖的奴隶主」),于是有 的概率第二次攻击扣减 Boss 的生命值,有 的概率第二次攻击扣减随从的生命值。所以答案为 。。
见附加文件下的 ex_2.in 与 ex_2.ans。
该组样例的数据范围(除询问组数 外)同第 7、8 个测试点。
在所有测试点中,。
各个测试点的分值和数据范围如下:
测试点编号 | 分值 | ||||
---|---|---|---|---|---|
1 | 3 | 10 | 10 | 1 | |
2 | 8 | 2 | 8 | ||
3 | 7 | 3 | |||
4 | 12 | 7 | |||
5 | 30 | 20 | 3 | 5 | |
6 | 10 | 500 | 6 | ||
7 | 200 | 7 | |||
8 | 5 | 1000 | |||
9 | 10 | 100 | 8 | ||
10 | 5 | 500 |