問題一覧 > 通常問題

No.3160 Party Game

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 49
作問者 : 👑 みうね / テスター : jastaway tatesoto 👑 kencho kmmtkm TKTYI fluorine butsurizuki
お気に入りにしたユーザー ProblemId : 12239 / 自分の提出
問題文最終更新日: 2025-05-23 21:22:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
KCPC新歓杯 -Happy Birthday physics0523- (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。