問題一覧 > 通常問題

No.2105 Avoid MeX

レベル : / AI推定難易度 : 1875 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 54
作問者 : Sumitacchan / テスター : 👑 hitonanode ygussany
お気に入りにしたユーザー ProblemId : 8326 / 自分の提出
問題文最終更新日: 2022-10-08 11:12:50
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
yukicoder contest 365 (順位表) の他の問題:

Problem Statement

Construct an integer sequence $a=(a_1,a_2,\dots,a_N)$ of length $N$ as follows.

  • For each $i=1,2,\dots,N$, the value of $a_i$ is chosen uniformly at random from the non-negative integers less than $C+i$.
    (That is, $1$ value is chosen from $0,1,\dots,C+i-1$, each with probability $\frac{1}{C+i}$.)
All choices of $a_i$ are made independently.

Let $p_N$ be the probability that $\mathrm{mex}\left(\{a_i\}_{i=1}^K\right)\ne X$ holds for all $K=1,2,\dots,N$.
Here, $\mathrm{mex}\left(\{a_i\}_{i=1}^K\right)$ denotes the smallest non-negative integer not contained in $a_1,a_2,\dots,a_K$.

Then, the limit $\lim_{N \to \infty} p_N$ is a rational number.
Find this value $\bmod\ 998244353$ as described in the Notes.

Notes

When the limit to be found is expressed as an irreducible fraction $P/Q$, it can be shown from the constraints that there uniquely exists an integer $R$ satisfying $RQ\equiv P\ (\bmod\ 998244353)$ and $0\le R < 998244353$.
Find this $R$.

Constraints

  • $0\le C,X \le 2000$
  • All inputs are integers.

Input

$C\ \ X$

Output

Output the value of the limit $\lim_{N \to \infty} p_N$ computed $\bmod\ 998244353$.

Sample

Sample 1
Input
0 0
Output
1

Since $a_1=0$ always holds, $\mathrm{mex}\left(\{a_i\}_{i=1}^K\right)=0$ never occurs afterward. Therefore, $p_N=1$ for any positive integer $N$.

Sample 2
Input
0 1
Output
0

Since $a_1=0$ always holds, $\mathrm{mex}(\{a_1\})=1\ (=X)$. Therefore, $p_N=0$ for any positive integer $N$.

Sample 3
Input
1 1
Output
499122177

Sample 4
Input
0 2
Output
748683265

Sample 5
Input
314 1592
Output
535530095

Sample 6
Input
2000 0
Output
151657313

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。