No.3160 Party Game
Problem Statement
$N$ participants who attended a physics lover's birthday party played a game defined by the following rules until the game ended.
The $N$ participants are numbered from $1$ to $N$.
The rules and the ending condition of this game are as follows. The game starts from Step 1.
- Step 1: Reset the points of all $N$ participants to $0$ points. Then, proceed to Step 2.
-
Step 2: For $i=1, 2, \ldots , N$ in this order, perform the following operation. Then, proceed to Step 3.
- In the $i$-th operation, roll an $M$-sided die that shows each integer between $0$ and $M-1$, inclusive, with equal probability. Let $X$ be the number rolled, and update the points of participant $i$ to $X$ points.
- Step 3: If the total points of all $N$ participants is at most $M$ points, end the game. Otherwise, do not end the game, and return to Step 1.
The minimum of the points of the $N$ participants after the game has ended is called the score.
That is, letting $P_i$ be the points of participant $i$ after the game has ended,
the value of the score is $\displaystyle \min_{i=1, 2, \ldots , N} P_i$.
Find the expected value of the score $\mod 998244353$.
What is the expected value $\mod 998244353$?
It can be proved that the expected value to be found is always a rational number.
It can also be proved that, under the constraints of this problem, when this value is expressed as an irreducible fraction $\frac{P}{Q}$, we have $Q \not \equiv 0 \pmod{998244353}$.
Then, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$. Find this $R$.
Constraints
- $1 \leq N \leq 10^6$
- $1 \leq M \leq 10^6$
- $C(N+M,N) \not \equiv N {\rm mod}\ 998244353$ Added after the contest
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N\ M$
Output
Output the answer.
Sample
Sample 1
Input
2 3
Output
623902721
The probability that the score is $0$ is $\displaystyle \frac{5}{8}$, and the probability that it is $1$ is $\displaystyle \frac{3}{8}$. Therefore, the expected value of the score is $\displaystyle \frac{3}{8}$.
Sample 2
Input
1 1
Output
0
The score is always $0$.
Sample 3
Input
5 23
Output
158510335
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
jastaway
butsurizuki