問題一覧 > 通常問題

No.2105 Avoid MeX

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 49
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
8 ProblemId : 8326 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-08 11:12:50

問題文

長さ $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$ つ選択する。 )
なお、各 $a_i$ の選択は全て独立に行われます。

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