No.2105 Avoid MeX

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 :

Sumitacchan / テスター :

hitonanode 👑

ygussany

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

出力

必ず $a_1=0$ であるため、以降 $\mathrm{mex}\left(\{a_i\}_{i=1}^K\right)=0$ となることはありません。したがって任意の正整数 $N$ に対して $p_N=1$ となります。

サンプル2

入力

0 1

出力

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