#2006. 小 Y 和恐怖的奴隶主

    ID: 2006 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>CTT赛事:contest487来源:qoj.ac数据:公开样例动态规划

小 Y 和恐怖的奴隶主

小 Y 和恐怖的奴隶主

题目描述

标题: 小 Y 和恐怖的奴隶主 - Problem - QOJ.ac

#4610. 小 Y 和恐怖的奴隶主

Statistics

The problem was used in the following contests:

"A fight? Count me in!" 要打架了,算我一个。

"Everyone, get in here!" 所有人,都过来!


小Y是一个喜欢玩游戏的OIer。一天,她正在玩一款游戏,要打一个Boss。

虽然这个Boss有 10100 点生命值,但它只带了一个随从——一个只有 m 点生命值的“恐怖的奴隶主”。

这个“恐怖的奴隶主”有一个特殊的技能:每当它被扣减生命值但没有死亡(死亡即生命值 ≤0),且Boss的随从数量小于上限 k,便会召唤一个新的具有 m 点生命值的“恐怖的奴隶主”。

现在小Y可以进行 n 次攻击,每次攻击时,会从Boss以及Boss的所有随从中的等概率随机选择一个,并扣减 1 点生命值,她想知道进行 n 次攻击后扣减Boss的生命值点数的期望。为了避免精度误差,你的答案需要对 998244353 取模。

输入格式

从标准输入读入数据。

输入第一行包含三个正整数 T,m,k,T 表示询问组数,m,k 的含义见题目描述。

接下来 T 行,每行包含一个正整数 n,表示询问进行 n 次攻击后扣减Boss的生命值点数的期望。

输出格式

输出到标准输出。

输出共 T 行,对于每个询问输出一行一个非负整数,表示该询问的答案对 998244353 取模的结果。

可以证明,所求期望一定是一个有理数,设其为 p/q(gcd(p,q)=1),那么你输出的数 x 要满足 p≡qx(mod998244353)。

样例一

input

3 2 6
1
2
3

output

499122177
415935148
471393168

explanation

对于第一次询问,第一次攻击有 12 的概率扣减Boss的生命值,有 12 的概率扣减随从的生命值,所以答案为 12。1≡2∗499122177(mod998244353)。

对于第二次询问,如果第一次攻击扣减了Boss的生命值,那么有 12 的概率第二次攻击仍扣减Boss的生命值,有 12 的概率第二次攻击扣减随从的生命值;如果第一次攻击扣减了随从的生命值,那么现在又新召唤了一个随从(“恐怖的奴隶主”),于是有 13 的概率第二次攻击扣减Boss的生命值,有 23 的概率第二次攻击扣减随从的生命值。所以答案为 12∗12∗2+12∗12∗1+12∗13∗1+12∗23∗0=1112。11≡12∗415935148(mod998244353)。

样例二

见下发文件。

该组样例的数据范围(除询问组数 T 外)同第7、8个测试点。

提示

题目顺序可能与难度无关。

限制与约定

在所有测试点中,1≤T≤1000,1≤n≤1018,1≤m≤3,1≤k≤8。

各个测试点的分值和数据范围如下:

测试点编号分值T=n≤m=k=131010112828371018341275302035610500671020078510009101008105500

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2 6
1
2
3
499122177
415935148
471393168

样例 2

1 3 7
233333333333333333
456628220