No.2530 Yellow Cards
タグ : / 解いたユーザー数 85
作問者 : 👑
shobonvip
Problem Statement
There is a sports team consisting of $10^{100}$ players, and the uniform numbers $1, 2, \dots, 10^{100}$ are assigned to the players in a one-to-one manner.
A match is played with $N$ of the team's players in the play area and the rest on the bench. The match starts with the players with uniform numbers $1$ through $N$ in the play area.
During the match, a yellow card may be shown to a player in the play area. A player who is shown a yellow card is treated as follows.
- If this is the first time during the match that the player is shown a yellow card, nothing happens.
- If this is the $2$-nd time during the match that the player is shown a yellow card, the player is immediately sent off from the play area. In their place, the player with the smallest uniform number among the players who have not yet been in the play area during the match enters the play area.
Now, after the start of a certain match, the following event occurred $K$ times.
- One player in the play area is chosen at random, and a yellow card is shown to that player.
Output the expected value of the maximum uniform number among the players in the play area immediately after the $K$ events have occurred, modulo $\bmod{998244353}$ as described in the notes below.
Note that before the $1$-st event occurs, no player has been shown a yellow card.
Notes
It can be proved that the desired value is a rational number. It can also be proved that, under the constraints of this problem, when the value is expressed as $\frac{Q}{P}$ using $2$ coprime integers $P,Q$, there exists exactly one integer $R$ satisfying $RP \equiv Q \pmod{998244353}$ and $0 \leq R < 998244353$. Output this $R$.
Constraints
- All input values are integers.
- $1 \leq N, K \leq 5000$
Input
The input is given from standard input in the following format.
$N$ $K$
Output
Output the expected value of the maximum uniform number among the players in the play area immediately after the $K$ events have finished, modulo $\bmod{998244353}$.
Sample
Sample 1
Input
3 2
Output
332748121
Initially, the players with uniform numbers $1, 2, 3$ are in the play area.
For example, if the player with uniform number $1$ is shown a yellow card $2$ times, the player with uniform number $1$ is sent off, and the player with uniform number $4$ enters the play area in their place. In this case, the maximum uniform number is $4$.
On the other hand, if the players with uniform number $1$ and uniform number $3$ are shown yellow cards in this order, no player is sent off. In this case, the maximum uniform number is $3$.
By also considering the other cases, we find that the probability that the maximum uniform number is $3$ is $\frac{2}{3}$, the probability that it is $4$ is $\frac{1}{3}$, and the maximum uniform number never takes any other value.
Therefore, the desired expected value is $3 \times \frac{2}{3} + 4 \times \frac{1}{3} = \frac{10}{3}$. Since $3 \times 332748121 \equiv 10 \pmod{998244353}$, output $332748121$.
Sample 2
Input
2 3
Output
3
No matter how the yellow cards are shown, the maximum uniform number is always $3$. Therefore, the desired expected value is also $3$.
Sample 3
Input
1 5000
Output
2501
There is only $1$ player in the play area. During the $5000$ events, a player is sent off $2500$ times, and the uniform number of the player in the play area immediately after the events finish is $2501$.
Sample 4
Input
11 2023
Output
35139493
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。