#2325. 「清华集训 2017」小 Y 和恐怖的奴隶主

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

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

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

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

虽然这个 Boss 有 1010010^{100} 点生命值,但它只带了一个随从——一个只有 mm 点生命值的「恐怖的奴隶主」。

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

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

输入格式

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

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

输出格式

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

可以证明,所求期望一定是一个有理数,设其为 pq{p \over q}gcd(p,q)=1\gcd(p,q) = 1),那么你输出的数 xx 要满足 pqx(mod998244353)p \equiv qx \pmod{998244353}

样例

样例 1

输入

3 2 6
1
2
3

输出

499122177
415935148
471393168

样例 1 解释

对于第一次询问,第一次攻击有 12\frac{1}{2} 的概率扣减 Boss 的生命值,有 12\frac{1}{2} 的概率扣减随从的生命值,所以答案为 12\frac{1}{2}12×499122177(mod998244353)1 \equiv 2 \times 499122177 \pmod{998244353}

对于第二次询问,如果第一次攻击扣减了 Boss 的生命值,那么有 12\frac{1}{2} 的概率第二次攻击仍扣减 Boss 的生命值,有 12\frac{1}{2} 的概率第二次攻击扣减随从的生命值;如果第一次攻击扣减了随从的生命值,那么现在又新召唤了一个随从(「恐怖的奴隶主」),于是有 13\frac{1}{3} 的概率第二次攻击扣减 Boss 的生命值,有 23\frac{2}{3} 的概率第二次攻击扣减随从的生命值。所以答案为 12×12×2+12×12×1+12×13×1+12×23×0=1112\frac{1}{2}\times\frac{1}{2}\times2+\frac{1}{2}\times\frac{1}{2}\times1+\frac{1}{2}\times\frac{1}{3}\times1+\frac{1}{2}\times\frac{2}{3}\times0 = \frac{11}{12}1112×415935148(mod998244353)11 \equiv 12 \times 415935148\pmod{998244353}

样例 2

见附加文件下的 ex_2.inex_2.ans

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

数据范围与提示

在所有测试点中,1T1000,1n1018,1m3,1k81 \leq T \leq 1000, 1 \leq n \leq {10}^{18}, 1 \leq m \leq 3, 1 \leq k \leq 8

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

测试点编号分值 T= T= n n\leq m= m= k= k=
13101011
2828
37 1018 {10}^{18} 3
4127
5302035
6105006
7102007
851000
9101008
105500