Educational Codeforces Round 78: F Cards

色々な解法があるようなので理解のために調べてまとめてみた。

問題概要

https://codeforces.com/contest/1278/problem/F

$JOKERが1枚含まれたm枚のカードから、カードを1枚引いて戻す操作をn回繰り返す。$ $JOKERを引いた回数をxと置くとき、x^kの期待値E\ [ x ^ k ]を求めよ。$

TLを見たところ(1)~(4)の解法が考えられるようだ。

(1)自分の解法 (ゴチャゴチャやる)

$p(x) :=$ (JOKERをx枚引く確率)とおくと $p(x)= {( \frac{1}{m} ) }^ n {( \frac{m-1}{m} ) }^ {n-x} \ _ n C _ x$ が成り立つ。このときFPSを $P(T) = \sum _ { i = 0 } ^ {\infty} p(x) T ^ x$ のようにおくと、二項定理より $P(T) = {( \frac{1}{m}T + \frac{m-1}{m} ) }^ n = m^{-n} \cdot (T + m - 1 ) ^ n$ が成り立つ。

ここで、 $A(T) = \sum _ { i = 0 } ^ {\infty} a(x) T ^ x$ なる $A(T)$ について、「Tで微分してT倍する」という操作をk回行った関数を $B_k(T)$ とおくと、
$B_0(T) = 1 \cdot a_0 + 1 \cdot a_1 T + 1 \cdot a_2 T ^ 2 + 1 \cdot a_3 T ^ 3 + \ldots$
$B_1(T) = 0 \cdot a_0 + 1 \cdot a_1 T + 2 \cdot a_2 T ^ 2 + 3 \cdot a_3 T ^ 3 + \ldots$
$B_2(T) = 0 \cdot a_0 + 1 \cdot a_1 T + 4 \cdot a_2 T ^ 2 + 9 \cdot a_3 T ^ 3 + \ldots$
$B_3(T) = 0 \cdot a_0 + 1 \cdot a_1 T + 8 \cdot a_2 T ^ 2 + 27 \cdot a_3 T ^ 3 + \ldots$
のように係数がTのべき数倍されていき、一般に $B _ k ( T ) = \sum _ { i = 0 } ^ {\infty} { i ^ k \cdot a _ x T ^ x }$ となる。

求めたい値は $E [ T ^ k ] = \sum _ { i = 0 } ^ {\infty} { p(i) i ^ k }$ であるため、 $P(T)$ に上記の操作を $k$ 回行って $T=1$ を代入すればよいとわかり、あとは適切な式変形をすると $O ( k ^ 2 )$ のDPに持ち込める。

(2)モーメント母関数

モーメント母関数の意味と具体例 | 高校数学の美しい物語
 積率母関数 - Wikipedia
詳しくはよく知らないが、リンク先を読んでやることをまとめると
(a) $P(T)$ に $T = e ^ t$ を代入する
(b) $k$ 次の係数を求めると、それが答え
となる。すごい(こなみかん)　よって $M ( e ^ t ) = m ^ {-n} ( e ^ t + m - 1 ) ^ n$ の $k$ 次の項をFPSのpowを使って $O(k \log k)$ で求めればよい。

(3) 多項式補間

P(T)の $a$ 回微分( $0 \leq a \leq k$ )に $T=1$ を代入していくと以下の式が導かれる。
( ${} ^ {(k)}$ は下降階乗冪)
$E [ 1 ]= 1 \ , \ E [ x ]= \frac{n}{m} \ , \ E [ x ( x - 1 ) ] = \frac { n ( n - 1 ) } { m ^ 2 } \ \ldots \ , \ E \ [ x ^ {(k)} ] = \frac{n ^ {(-n)} } { m ^ k }$
これが求まれば、あとは
$x ^ k = a_0 \cdot 1 + a_1 \cdot x + \ldots + a _ k \cdot x ^ {(k)}$
を満たす係数をニュートン補間で求めれば $O(k ^ 2 )$ で $E [ x ^ k ]$ が求まる。
( $a_n$ は性質の良い数列なので式変形や包除などにより係数を直接導出することも可能。後述。)

(4) スターリング数

editorialはこの解き方で解説されているようだ。
確率変数 $x _ i$ を「 $i$ 番目にジョーカーを引いたら1、引かなかったら0」となるようにとる。この時、
$E [ x ^ k ] = E [ ( x _ 1 + x _ 2 + \ldots + x _ n ) ^ k ]$
であり、さらに期待値の線形性を用いると、
$E [ x ^ k ] = \sum _ { 0 \leq i \leq k } { (i種類の確率変数の積) \cdot (その確率) }$
$= \sum _ {0 \leq i \leq k} { (i種類のものを全て使うようにkコ選ぶ ) {} _ n C _ i \cdot \frac { 1 } {m ^ {i} }}$
となる。(i種類のものを全て使うようにkコ選ぶ)というのはいわゆる第二種スターリング数なので、包除や漸化式を用いて $O(k ^ 2)$ で計算できる。

(1)と(2)は同値

$P ( T ) = M ( {e} ^ t )$ について、以下の操作は変数変換すれば等しいとわかる。
(a) $P(T)$ を $x$ で微分して $x$ 倍する操作を $k$ 回繰り返して $x=1$ を代入する
(b) $M ( e ^ t )$ を $t$ で微分する操作を $k$ 回繰り返して $t=0$ を代入する
また、(b)の操作は $M ( e ^ t )$ の $k$ 次の項を求めるのに等しい。

(3)と(4)は同値

途中で補間により求めた数列 $a_n$ は実は第二種スターリング数の定義である。
よってやってることはだいたい同じ(論理の飛躍さん…)

(2)と(4)は同値

(4)で得られた式を第二種スターリング数 $S ( k , i )$ を用いて書き直す。 $E [ x ^ k ] = \sum _ {0 \leq i \leq k}{ S(k , i) \cdot\frac { {} _ n C _ i } {m ^ {i} } }$
ところで第二種スターリング数 $S ( k , i )$ は、実は ${ ( e ^ t - 1) } ^ i$ の $t ^ k$ 次の係数である。
(形式的)べき級数と数え上げの写像12相との関係性前編 - Senの競技プログラミング備忘録
また、(2)の式を変形すると
$E [ x ^ k ] = [ t ^ k ] M ( e ^ t ) = [ t ^ k ] ( m ^ {-n} ( ( e ^ t - 1 ) + m ) ^ n ) = [ t ^ k ] \sum _ { 0 \leq i \leq k } (e ^ t - 1 ) ^ i \cdot \frac { {} _ n C _ i } { m ^ i }$
となる。( $e ^ t - 1$ は1次以上であることからsumの範囲が $k$ 以下に限定されることを用いた)
よってスターリング数のFPS表記と合わせると確かに(2)と(4)は同じ式である。