Educational Codeforces Round 78 (Rated for Div. 2) F. Cards

主にCodeForcesの問題で、一度通した問題の解法を忘れないために特徴的だった問題の解法を記事にまとめることにしました。日本語で詳しく解説してくれている人がいなかったのでこの問題を一問目の記事にします。

$m$ 枚のカードに一枚ジョーカーが含まれている。山札をシャッフルした後一枚のカードを引いて、山札に戻すという行為を $n$ 回繰り返す。ジョーカーを引いた回数を $x$ としたとき $x^k$ の期待値をmod $998244353$ で求めよ。

$1 \le n,m \lt 998244353,1 \le k \le 5000$

愚直に $0$ から $n$ 回ジョーカーを引く確率を求めて期待値を算出するのでは $n$ の制約から間に合わない。 $k$ の制約が小さいのでこれを利用する。

$x^k$ というのは $n$ 回の試行からジョーカーを引くことができた回を重複ありで $k$ 個選ぶ通りの数と言い換えることができる。つまり $k$ 個選んだ時全てジョーカーを引けているか、と考えればよい。

ここで重複ありで $k$ 個選ぶ時、 $1$ ~ $k$ 個の独立した試行を選ぶことになる。 $i$ 個の独立した試行を選んだ時全てジョーカーである確率はもちろん $(1/m)^i$ となる。あとは $i$ 個の独立した試行を選ぶ通り数を求めれば期待値が求まる。

・ $dp$ [ $i$ ][ $j$ ] $:=$ $j$ 個の独立な試行から $i$ 個選んでいるような通り数

と置くことで、上述の値は求めることができるのでこれで $x^k$ の期待値を求めることができた。

umineko-sephi’s blog