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