4337: 「清华集训 2017」小 Y 和恐怖的奴隶主
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
>"A fight? Count me in!" 要打架了，算我一个。
>"Everyone, get in here!" 所有人，都过来！
小 Y 是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。
虽然这个 Boss 有 $10^{100}$ 点生命值，但它只带了一个随从——一个只有 $m$ 点生命值的「恐怖的奴隶主」。
这个「恐怖的奴隶主」有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 $\leq 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 \over q}$（$\gcd(p,q) = 1$），那么你输出的数 $x$ 要满足 $p \equiv qx \pmod{998244353}$。
样例输入 复制
3 2 6
1
2
3
样例输出 复制
499122177
415935148
471393168
提示
数据范围：在所有测试点中，$1 \leq T \leq 1000, 1 \leq n \leq {10}^{18}, 1 \leq m \leq 3, 1 \leq k \leq 8$。 各个测试点的分值和数据范围如下： | 测试点编号 | 分值 | $ T= $ | $ n\leq $ | $ m= $ | $ k= $ | |-|-|-|-|-|-| | 1 | 3 | 10 | 10 | 1 | 1 | | 2 | 8 | 10 | 10 | 2 | 8 | | 3 | 7 | 10 | $ {10}^{18} $ | 2 | 3 | | 4 | 12 | 10 | $ {10}^{18} $ | 2 | 7 | | 5 | 30 | 20 | $ {10}^{18} $ | 3 | 5 | | 6 | 10 | 500 | $ {10}^{18} $ | 3 | 6 | | 7 | 10 | 200 | $ {10}^{18} $ | 3 | 7 | | 8 | 5 | 1000 | $ {10}^{18} $ | 3 | 7 | | 9 | 10 | 100 | $ {10}^{18} $ | 3 | 8 | | 10 | 5 | 500 | $ {10}^{18} $ | 3 | 8 |