P8653 - Leapfrogger

内存限制：128 MB 时间限制：3 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：2 通过：0

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.

In the famous card-collecting game Hearthstone, there is a mode named Battlegrounds, 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 leapfrogger, which is a second-tier beast with stats 3/3, and has the deathrattle of "Give a friendly beast +1/+1 and this deathrattle'', 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 stackable, 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, repeated $k$ times. Note that in each of the $k$ times, the friendly beast is chosen independently at random. What makes things more interesting is a minion in Battlegrounds called Baron Rivendare 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, twice. 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 any minion instead of only to beasts. We also assume that ALL Deathrattles will be triggered $k$ times for the sake of the problem. The question is,

There are $n$ minions on the board with exactly one of them being leapfrogger. If you kill all the 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 times), answer the question for all 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.

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 . $(1 \leq n < 998244353, 2 \leq m \leq 1 0^{5})$ , denoting the number of minions and the parameter, respectively.

For each test case, the output consists of

lines, where on the

-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

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

and

are coprime integers and

Q ！ \equiv 0 (mod 998244353)

. You need to output

P \cdot Q^{- 1} (mod 998244353)

as the answer, where

Q^{- 1} (mod 998244353)

represents the modular inverse of

Q

with respect to

1
3 2

2022 杭电多校第九场

8653: Leapfrogger

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签