当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7237:Leapfrogger

题目描述
<strong>Notice: If you have played Battlegrounds in Hearthstone and know the mechanism of leapfrogger and Baron Rivendare, you can start at the fourth paragraph, but note that the context of the problem is simplified and may not be the same as what is in-game.</strong>

In the famous card-collecting game <i>Hearthstone</i>, there is a mode named <i>Battlegrounds</i>, based on the auto battler genre, and allows eight players to compete in each match by recruiting minions over several rounds. In Battlegrounds, there is a special minion named <strong>leapfrogger</strong>, which is a second-tier beast with stats 3/3, and has the deathrattle of <i>"Give a friendly beast +1/+1 and this deathrattle''</i>, which means that when this minion dies, it will randomly give a friendly beast (if there exists any) the effect of +1/+1 in stats and this same effect (i.e., when that friendly beast dies, it will randomly give a friendly beast +1/+1 and the same effect, et cetera).



An interesting thing about leapfrogger is that its deathrattle is <strong>stackable</strong>, i.e., a minion is allowed to have multiple, say $k$, deathrattles of the leapfrogger at the same time, then when this minion dies, it will randomly give a friendly beast(if there exists any) the effect of +1/+1 in stats and this same effect, <strong>repeated $k$ times.</strong> Note that in each of the $k$ times, the friendly beast is chosen <strong>independently</strong> at random. What makes things more interesting is a minion in Battlegrounds called <strong>Baron Rivendare</strong> that can double the effect of deathrattles when it is on the board. When Baron Rivendare is on the board, and a leapfrogger dies, its deathrattle is triggered and given to a random friendly beast, <strong>twice</strong>. If both deathrattles are given to the same friendly beast and that beast dies, still with Baron Rivendare on the board, each of the two deathrattles of leapfrogger on the beast is triggered twice, so that a total of four copies of the deathrattle of leapfrogger are triggered and given to a random friendly beast... The speed the deathrattle of leapfrogger spread when Baron Rivendare is on the board is quite insane and is what makes the "leapfrogger build" a possible and quite powerful strategy in Battlegrounds.

That is quite a lot for the background. Let's then make some simplifications. We assume the deathrattle of leapfrogger can be given to <strong>any minion</strong> instead of <strong>only to beasts</strong>. We also assume that <strong>ALL Deathrattles will be triggered $k$ times</strong> for the sake of the problem. The question is,

<ol>
<li> There are $n$ minions on the board with <strong>exactly one</strong> of them being leapfrogger. If you kill all the $n$ minions in a random order, how many times in expectation will the deathrattle of the leapfrogger be triggered? (Recall that all deathrattles will be triggered $k$ times), answer the question for all $k=2,3,...,m$ for some given parameter $m$. Note that the deathrattles on the last minion still count as triggered, even if they are not given to another minion. </li>
</ol>

输入解释
The first line contains an integer $T(1\leq T\leq 10)$, denoting the number of test cases.

For each test case, the input consists of one line containing two integers $n,m$. $(1\leq n \lt 998244353, 2\leq m \leq 10^5)$, denoting the number of minions and the parameter, respectively.
输出解释
For each test case, the output consists of $m-1$ lines, where on the $i$-th line, you should output a number denoting the expected number of times the deathrattle of leapfrogger is triggered when all deathrattles will be triggered $k=i+1$ times. Under the input constraints of the problem, it can be shown that the answer can be written as a fraction $\frac{P}{Q}$, where $P$ and $Q$ are coprime integers and $Q\not\equiv 0\pmod {998244353}$. You need to output $P\cdot Q^{-1}\pmod{998244353}$ as the answer, where $Q^{-1}\pmod{998244353}$ represents the modular inverse of $Q$ with respect to $998244353$.
输入样例
1
3 2
输出样例
6

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-7237

最后修改于 2022-09-15T06:17:33+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/2500MS(Java/Others) 524288/524288K(Java/Others)