No.2105 Avoid MeX
タグ : / 解いたユーザー数 53
作問者 :
Sumitacchan
/ テスター :
hitonanode
👑 
ygussany
問題文
長さ $N$ の整数列 $a=(a_1,a_2,\dots,a_N)$ を次のように作ります。
- $i=1,2,\dots,N$ のそれぞれに対して $a_i$ の値として、 $C+i$ 未満の非負整数の中から一様ランダムに選択する。
（すなわち、$0,1,\dots,C+i-1$ の中から$\frac{1}{C+i}$ ずつの確率で $1$ つ選択する。 ）
$K=1,2,\dots,N$ の全てに対して $\mathrm{mex}\left(\{a_i\}_{i=1}^K\right)\ne X$ が成り立つ確率を $p_N$ とします。
ここで、$\mathrm{mex}\left(\{a_i\}_{i=1}^K\right)$ は $a_1,a_2,\dots,a_K$ に含まれない最小の非負整数を表します。
このとき、極限 $\lim_{N \to \infty} p_N$ は有理数になります。
この値を注記のように $\bmod\ 998244353$ で求めてください。
注記
求める極限を既約分数 $P/Q$ として表したとき、$RQ\equiv P\ (\bmod\ 998244353)$ かつ $0\le R < 998244353$ を満たす整数 $R$ が一意に存在することが制約より示せます。この $R$ を求めてください。
制約
- $0\le C,X \le 2000$
- 入力は全て整数である。
入力
$C\ \ X$
出力
極限 $\lim_{N \to \infty} p_N$ を $\bmod\ 998244353$ で求めた値を出力してください。
サンプル
サンプル1
入力
0 0
出力
1
必ず $a_1=0$ であるため、以降 $\mathrm{mex}\left(\{a_i\}_{i=1}^K\right)=0$ となることはありません。したがって任意の正整数 $N$ に対して $p_N=1$ となります。
サンプル2
入力
0 1
出力
0
必ず $a_1=0$ であるため、$\mathrm{mex}(\{a_1\})=1\ (=X)$ です。したがって任意の正整数 $N$ に対して $p_N=0$ となります。
サンプル3
入力
1 1
出力
499122177
サンプル4
入力
0 2
出力
748683265
サンプル5
入力
314 1592
出力
535530095
サンプル6
入力
2000 0
出力
151657313
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。