yukicoder No.1518 Simple Combinatorics - かんプリンの学習記録

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${1}$ 以上 ${N}$ 以下の整数をランダムに選ぶという操作を ${K}$ 回行うとき，選ばれた整数の種類数の期待値に ${N^K}$ をかけた値を求めよ．

${1\leq N,K < 10^9+7}$

解説

種類数を ${X}$ とする.
求めるものは ${E[X]=\sum_{k=1}^{N}kP(X=k)}$ で, ${P(X=k)}$ は包除原理とかで求められそうだが面倒なので別の方法を考える.

${\downarrow}$

新たに以下の確率変数 ${Y}$ を導入する.

${\begin{equation} Y_i= \left \{ \begin{array}{l} 1　(K回の操作で1度でもiを選んだ) \\ 0　(K回の操作で1度もiを選ばなかった) \end{array} \right. \end{equation}}$

これを用いると,
$X=\sum_{i=1}^{N}Y_i$
となる. よって期待値の線形性より,
$E[X]=E[\sum_{i=1}^{N}Y_i]=\sum_{i=1}^{N}E[Y_i]$
したがって, 各 ${i}$ について ${E[Y_i]=P(Y_i=1)}$ , つまり ${K}$ 回の操作で ${1}$ 度でも ${i}$ を選ぶ確率を求めればいい．これはどの ${i}$ も $1-\left(\frac{N-1}{N}\right)^K$ なので答えは ${N(N^K-(N-1)^K)}$ となる．

提出プログラム

https://yukicoder.me/submissions/661652

問題概要

解説

提出プログラム

感想